DBScholar

Back to papers

Topology Dependent Bounds For FAQs

Summary: Topology-aware round-complexity bounds for FAQs in the Chattopadhyay synchronous private-link model, focusing on Boolean conjunctive queries and PGM marginals. Tight bounds for O(1)-degenerate, O(1)-arity hypergraphs via a new GHD "internal-node-width", plus matrix-chain×vector lower bounds via a min-entropy argument. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1780
Venue
PODS
Year
2019
Pagerank
6.0411129e-05
Overall Rank
5,923 | 59.37%
DOI
10.1145/3294052.3319686

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{langberg_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Topology Dependent Bounds For FAQs}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319686},
        doi = {10.1145/3294052.3319686},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Langberg, Michael and Li, Shi and Jayaraman, Sai Vikneshwar Mani and Rudra, Atri},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
11,132 Topology-aware Parallel Joins 2024 PODS 5.093636e-05
11,338 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 5.093636e-05
11,634 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 5.093636e-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
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
765 Query Processing for Sensor Networks 2003 CIDR 0.00014217472
814 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013841737
860 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013560445
1,207 Communication Steps for Parallel Query Processing 2013 PODS 0.00011663155
1,448 Skew in Parallel Query Processing 2014 PODS 0.00010758872
2,678 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS 8.2680182e-05
Previous Page 1 / 1 Next

Semantically Similar Papers