DBScholar

Back to papers

An Incremental Algorithm for Computing Ranked Full Disjunctions

Summary: Introduces IncrementalFD, an incremental algorithm for computing full disjunctions that reduces total runtime and offers lower cost for retrieving only k tuples (for any constant k). For a natural class of ranking functions it emits tuples in ranking order and supports block-based execution. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h3d2c0e180503a9cd
Venue
PODS
Year
2005
Pagerank
5.3711847e-05
Overall Rank
8,234 | 44.64%
DOI
10.1145/1065167.1065180

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cohen_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{An Incremental Algorithm for Computing Ranked Full Disjunctions}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065180},
        doi = {10.1145/1065167.1065180},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Sara and Sagiv, Yehoshua},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
3,132 Matching Twigs in Probabilistic XML 2007 VLDB 7.6137556e-05
4,159 Integrating Data Lake Tables 2023 VLDB 6.7717519e-05
4,262 Maximally Joining Probabilistic Data 2007 PODS 6.6984258e-05
6,499 Full Disjunctions: Polynomial-Delay Iterators in Action 2006 VLDB 5.7650247e-05
8,183 On the Complexity of Package Recommendation Problems 2012 PODS 5.3817332e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017101297
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016909926
794 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00013941847
1,198 Outerjoins as Disjunctions 1994 SIGMOD 0.00011565328
1,773 Rank-aware Query Optimization 2004 SIGMOD 9.6719067e-05
2,853 Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract) 1996 PODS 7.9412355e-05
9,789 Computing Full Disjunctions 2003 PODS 5.1265605e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,467 Output-sensitive Conjunctive Query Evaluation 2024 PODS
2 6,545 Ranked Enumeration of Join Queries with Projections 2022 VLDB
3 2,614 Evaluating Rank Joins with Optimal Cost 2008 PODS
4 12,677 Efficient Rank Join with Aggregation Constraints 2011 VLDB
5 8,015 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
6 9,789 Computing Full Disjunctions 2003 PODS
7 2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
8 5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB
9 507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB
10 6,499 Full Disjunctions: Polynomial-Delay Iterators in Action 2006 VLDB