DBScholar

Back to papers

Minimal Probing: Supporting Expensive Predicates for Top-k Queries

Summary: Necessary-probe principle for top-k queries with expensive predicates (external UDFs, fuzzy similarity) that defy zero-time indexing. MPro is provably optimal, parallelizable, and dramatically reduces probes versus full probing; demonstrated on real-estate and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h6679cdb7e9f13f02
Venue
SIGMOD
Year
2002
Pagerank
0.00013521251
Overall Rank
840 | 94.38%
DOI
10.1145/564691.564731

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chang_sigmod02,
        title = {{Minimal Probing: Supporting Expensive Predicates for Top-k Queries}},
        author = {Chang, Kevin Chen-Chuan and Hwang, Seung-won},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564731},
        url = {https://dl.acm.org/doi/10.1145/564691.564731},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank Citing Paper Year Venue Pagerank
505 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017162373
941 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012938573
947 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.00012910239
1,447 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010604169
1,539 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB 0.00010292787
1,641 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 9.9814769e-05
1,649 Relaxing Join and Selection Queries 2006 VLDB 9.9699016e-05
1,712 Rank-aware Query Optimization 2004 SIGMOD 9.7961248e-05
2,019 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.1666472e-05
2,406 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.4962449e-05
2,566 Answering Top-k Queries Using Views 2006 VLDB 8.2679821e-05
2,777 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0101016e-05
2,880 KLEE: A Framework for Distributed Top-k Query Algorithms 2005 VLDB 7.8948229e-05
3,288 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.4398818e-05
3,623 Best Position Algorithms for Top-k Queries 2007 VLDB 7.1347556e-05
3,793 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 6.9967739e-05
3,819 Querying Structured Text in an XML Database 2003 SIGMOD 6.9825548e-05
4,668 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4622135e-05
5,298 Top-K Structural Diversity Search in Large Networks 2013 VLDB 6.1768321e-05
5,954 RankSQL: Supporting Ranking Queries in Relational Database Management Systems 2005 VLDB 5.9176407e-05
6,544 Moirae: History-Enhanced Monitoring 2007 CIDR 5.7329952e-05
7,348 Anytime Measures for Top-k Algorithms 2007 VLDB 5.5302579e-05
7,413 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD 5.516158e-05
7,521 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 5.4881075e-05
7,981 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 5.3964641e-05
8,213 Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation 2011 VLDB 5.3607592e-05
8,521 Sideway Value Algebra for Object-Relational Databases 2002 VLDB 5.309662e-05
8,841 ARCube: Supporting Ranking Aggregate Queries in Partially Materialized Data Cubes 2008 SIGMOD 5.2511874e-05
8,861 Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases 2010 SIGMOD 5.2477452e-05
12,425 Query Reranking As A Service 2016 VLDB 4.9605343e-05
12,648 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD 4.9605343e-05
12,834 Privacy Preservation of Aggregates in Hidden Databases: Why and How? 2009 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0010688884
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030398363
164 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.00027451323
170 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.0002707332
398 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00019117739
419 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018558415
511 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017061618
647 Evaluating Top-k Selection Queries 1999 VLDB 0.00015165562
687 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014736766
1,162 A Framework for Expressing and Combining Preferences 2000 SIGMOD 0.00011729702
1,569 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010177494
1,866 Optimizing Disjunctive Queries with Expensive Predicates 1994 SIGMOD 9.4590899e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,842 Supporting Hard Queries over Probabilistic Preferences 2020 VLDB
2 1,480 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB
3 7,413 Efficient and Generic Evaluation of Ranked Queries 2011 SIGMOD
4 8,473 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB
5 2,193 Probabilistic Optimization of Top N Queries 1999 VLDB
6 7,521 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD
7 12,671 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB
8 3,578 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD
9 51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB
10 12,648 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD