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: 10341
Venue: VLDB
Year: 2012
Pagerank: 0.00010040427
Overall Rank: 1,931 | 86.57%
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,435	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00012004456
2,300	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	9.0677864e-05
2,674	Minimal MapReduce Algorithms	2013	SIGMOD	8.3328645e-05
3,129	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.5008242e-05
4,650	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.0234336e-05
5,980	The Era of Big Spatial Data	2017	VLDB	5.2449608e-05
7,125	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	4.8246382e-05
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
7,271	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	4.7813404e-05
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-05
8,575	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4928872e-05
8,709	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	4.4638829e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1945683e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-05
11,927	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	4.1945683e-05
11,976	Anti-Combining for MapReduce	2014	SIGMOD	4.1945683e-05
12,064	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	4.1945683e-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.00076637636
161	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00039846974
447	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00022900171
774	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016865771
1,074	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014260096
1,615	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00011132319
1,715	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010803271
3,300	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2516103e-05
5,636	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	5.3981191e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
1,074	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014260096
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
5,636	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	5.3981191e-05
4,147	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD	6.4096022e-05
15	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.0010654262
4,775	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	5.9315784e-05
960	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00015012242
447	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00022900171
3,141	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	7.4829448e-05