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: 5733
Venue: SIGMOD
Year: 2019
Pagerank: 5.5606224e-05
Overall Rank: 7,715 | 47.07%
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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.3251649e-05
9,634	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	5.2434488e-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.00040719947
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
4,260	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	6.7984322e-05
6,157	Similarity Join over Array Data	2016	SIGMOD	5.9554363e-05
8,948	EaseDB: A Cache-Oblivious In-Memory Query Processor	2007	SIGMOD	5.3463915e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,470	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB
2	200	Efficient set joins on similarity predicates	2004	SIGMOD
3	10,359	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD
4	7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
5	6,157	Similarity Join over Array Data	2016	SIGMOD
6	10,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
7	13,672	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
8	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
9	2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
10	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD