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.0904184e-05
Overall Rank: 5,536 | 62.80%
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,175	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	8.918268e-05
3,811	On the Complexity of Inner Product Similarity Join	2016	PODS	7.0061203e-05
6,795	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.6785871e-05
8,829	Spatial Queries with Two kNN Predicates	2012	VLDB	5.2669831e-05
9,688	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1403642e-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.0019923528
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051292389
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029189529
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029048509
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014239937
994	Spatial Hash-Joins	1996	SIGMOD	0.00012630797
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010270215
1,634	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010013999
1,998	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.2123795e-05
2,589	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2479257e-05
3,017	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7455245e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	583	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD
2	10,382	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
3	10,336	Distributed Stream KNN Join	2021	SIGMOD
4	8,935	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
5	8,416	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
6	11,498	Improved Approximation Algorithms for Relational Clustering	2024	PODS
7	8,046	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
8	1,998	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,175	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB