140:, users need to specify the key type, the comparison function on the key type, the value type, the augmented value type, the base function, the combine function and the identity of the combine function.
90:
PAM supports functions on sequences including construction, find an entry with a certain rank, first, last, next, previous, size, empty, filter, map-reduce, concatenating, etc.
395:
Ben-David, Naama; Blelloch, Guy E.; Sun, Yihan; Wei, Yuanhao (17 June 2019). "Multiversion
Concurrency with Bounded Delay and Precise Garbage Collection".
379:
414:
32:
211:
128:
On top of the ordered set interface, PAM also supports functions for ordered maps, such as insertion with combining values.
125:
To define an ordered map, users need to specify the key type, the comparison function on the key type, and the value type.
457:
158:
The library also provides example implementations for a number of applications, including 1D stabbing query (using
36:
71:
452:
105:
On top of the sequence interface, PAM also supports functions for ordered sets including insertion, deletion,
70:. Theoretically, all algorithms in PAM are work-efficient and have polylogarithmic depth. PAM uses underlying
143:
On top of the ordered map interface, PAM also supports functions for augmented maps, such as aug_range.
52:
98:
To define an ordered set, users need to specify the key type and the comparison function defining a
183:
179:
171:
355:
328:
106:
58:
PAM is a parallel library and is also safe for concurrency. Its parallelism can be supported by
410:
375:
320:
301:"On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes"
259:
24:
400:
365:
312:
251:
67:
44:
207:
198:
The library has been tested in various applications, including database benchmarks, 2D
187:
114:
99:
300:
74:
tree structure such that multi-versioning is allowed. PAM also supports efficient GC.
446:
332:
239:
203:
159:
147:
137:
28:
199:
175:
110:
352:
2019 Proceedings of the
Meeting on Algorithm Engineering and Experiments (ALENEX)
163:
20:
19:
is an open-source parallel C++ library implementing the interface for sequence,
370:
347:
167:
324:
316:
299:
Sun, Yihan; Blelloch, Guy E.; Lim, Wan Shen; Pavlo, Andrew (1 October 2019).
263:
405:
255:
87:
To define a sequence, users need to specify the key type of the sequence.
40:
284:
397:
The 31st ACM Symposium on
Parallelism in Algorithms and Architectures
63:
436:
360:
348:"Parallel Range, Segment and Rectangle Queries with Augmented Maps"
48:
238:
Sun, Yihan; Ferizovic, Daniel; Belloch, Guy E. (23 March 2018).
59:
31:. The library is available on GitHub. It uses the underlying
146:
In addition to the tree structures, PAM also implements the
354:. Society for Industrial and Applied Mathematics: 159–173.
399:. Association for Computing Machinery. pp. 241–252.
182:), 2D rectangle query (using a tree structure and a
39:. PAM supports four balancing schemes, including
346:Sun, Yihan; Blelloch, Guy E. (1 January 2019).
8:
404:
369:
359:
223:
154:Implementation for Example Applications
439:, the parallel augmented map library.
286:Problem Based Benchmark Suite Library
233:
231:
229:
227:
7:
14:
305:Proceedings of the VLDB Endowment
212:multiversion concurrency control
240:"PAM: parallel augmented maps"
33:balanced binary tree structure
1:
174:), 2D segment query (using a
17:PAM (Parallel Augmented Maps)
474:
371:10.1137/1.9781611975499.13
317:10.14778/3364324.3364334
188:inverted index searching
406:10.1145/3323165.3323185
256:10.1145/3200691.3178509
53:weight-balanced trees
37:join-based algorithms
194:Used in applications
150:for augmented maps.
66:or the scheduler in
244:ACM SIGPLAN Notices
184:sweepline algorithm
180:sweepline algorithm
172:sweepline algorithm
458:Computer libraries
381:978-1-61197-549-9
102:on the key type.
465:
421:
420:
408:
392:
386:
385:
373:
363:
343:
337:
336:
296:
290:
289:
281:
275:
274:
272:
270:
235:
148:prefix structure
473:
472:
468:
467:
466:
464:
463:
462:
443:
442:
433:
427:
425:
424:
417:
394:
393:
389:
382:
345:
344:
340:
298:
297:
293:
283:
282:
278:
268:
266:
237:
236:
225:
220:
196:
156:
134:
123:
96:
85:
80:
45:red-black trees
12:
11:
5:
471:
469:
461:
460:
455:
445:
444:
441:
440:
432:
431:External links
429:
423:
422:
415:
387:
380:
338:
311:(2): 211–225.
291:
276:
250:(1): 290–304.
222:
221:
219:
216:
208:inverted index
195:
192:
160:interval trees
155:
152:
133:
132:Augmented maps
130:
122:
119:
100:total ordering
95:
92:
84:
81:
79:
76:
29:augmented maps
13:
10:
9:
6:
4:
3:
2:
470:
459:
456:
454:
453:C++ libraries
451:
450:
448:
438:
435:
434:
430:
428:
418:
416:9781450361842
412:
407:
402:
398:
391:
388:
383:
377:
372:
367:
362:
357:
353:
349:
342:
339:
334:
330:
326:
322:
318:
314:
310:
306:
302:
295:
292:
288:
287:
280:
277:
265:
261:
257:
253:
249:
245:
241:
234:
232:
230:
228:
224:
217:
215:
213:
209:
205:
204:interval tree
201:
193:
191:
189:
185:
181:
177:
173:
169:
165:
161:
153:
151:
149:
144:
141:
139:
138:augmented map
136:To define an
131:
129:
126:
120:
118:
116:
112:
108:
103:
101:
93:
91:
88:
82:
77:
75:
73:
69:
65:
61:
56:
54:
50:
46:
42:
38:
34:
30:
26:
22:
18:
426:
396:
390:
351:
341:
308:
304:
294:
285:
279:
267:. Retrieved
247:
243:
200:segment tree
197:
176:segment tree
157:
145:
142:
135:
127:
124:
121:Ordered maps
111:intersection
104:
97:
94:Ordered sets
89:
86:
57:
21:ordered sets
16:
15:
269:5 September
164:range query
447:Categories
361:1803.08621
218:References
168:range tree
115:difference
72:persistent
23:, ordered
333:204841857
325:2150-8097
264:0362-1340
166:(using a
83:Sequences
78:Interface
41:AVL trees
190:, etc.
117:, etc.
413:
378:
331:
323:
262:
178:and a
170:and a
64:OpenMP
49:treaps
35:using
27:, and
356:arXiv
329:S2CID
202:, 2D
162:, 2D
107:union
411:ISBN
376:ISBN
321:ISSN
271:2020
260:ISSN
210:and
68:PBBS
60:cilk
51:and
25:maps
437:PAM
401:doi
366:doi
313:doi
252:doi
186:),
449::
409:.
374:.
364:.
350:.
327:.
319:.
309:13
307:.
303:.
258:.
248:53
246:.
242:.
226:^
214:.
206:,
113:,
109:,
62:,
55:.
47:,
43:,
419:.
403::
384:.
368::
358::
335:.
315::
273:.
254::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.