A parallel buffer tree

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Nodar Sitchinava, Denmark
  • Norbert Zeh, Faculty of Computer Science, Dalhouse University, Canada
We present the parallel buffer tree, a parallel external memory (PEM) data structure for batched search problems. This data structure is a non-trivial extension of Arge's sequential buffer tree to a private-cache multiprocessor environment and reduces the number of I/O operations by the number of available processor cores compared to its sequential counterpart, thereby taking full advantage of multicore parallelism.

The parallel buffer tree is a search tree data structure that supports the batched parallel processing of a sequence of N insertions, deletions, membership queries, and range queries in the optimal OhOf(psortN + K/PB) parallel I/O complexity, where K is the size of the output reported in the process and psortN is the parallel I/O complexity of sorting N elements using P processors.
Original languageEnglish
Title of host publicationProceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2012
ISBN (print)978-1-4503-1213-4
Publication statusPublished - 2012
EventSymposium on Parallelism in Algorithms and Architectures - Montreal, Canada
Duration: 23 Jul 201225 Feb 2013
Conference number: 24


ConferenceSymposium on Parallelism in Algorithms and Architectures

See relations at Aarhus University Citationformats

ID: 52736529