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,926 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8184457e-05 |
| 5,963 | Beyond Equi-joins: Ranking, Enumeration and Factorization | 2021 | VLDB | 5.2485815e-05 |
| 7,145 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8139975e-05 |
| 8,029 | Tight Fine-Grained Bounds for Direct Access on Join Queries | 2022 | PODS | 4.598451e-05 |
| 8,065 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5899218e-05 |
| 9,743 | Output-Sensitive Evaluation of Regular Path Queries | 2025 | PODS | 4.2856385e-05 |
| 10,002 | Clustering with Set Outliers and Applications in Relational Clustering | 2026 | PODS | 4.1905499e-05 |
| 10,928 | Improved Approximation Algorithms for Relational Clustering | 2024 | PODS | 4.1905499e-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,322 | Hypertree Decompositions: Questions and Answers | 2016 | PODS | 0.00012595941 |
| 2,864 | A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies | 2012 | PODS | 7.9964194e-05 |
| 3,386 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.151562e-05 |
| 3,702 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 6.8251643e-05 |
| 4,358 | The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries | 2016 | VLDB | 6.2499e-05 |
| 5,845 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 5.3057391e-05 |
| 6,167 | Approximate Lifted Inference with Probabilistic Databases | 2015 | VLDB | 5.1725053e-05 |
Previous
Page 1 / 1
Next