42:
One application would be calculating national election results. Construct a tree with the root node as the entire nation and each level representing refined geographical areas such as states/provinces, counties/parishes, cities/townships, and polling districts as the leaves. By accumulating the vote
39:
Upward accumulation refers to accumulating on each node information about all descendants. Downward accumulation refers to accumulating on each node information of every ancestor.
90:
150:
129:
Gibbons, Jeremy; Cai, Wentong; Skillcorn, David B. (1994). "Efficient parallel algorithms for tree accumulations".
43:
totals from the polling districts, one can compute the vote totals for each of the larger geographic areas.
29:
25:
51:
Gibbons et al. formally define binary tree accumulation as iterative application of a ternary operator
54:
17:
144:
33:
110:
92:; where A are descendant labels and B is a junction label.
57:
84:
24:is the process of accumulating data placed in
8:
56:
32:structure. Formally, this operation is a
101:
7:
14:
131:Science of Computer Programming
85:{\displaystyle \otimes (A,B,A)}
79:
61:
1:
112:Algebras for Tree Algorithms
118:(Ph.D.). Oxford University.
167:
28:nodes according to their
109:Gibbons, Jeremy (1991).
151:Trees (data structures)
86:
87:
55:
82:
22:tree accumulation
158:
135:
134:
126:
120:
119:
117:
106:
91:
89:
88:
83:
18:computer science
166:
165:
161:
160:
159:
157:
156:
155:
141:
140:
139:
138:
128:
127:
123:
115:
108:
107:
103:
98:
53:
52:
49:
47:Formal analysis
12:
11:
5:
164:
162:
154:
153:
143:
142:
137:
136:
121:
100:
99:
97:
94:
81:
78:
75:
72:
69:
66:
63:
60:
48:
45:
13:
10:
9:
6:
4:
3:
2:
163:
152:
149:
148:
146:
132:
125:
122:
114:
113:
105:
102:
95:
93:
76:
73:
70:
67:
64:
58:
46:
44:
40:
37:
35:
31:
27:
23:
19:
130:
124:
111:
104:
50:
41:
38:
34:catamorphism
21:
15:
133:. Elsiver.
96:References
59:⊗
145:Category
116:(PDF)
30:tree
26:tree
16:In
147::
36:.
20:,
80:)
77:A
74:,
71:B
68:,
65:A
62:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.