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.0715188e-05
Overall Rank: 5,547 | 62.82%
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,183	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	8.8973287e-05
3,774	On the Complexity of Inner Product Similarity Join	2016	PODS	7.0102162e-05
6,811	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.6598101e-05
8,847	Spatial Queries with Two kNN Predicates	2012	VLDB	5.2495672e-05
9,717	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1233669e-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.0019892478
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051134355
143	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029095978
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
760	Partition Based Spatial-Merge Join	1996	SIGMOD	0.0001419395
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010236406
1,642	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	9.9812004e-05
2,007	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.182637e-05
2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2212352e-05
3,025	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7214661e-05

Semantically Similar Papers

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