Parallel algorithms for constructing range and nearest-neighbor searching data structures

Conference Paper

With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for kd-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Fox, K; Munagala, K; Nath, A

Published Date

  • June 15, 2016

Published In

  • Proceedings of the Acm Sigact Sigmod Sigart Symposium on Principles of Database Systems

Volume / Issue

  • 26-June-01-July-2016 /

Start / End Page

  • 429 - 440

International Standard Book Number 13 (ISBN-13)

  • 9781450341912

Digital Object Identifier (DOI)

  • 10.1145/2902251.2902303

Citation Source

  • Scopus