DBScholar

Back to papers

Top-k Query Evaluation with Probabilistic Guarantees

Summary: Proposes approximate top-k algorithms using probabilistic bounds to prune candidates during index-list scans, reducing reliance on Fagin’s TA. Convolution-based bounds yield high-probability guarantees for early dropping, with experiments on Web and structured data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h0192d3cf68050cd5
Venue
VLDB
Year
2004
Pagerank
0.00010326646
Overall Rank
1,535 | 89.69%
DOI
10.1016/B978-012088469-8.50058-9

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{theobald_vldb04,
        title = {{Top-k Query Evaluation with Probabilistic Guarantees}},
        author = {Theobald, Martin and Weikum, Gerhard and Schenkel, Ralf},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {648--659},
        doi = {10.1016/B978-012088469-8.50058-9},
        url = {https://doi.org/10.1016/B978-012088469-8.50058-9},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
1,441 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010638056
1,759 Structured Querying of Web Text: A Technical Challenge 2007 CIDR 9.7090189e-05
2,008 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.1956849e-05
2,397 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.5238625e-05
2,644 The SphereSearch Engine for Unified Ranked Retrieval of Heterogeneous XML and Web Documents 2005 VLDB 8.1738056e-05
2,874 KLEE: A Framework for Distributed Top-k Query Algorithms 2005 VLDB 7.9186028e-05
3,277 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.4642865e-05
3,380 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.353368e-05
5,905 On Efficient Approximate Queries over Machine Learning Models 2023 VLDB 5.9504628e-05
6,210 MINERVA: Collaborative P2P Search 2005 VLDB 5.8479648e-05
6,302 Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies 2008 SIGMOD 5.8163342e-05
6,974 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD 5.6277375e-05
7,102 DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation 2022 VLDB 5.5991152e-05
7,329 Anytime Measures for Top-k Algorithms 2007 VLDB 5.5485926e-05
7,432 Efficient and Flexible Information Retrieval Using MonetDB/X100 2007 CIDR 5.5277182e-05
7,621 Processing Top-k Join Queries 2010 VLDB 5.4808989e-05
9,298 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.1997281e-05
11,186 Approximating Opaque Top-k Queries 2025 SIGMOD 4.9769913e-05
12,456 Leveraging Graph Dimensions in Online Graph Search 2015 VLDB 4.9769913e-05
12,683 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.9769913e-05
12,759 An Access Cost-Aware Approach for Object Retrieval over Multiple Sources 2010 VLDB 4.9769913e-05
12,790 Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval 2009 SIGMOD 4.9769913e-05
12,837 Robust and Distributed Top-N Frequent-Pattern Mining With SAP BW Accelerator 2009 VLDB 4.9769913e-05
12,945 The TopX DB&IR Engine 2007 SIGMOD 4.9769913e-05
13,052 Database-Inspired Search 2005 VLDB 4.9769913e-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.0010679903
111 Optimizing Multi-Feature Queries for Image Databases 2000 VLDB 0.00032668973
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017665834
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017093562
840 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00013544367
2,183 Probabilistic Optimization of Top N Queries 1999 VLDB 8.9044171e-05
3,006 Optimized Query Execution in Large Search Engines with Global Page Ordering 2003 VLDB 7.7598321e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
2 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB
3 7,964 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB
4 3,107 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD
5 11,186 Approximating Opaque Top-k Queries 2025 SIGMOD
6 7,396 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD
7 12,605 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
8 8,458 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB
9 1,397 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD
10 7,329 Anytime Measures for Top-k Algorithms 2007 VLDB