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: 6849
Venue: SIGMOD
Year: 2024
Pagerank: 4.241573e-05
Overall Rank: 9,940 | 30.92%
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,379	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	4.1905499e-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,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
2,178	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.3645765e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,504	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.629969e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
5,503	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4718854e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
6,640	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	4.9753538e-05
6,822	Computing Join Queries with Functional Dependencies	2016	PODS	4.9101655e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
7,106	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8250163e-05
10,714	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1905499e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
6,240	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1362097e-05
9,326	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	4.351469e-05
4,953	Efficient Top-K SimRank-based Similarity Join	2015	VLDB	5.8060034e-05
8,899	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	4.4229886e-05
5,503	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4718854e-05