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: 6848
Venue: SIGMOD
Year: 2024
Pagerank: 4.2456408e-05
Overall Rank: 9,940 | 30.85%
DOI: 10.1145/3639294

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,367	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,228	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.2385241e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,505	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.634551e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
5,493	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4771449e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
6,639	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	4.9801324e-05
6,824	Computing Join Queries with Functional Dependencies	2016	PODS	4.9144789e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,833	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7173578e-05
250	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030661988
7,109	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8292998e-05
10,706	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1945683e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
6,241	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1411469e-05
9,321	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.3556432e-05
4,976	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.7882361e-05
8,899	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	4.427232e-05
5,493	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4771449e-05