Database Paper Browser

Back to papers

Histogram-Based Approximation of Set-Valued Query Answers

Summary: Extends approximate query answering to queries with histograms; introduces a multiset-aware error measure and histogram algebra. MaxDiff histograms yield approximations for set-valued and aggregate queries, while sampling is competitive mainly for aggregates without joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8558
Venue
VLDB
Year
1999
Pagerank
0.00025775749
Overall Rank
361 | 97.50%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072723062
118 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00045685662
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
388 Graph Summarization with Bounded Error 2008 SIGMOD 0.00024662272
405 Approximate Query Processing Using Wavelets 2000 VLDB 0.00024057494
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021380733
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,101 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00014070632
1,260 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012993347
1,717 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010793312
2,011 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.7964875e-05
2,808 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0870741e-05
3,419 Approximate XML Query Answers 2004 SIGMOD 7.1173416e-05
4,014 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.5273084e-05
4,546 Bounded Conjunctive Queries 2014 VLDB 6.0987778e-05
4,681 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.0034918e-05
5,579 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4245689e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
6,829 Depth Estimation for Ranking Query Optimization 2007 VLDB 4.9136064e-05
7,085 Querying Big Data by Accessing Small Data 2015 PODS 4.8388174e-05
7,136 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 4.8220711e-05
8,102 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 4.5852446e-05
8,662 Delay Aware Querying with Seaweed 2006 VLDB 4.4722862e-05
8,715 Data Driven Approximation with Bounded Resources 2017 VLDB 4.4619052e-05
9,061 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.4039656e-05
9,950 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 4.2421586e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
11,194 A Step Toward Deep Online Aggregation 2023 SIGMOD 4.1945683e-05
11,897 Capturing the Laws of (Data) Nature 2015 CIDR 4.1945683e-05
12,469 A Cost-Estimation Component for Statement Sequences 2007 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
14 Online Aggregation 1997 SIGMOD 0.0010801504
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
252 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030632263
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
3,630 A Semantics for Complex Objects and Approximate Queries 1988 PODS 6.9016174e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
1,874 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD 0.00010244443
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
996 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014741524
2,808 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0870741e-05
2,580 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.5058814e-05
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8163484e-05