DBScholar

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
3346
Venue
SIGMOD
Year
2001
Pagerank
9.3421788e-05
Overall Rank
1,993 | 86.33%
DOI
10.1145/375663.375714

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bohm_sigmod01,
        title = {{Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data}},
        author = {Böhm, Christian and Braunmüller, Bernhard and Krebs, Florian and Kriegel, Hans-Peter},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375714},
        url = {https://dl.acm.org/doi/10.1145/375663.375714},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014110016
911 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013283031
3,041 Spatio-Textual Similarity Joins 2013 VLDB 7.8254399e-05
5,186 On Link-based Similarity Join 2011 VLDB 6.3279474e-05
5,405 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.2291247e-05
5,467 On Producing Join Results Early 2003 PODS 6.2074577e-05
6,157 Similarity Join over Array Data 2016 SIGMOD 5.9554363e-05
6,880 Real-time Distributed Co-Movement Pattern Detection on Streaming Trajectories 2019 VLDB 5.7470112e-05
7,715 Cache-oblivious High-performance Similarity Join 2019 SIGMOD 5.5606224e-05
8,178 Adaptable Similarity Search using Non-Relevant Information 2002 VLDB 5.4728384e-05
8,499 THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads 2015 SIGMOD 5.4133616e-05
9,052 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 5.3251649e-05
10,359 DiskJoin: Large-scale Vector Similarity Join with SSD 2026 SIGMOD 5.093636e-05
10,951 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 5.093636e-05
12,442 SimDB: A Similarity-aware Database System 2010 SIGMOD 5.093636e-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
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029548428
291 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00022264197
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
350 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020425134
351 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00020424271
693 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.00014918477
728 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014542772
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
994 Spatial Hash-Joins 1996 SIGMOD 0.00012764684
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.5068846e-05
2,310 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.7650894e-05
2,548 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.432498e-05
3,066 Size Separation Spatial Join 1997 SIGMOD 7.7941163e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 21 Similarity Search in High Dimensions via Hashing 1999 VLDB
2 7,715 Cache-oblivious High-performance Similarity Join 2019 SIGMOD
3 690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD
4 2,567 ClusterJoin: A Similarity Joins Framework using Map-Reduce 2014 VLDB
5 9,052 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD
6 200 Efficient set joins on similarity predicates 2004 SIGMOD
7 6,157 Similarity Join over Array Data 2016 SIGMOD
8 13,672 Exploiting Database Similarity Joins for Metric Spaces 2012 VLDB
9 3,671 Exploiting MapReduce-based Similarity Joins 2012 SIGMOD
10 7,326 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB