Optimal Join Algorithms Meet Top-k

Summary: Unifies top-k queries with RAM-based optimal join algorithms, addressing large intermediates and Threshold Algorithm limitations. Surveys intersection of ranked-join enumeration, linking k-shortest path ideas to a unified, efficient top-k framework. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hdbac817c69460ef6
Venue: SIGMOD
Year: 2020
Pagerank: 6.434561e-05
Overall Rank: 4,752 | 68.06%
DOI: 10.1145/3318464.3383132

Incoming Non-self Citations Over Time

Authors

1. Nikolaos Tziavelis (Northeastern University)
2. Wolfgang Gatterbauer (Northeastern University)
3. Mirek Riedewald (Northeastern University)

BibTeX Citation

@inproceedings{tziavelis_sigmod20,
        title = {{Optimal Join Algorithms Meet Top-k}},
        author = {Tziavelis, Nikolaos and Gatterbauer, Wolfgang and Riedewald, Mirek},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3383132},
        url = {https://dl.acm.org/doi/10.1145/3318464.3383132},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
194	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00025636725
4,605	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5047683e-05
4,698	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.4640177e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
8,048	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.4004443e-05
10,832	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9793485e-05
10,984	Into the CUDA Multiverse of Runtime Compilation: Exploring Kernel Fusion Strategies for GPU Database Systems	2026	VLDB	4.9793485e-05
11,033	An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation	2026	VLDB	4.9793485e-05
11,526	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 35 of 35 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.0010679641
111	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032675259
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026835705
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020020639
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
412	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00018694414
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017101297
521	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016929744
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016909926
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015341557
684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00014798237
730	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014406936
818	Hypertree Decompositions: Questions and Answers	2016	PODS	0.0001366708
849	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013504405
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,690	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8609347e-05
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
2,290	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6889284e-05
2,299	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6727773e-05
2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2255837e-05
2,975	In-Database Learning with Sparse Tensors	2018	PODS	7.7907759e-05
3,373	F: Regression Models over Factorized Views	2016	VLDB	7.3661025e-05
5,229	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2196057e-05
5,489	Compressed Representations of Conjunctive Query Results	2018	PODS	6.1095111e-05
6,004	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9166815e-05
6,739	Computing Join Queries with Functional Dependencies	2016	PODS	5.6917027e-05
7,247	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5748328e-05
7,615	Processing Top-k Join Queries	2010	VLDB	5.4834169e-05
7,752	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4595236e-05
8,643	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.2954976e-05
8,801	Geometric Approaches for Top-k Queries	2017	VLDB	5.2735579e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
2	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
3	1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD
4	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
5	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
6	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
7	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
9	2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS
10	7,615	Processing Top-k Join Queries	2010	VLDB