Worst-Case-Optimal Similarity Joins on Graph Databases

Summary: Worst-case-optimal graph equijoins extended to k-NN similarity by fusing the data graph with a k-NN graph and using LTJ on a Ring to integrate similarity predicates. Wikidata–IMGpedia experiments show clear gains over a two-phase baseline, especially for dense similarity connections (up to an order of magnitude). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6910
Venue: SIGMOD
Year: 2024
Pagerank: 5.1558402e-05
Overall Rank: 10,087 | 30.80%
DOI: 10.1145/3639294

Incoming Non-self Citations Over Time

Authors

1. Diego Arroyuelo (Millennium Institute for Foundational Data; Pontifical Catholic University of Chile)
2. Benjamin Bustos (Millennium Institute for Foundational Data; University of Chile)
3. Adrián Gómez-Brandón (Millennium Institute for Foundational Data; Research Center for Information and Communication Technologies; University of A Coruña)
4. Aidan Hogan (Millennium Institute for Foundational Data; University of Chile)
5. Gonzalo Navarro (Millennium Institute for Foundational Data; University of Chile)
6. Juan Reutter (Millennium Institute for Foundational Data; Pontifical Catholic University of Chile)

BibTeX Citation

@inproceedings{arroyuelo_sigmod24,
        title = {{Worst-Case-Optimal Similarity Joins on Graph Databases}},
        author = {Arroyuelo, Diego and Bustos, Benjamin and Gómez-Brandón, Adrián and Hogan, Aidan and Navarro, Gonzalo and Reutter, Juan},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639294},
        url = {https://dl.acm.org/doi/10.1145/3639294},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,896	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	5.3495662e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	9.6489549e-05
1,944	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.4354517e-05
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
4,753	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5231863e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
6,387	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	5.8896555e-05
6,672	Computing Join Queries with Functional Dependencies	2016	PODS	5.8070233e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS
2	200	Efficient set joins on similarity predicates	2004	SIGMOD
3	6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
4	10,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
5	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
6	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
7	9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
8	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
9	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
10	4,753	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD