Efficient Processing of k Nearest Neighbor Joins using MapReduce

Summary: kNN join on MapReduce: mappers cluster objects; reducers perform per-group kNN joins. distance pruning and two approximate replica-minimization strategies cut shuffling and computation, yielding scalable, robust performance on large clusters. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10342
Venue: VLDB
Year: 2012
Pagerank: 0.00010062395
Overall Rank: 1,927 | 86.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,301	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00012702767
2,304	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	9.0659453e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
4,646	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.0176549e-05
5,985	The Era of Big Spatial Data	2017	VLDB	5.2399365e-05
7,121	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	4.8200109e-05
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
7,268	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	4.7769096e-05
7,827	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.6379617e-05
8,572	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4885798e-05
8,704	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	4.4596039e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1905499e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-05
11,935	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	4.1905499e-05
11,984	Anti-Combining for MapReduce	2014	SIGMOD	4.1905499e-05
12,072	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
159	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00040135453
442	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00023095823
768	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016864875
1,073	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014255717
1,615	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00011137225
1,775	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010584816
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05
5,646	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	5.3924438e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,026	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5166769e-05
1,073	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014255717
4,096	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4506806e-05
5,646	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	5.3924438e-05
4,130	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD	6.4205218e-05
15	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.0010668335
4,752	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	5.9396804e-05
962	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00015003834
442	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00023095823
3,139	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	7.4915127e-05