Cache-oblivious High-performance Similarity Join

Summary: Cache-oblivious similarity join with a space-filling-curve order to boost data locality. Proposes the Fast General Form (FGF) Hilbert-curve: non-recursive, square-agnostic, constant-time per-iteration, enabling cache-oblivious, parallel refinement and operator portability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hbec02422d10e3a3c
Venue: SIGMOD
Year: 2019
Pagerank: 5.4962229e-05
Overall Rank: 7,560 | 49.18%
DOI: 10.1145/3299869.3319859

Incoming Non-self Citations Over Time

Authors

1. Martin Perdacher (University of Vienna)
2. Claudia Plant (University of Vienna)
3. Christian Böhm (Ludwig Maximilian University of Munich)

BibTeX Citation

@inproceedings{perdacher_sigmod19,
        title = {{Cache-oblivious High-performance Similarity Join}},
        author = {Perdacher, Martin and Plant, Claudia and Böhm, Christian},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319859},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319859},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.336718e-05
9,811	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	5.1257999e-05
11,028	Advances of Query Processing in Vector Databases	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023175253
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1790375e-05
4,274	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	6.6918599e-05
6,149	Similarity Join over Array Data	2016	SIGMOD	5.8706665e-05
9,060	EaseDB: A Cache-Oblivious In-Memory Query Processor	2007	SIGMOD	5.2291768e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,507	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB
2	201	Efficient set joins on similarity predicates	2004	SIGMOD
3	9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD
4	7,468	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
5	6,149	Similarity Join over Array Data	2016	SIGMOD
6	11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
7	13,985	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
8	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
9	2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
10	361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD