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.8973287e-05
Overall Rank: 2,183 | 85.37%
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,183	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011589152
2,561	Minimal MapReduce Algorithms	2013	SIGMOD	8.2743492e-05
2,866	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	7.9054791e-05
3,071	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6670408e-05
4,532	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.5412636e-05
5,142	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	6.2420637e-05
6,476	The Era of Big Spatial Data	2017	VLDB	5.7551052e-05
7,082	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	5.5894172e-05
7,284	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5505534e-05
7,542	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.4821664e-05
8,364	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3304544e-05
8,683	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2733366e-05
8,834	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.2524856e-05
10,357	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0156513e-05
12,467	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	4.9605343e-05
12,514	Anti-Combining for MapReduce	2014	SIGMOD	4.9605343e-05
12,602	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	4.9605343e-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.00057610161
143	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029095978
359	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00019963275
698	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.0001465073
867	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013342302
1,424	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010694144
1,470	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00010532106
3,025	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7214661e-05
5,547	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0715188e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,761	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
2	867	Processing Theta-Joins using MapReduce*	2011	SIGMOD
3	4,749	Finding Near Neighbors Through Cluster Pruning	2007	PODS
4	5,547	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB
5	3,695	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD
6	76	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD
7	4,282	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	359	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD
10	2,581	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB