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: 10529
Venue: VLDB
Year: 2012
Pagerank: 9.110238e-05
Overall Rank: 2,137 | 85.34%
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,175	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011812263
2,539	Minimal MapReduce Algorithms	2013	SIGMOD	8.4526595e-05
2,794	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	8.1167671e-05
3,008	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.8578871e-05
4,480	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.67565e-05
6,382	The Era of Big Spatial Data	2017	VLDB	5.8915267e-05
6,995	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.7301567e-05
7,111	Submodularity of Distributed Join Computation	2018	SIGMOD	5.69924e-05
7,218	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	5.6683391e-05
7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.629255e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
8,644	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.3934068e-05
9,776	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.2209769e-05
10,412	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.093636e-05
12,125	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	5.093636e-05
12,174	Anti-Combining for MapReduce	2014	SIGMOD	5.093636e-05
12,262	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	5.093636e-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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.0002962566
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00014918477
843	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013666161
1,415	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010840141
1,436	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00010797443
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05

Semantically Similar Papers

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