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.4754557e-05
Overall Rank: 7,580 | 49.20%
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,434	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.3165535e-05
9,852	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	5.1064323e-05
11,098	Advances of Query Processing in Vector Databases	2026	VLDB	4.9605343e-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.0004024707
102	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033850505
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023099455
934	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00012973416
2,007	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.182637e-05
3,604	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1548073e-05
4,282	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	6.6712965e-05
6,168	Similarity Join over Array Data	2016	SIGMOD	5.8484846e-05
9,088	EaseDB: A Cache-Oblivious In-Memory Query Processor	2007	SIGMOD	5.2094186e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,515	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB
2	202	Efficient set joins on similarity predicates	2004	SIGMOD
3	9,947	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD
4	7,491	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
5	6,168	Similarity Join over Array Data	2016	SIGMOD
6	11,400	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
7	14,030	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
8	8,434	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
9	2,475	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