GORDER: An Efficient Method for KNN Join Processing

Summary: GORDER accelerates high-dimensional KNN joins by G-ordering data and scheduling block-nested-loop comparisons. Distance-computation filtering/reduction cuts CPU and I/O costs, substantially outperforming prior methods on clustered and real datasets. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h3768ef8f6c683532
Venue: VLDB
Year: 2004
Pagerank: 6.0932822e-05
Overall Rank: 5,532 | 62.81%
DOI: 10.1016/B978-012088469-8.50067-X

Incoming Non-self Citations Over Time

Authors

1. Chenyi Xia (National University of Singapore)
2. Hongjun Lu (Hong Kong University of Science and Technology)
3. Beng Chin Ooi (National University of Singapore)
4. Jing Hu (National University of Singapore)

BibTeX Citation

@article{xia_vldb04,
        title = {{GORDER: An Efficient Method for KNN Join Processing}},
        author = {Xia, Chenyi and Lu, Hongjun and Ooi, Beng Chin and Hu, Jing},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {756},
        doi = {10.1016/B978-012088469-8.50067-X},
        url = {https://doi.org/10.1016/B978-012088469-8.50067-X},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,176	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	8.9159001e-05
3,809	On the Complexity of Inner Product Similarity Join	2016	PODS	7.0089846e-05
6,790	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.6812765e-05
8,820	Spatial Queries with Two kNN Predicates	2012	VLDB	5.2694776e-05
9,681	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1427987e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029202746
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
1,634	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001001862
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2518251e-05
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	583	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD
2	10,370	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
3	10,329	Distributed Stream KNN Join	2021	SIGMOD
4	8,927	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
5	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
6	11,492	Improved Approximation Algorithms for Relational Clustering	2024	PODS
7	8,039	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
8	1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD
9	2,577	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB
10	2,176	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB