Skip to main content

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

Publication ,  Conference
Agarwal, PK; Fox, K; Munagala, K; Nath, A
Published in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
June 15, 2016

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.

Duke Scholars

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISBN

9781450341912

Publication Date

June 15, 2016

Volume

26-June-01-July-2016

Start / End Page

429 / 440
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., Fox, K., Munagala, K., & Nath, A. (2016). Parallel algorithms for constructing range and nearest-neighbor searching data structures. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Vol. 26-June-01-July-2016, pp. 429–440). https://doi.org/10.1145/2902251.2902303
Agarwal, P. K., K. Fox, K. Munagala, and A. Nath. “Parallel algorithms for constructing range and nearest-neighbor searching data structures.” In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 26-June-01-July-2016:429–40, 2016. https://doi.org/10.1145/2902251.2902303.
Agarwal PK, Fox K, Munagala K, Nath A. Parallel algorithms for constructing range and nearest-neighbor searching data structures. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2016. p. 429–40.
Agarwal, P. K., et al. “Parallel algorithms for constructing range and nearest-neighbor searching data structures.” Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, vol. 26-June-01-July-2016, 2016, pp. 429–40. Scopus, doi:10.1145/2902251.2902303.
Agarwal PK, Fox K, Munagala K, Nath A. Parallel algorithms for constructing range and nearest-neighbor searching data structures. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2016. p. 429–440.

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISBN

9781450341912

Publication Date

June 15, 2016

Volume

26-June-01-July-2016

Start / End Page

429 / 440