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: h8c6fabb1b2a61a82
Venue: VLDB
Year: 2012
Pagerank: 8.9159001e-05
Overall Rank: 2,176 | 85.38%
DOI: 10.14778/2336664.2336675

Incoming Non-self Citations Over Time

Authors

1. Wei Lu (National University of Singapore)
2. Yanyan Shen (National University of Singapore)
3. Su Chen (National University of Singapore)
4. Beng Chin Ooi (National University of Singapore)

BibTeX Citation

@article{lu_vldb12,
        title = {{Efficient Processing of k Nearest Neighbor Joins using MapReduce}},
        author = {Lu, Wei and Shen, Yanyan and Chen, Su and Ooi, Beng Chin},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {10},
        pages = {1016--1027},
        doi = {10.14778/2336664.2336675},
        url = {https://doi.org/10.14778/2336664.2336675},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,178	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011632691
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2821647e-05
2,858	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	7.9354625e-05
3,066	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6877117e-05
4,513	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.565997e-05
6,461	The Era of Big Spatial Data	2017	VLDB	5.7768622e-05
6,895	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6536466e-05
7,059	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	5.6106152e-05
7,259	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5716049e-05
7,519	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.502959e-05
8,658	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2933372e-05
8,809	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.2724071e-05
9,551	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1591583e-05
10,324	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0346745e-05
12,418	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	4.9793485e-05
12,465	Anti-Combining for MapReduce	2014	SIGMOD	4.9793485e-05
12,553	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	4.9793485e-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
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029202746
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020009936
695	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00014702685
865	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.0001338765
1,421	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010726757
1,466	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00010569837
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05
5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0932822e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,755	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
2	865	Processing Theta-Joins using MapReduce*	2011	SIGMOD
3	4,728	Finding Near Neighbors Through Cluster Pruning	2007	PODS
4	5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB
5	3,691	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD
6	75	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD
7	4,274	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB
8	799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD
9	360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD
10	2,577	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB