Publications [#321941] of Kamesh Munagala

Journal articles or Book chapters PUBLISHED

1. 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, vol. 26-June-01-July-2016 (June, 2016), pp. 429-440, ACM Press, ISBN 9781450341912 [doi]
   (last updated on 2024/04/24)

   Abstract:
   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.