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: 9375
Venue: VLDB
Year: 2004
Pagerank: 6.2291247e-05
Overall Rank: 5,405 | 62.92%
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,137	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	9.110238e-05
3,806	On the Complexity of Inner Product Similarity Join	2016	PODS	7.108802e-05
6,749	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.7844585e-05
8,659	Spatial Queries with Two kNN Predicates	2012	VLDB	5.3904242e-05
9,497	Rank Join Queries in NoSQL Databases	2014	VLDB	5.2608378e-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.0020210012
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.0002962566
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,602	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010239526
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.432498e-05
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05

Semantically Similar Papers

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