Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
Summary: Identifies when self-join-free CQs admit quasilinear preprocessing plus O(log n) direct access to the k-th answer: provides a decidable characterization for lexicographic orderings and shows sum-of-weights orders are tractable only in trivial cases. For the selection variant (single-position), gives a quasilinear algorithm for a subclass of full CQs using Frederickson–Johnson selection on sorted matrices and proves matching hardness for the rest. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,953 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8085795e-05 |
| 5,962 | Beyond Equi-joins: Ranking, Enumeration and Factorization | 2021 | VLDB | 5.2536266e-05 |
| 7,195 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8037242e-05 |
| 8,028 | Tight Fine-Grained Bounds for Direct Access on Join Queries | 2022 | PODS | 4.6028646e-05 |
| 8,061 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5943269e-05 |
| 9,744 | Output-Sensitive Evaluation of Regular Path Queries | 2025 | PODS | 4.2897489e-05 |
| 10,003 | Clustering with Set Outliers and Applications in Relational Clustering | 2026 | PODS | 4.1945683e-05 |
| 10,924 | Improved Approximation Algorithms for Relational Clustering | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 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,328 | Hypertree Decompositions: Questions and Answers | 2016 | PODS | 0.00012565612 |
| 2,857 | A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies | 2012 | PODS | 8.0037703e-05 |
| 3,387 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.1573735e-05 |
| 3,715 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 6.8220943e-05 |
| 4,361 | The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries | 2016 | VLDB | 6.2559141e-05 |
| 5,855 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 5.3006096e-05 |
| 6,169 | Approximate Lifted Inference with Probabilistic Databases | 2015 | VLDB | 5.1716068e-05 |
Previous
Page 1 / 1
Next