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.918268e-05
Overall Rank: 2,175 | 85.39%
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.00011627256
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2782871e-05
2,858	A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data	2013	VLDB	7.931706e-05
3,068	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6841028e-05
4,514	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB	6.5629213e-05
6,230	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.842393e-05
6,463	The Era of Big Spatial Data	2017	VLDB	5.7741601e-05
7,062	Fast Failure Recovery in Distributed Graph Processing Systems	2015	VLDB	5.6079605e-05
7,266	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5689674e-05
7,524	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.500354e-05
8,350	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3481387e-05
8,666	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2908314e-05
8,817	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.2699112e-05
10,331	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0322912e-05
12,424	TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems	2015	VLDB	4.9769913e-05
12,471	Anti-Combining for MapReduce	2014	SIGMOD	4.9769913e-05
12,559	Mobility and Social Networking: A Data Management Perspective	2013	VLDB	4.9769913e-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.0005758001
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029189529
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020001237
695	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00014696154
866	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013381756
1,421	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010722146
1,466	The Performance of MapReduce: An In-depth Study	2010	VLDB	0.00010565007
3,017	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7455245e-05
5,536	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0904184e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,757	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
2	866	Processing Theta-Joins using MapReduce*	2011	SIGMOD
3	4,730	Finding Near Neighbors Through Cluster Pruning	2007	PODS
4	5,536	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB
5	3,694	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD
6	75	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD
7	4,275	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