GORDER: An Efficient Method for KNN Join Processing

Summary: GORDER: a G-ordering KNN-join via a block-nested-loop (BNLJ) for high-dimensional data. It uses G-order sorting, scheduled BNLJ, and distance filtering/reduction to reduce I/O and CPU, achieving wide-margin gains over existing KNN-join methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9185
Venue: VLDB
Year: 2004
Pagerank: 5.3924438e-05
Overall Rank: 5,646 | 60.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,927	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	0.00010062395
4,808	On the Complexity of Inner Product Similarity Join	2016	PODS	5.9040739e-05
6,802	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	4.9172931e-05
8,629	Spatial Queries with Two kNN Predicates	2012	VLDB	4.4766922e-05
9,353	Rank Join Queries in NoSQL Databases	2014	VLDB	4.3485003e-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.0032118946
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
159	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00040135453
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
1,802	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001048177
2,285	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1097273e-05
2,905	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	7.9364369e-05
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,953	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.8060034e-05
697	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017964755
9,952	Distributed Stream KNN Join	2021	SIGMOD	4.236537e-05
8,559	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	4.4893996e-05
8,899	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	4.4229886e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
2,285	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1097273e-05
3,139	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	7.4915127e-05
1,927	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	0.00010062395