Database Paper Browser

Back to papers

Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data

Summary: Proposes Epsilon Grid Order, a scalable similarity-join for massive high-dimensional data using an equi-distant grid-order. Achieves memory efficiency with external sorting and a join-phase schedule, beating MSJ and epsilon-kdB-tree on large datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3284
Venue
SIGMOD
Year
2001
Pagerank
9.1077704e-05
Overall Rank
2,281 | 84.14%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
1,234 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013122499
3,514 Spatio-Textual Similarity Joins 2013 VLDB 7.0226998e-05
4,995 On Link-based Similarity Join 2011 VLDB 5.7787414e-05
5,511 On Producing Join Results Early 2003 PODS 5.4699346e-05
5,636 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3981191e-05
6,507 Similarity Join over Array Data 2016 SIGMOD 5.0337166e-05
7,037 Real-time Distributed Co-Movement Pattern Detection on Streaming Trajectories 2019 VLDB 4.8548122e-05
7,765 Cache-oblivious High-performance Similarity Join 2019 SIGMOD 4.6572085e-05
7,855 Adaptable Similarity Search using Non-Relevant Information 2002 VLDB 4.6348533e-05
8,575 THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads 2015 SIGMOD 4.4928872e-05
8,899 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 4.427232e-05
10,068 DiskJoin: Large-scale Vector Similarity Join with SSD 2026 SIGMOD 4.1945683e-05
10,706 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 4.1945683e-05
12,247 SimDB: A Similarity-aware Database System 2010 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank Cited Paper Year Venue Pagerank
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032163466
270 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00029505642
341 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026810548
354 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026137988
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018451109
774 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.00016865771
925 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015264328
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
2,136 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.4721139e-05
2,672 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3363695e-05
2,900 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9405413e-05
3,457 Size Separation Spatial Join 1997 SIGMOD 7.0755358e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
7,765 Cache-oblivious High-performance Similarity Join 2019 SIGMOD 4.6572085e-05
709 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00017768547
3,141 ClusterJoin: A Similarity Joins Framework using Map-Reduce 2014 VLDB 7.4829448e-05
250 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030661988
8,899 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 4.427232e-05
6,507 Similarity Join over Array Data 2016 SIGMOD 5.0337166e-05
13,473 Exploiting Database Similarity Joins for Metric Spaces 2012 VLDB -
4,147 Exploiting MapReduce-based Similarity Joins 2012 SIGMOD 6.4096022e-05
7,133 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226285e-05