DBScholar

Back to papers

Beyond Equi-joins: Ranking, Enumeration and Factorization

Summary: Ranked theta-join enumeration with inequalities; top-k on acyclic full joins in O(n polylog n + k log k). On-the-fly factorized output representation; memory-efficient, fast; experiments show orders-of-magnitude speedups over state-of-the-art DB systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
12622
Venue
VLDB
Year
2021
Pagerank
6.1552328e-05
Overall Rank
5,593 | 61.63%
DOI
10.14778/3476249.3476306

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{tziavelis_vldb21,
        title = {{Beyond Equi-joins: Ranking, Enumeration and Factorization}},
        author = {Tziavelis, Nikolaos and Gatterbauer, Wolfgang and Riedewald, Mirek},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {11},
        pages = {2599--2612},
        doi = {10.14778/3476249.3476306},
        url = {https://doi.org/10.14778/3476249.3476306},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
4,575 Conjunctive Queries with Comparisons 2022 SIGMOD 6.6223692e-05
6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.8836116e-05
7,286 Efficient Computation of Quantiles over Joins 2023 PODS 5.655242e-05
9,184 Complex Event Recognition meets Hierarchical Conjunctive Queries 2024 PODS 5.3058708e-05
9,235 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.3016261e-05
10,087 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.1558402e-05
10,133 Database Research needs an Abstract Relational Query Language 2026 CIDR 5.093636e-05
10,154 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 36 of 36 cited papers.

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

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
210 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024797689
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
333 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.0002089582
407 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00019021441
414 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018893507
499 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017431827
509 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017220967
536 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.0001693369
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
715 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014655327
814 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013841737
860 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013560445
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
1,123 Path Problems in Temporal Graphs 2014 VLDB 0.00012089975
1,699 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.975915e-05
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,392 FDB: A Query Engine for Factorised Relational Databases 2012 VLDB 8.6404947e-05
2,468 On the Enumeration Complexity of Unions of Conjunctive Queries 2019 PODS 8.5358494e-05
2,525 Answering Top-k Queries Using Views 2006 VLDB 8.4653166e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
2,831 Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities 2009 SIGMOD 8.0788784e-05
2,927 In-Database Learning with Sparse Tensors 2018 PODS 7.9531195e-05
3,334 F: Regression Models over Factorized Views 2016 VLDB 7.5110164e-05
4,268 Joining Interval Data in Relational Databases 2004 SIGMOD 6.7925685e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,138 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.3495536e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
6,596 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 5.828647e-05
7,550 Processing Top-k Join Queries 2010 VLDB 5.6011318e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-05
8,024 Progressive Join Algorithms Considering User Preference 2021 CIDR 5.5052493e-05
8,673 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.3872753e-05
11,757 Factorized Graph Representations for Semi-Supervised Learning from Sparse Data 2020 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,854 Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis 2023 PODS
2 10,154 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS
3 6,678 Output-sensitive Conjunctive Query Evaluation 2024 PODS
4 12,386 Efficient Rank Join with Aggregation Constraints 2011 VLDB
5 499 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB
6 2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS
7 7,286 Efficient Computation of Quantiles over Joins 2023 PODS
8 10,622 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB
9 2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
10 6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB