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
8559
Venue
VLDB
Year
1999
Pagerank
0.00025768448
Overall Rank
360 | 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.00072660894
119 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00045724707
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
387 Graph Summarization with Bounded Error 2008 SIGMOD 0.00024682268
416 Approximate Query Processing Using Wavelets 2000 VLDB 0.00023773968
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021385343
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,100 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00014062265
1,257 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013002384
1,712 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010786152
2,005 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.8168893e-05
2,813 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0816314e-05
3,421 Approximate XML Query Answers 2004 SIGMOD 7.1107127e-05
4,022 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.5185189e-05
4,545 Bounded Conjunctive Queries 2014 VLDB 6.0917464e-05
4,679 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 5.9978792e-05
5,588 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4193309e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
6,826 Depth Estimation for Ranking Query Optimization 2007 VLDB 4.9090969e-05
7,061 Querying Big Data by Accessing Small Data 2015 PODS 4.8400281e-05
7,134 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 4.8174665e-05
8,108 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 4.5808537e-05
8,659 Delay Aware Querying with Seaweed 2006 VLDB 4.4682399e-05
8,712 Data Driven Approximation with Bounded Resources 2017 VLDB 4.4578168e-05
9,059 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.3997447e-05
9,946 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 4.240067e-05
10,647 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1905499e-05
11,196 A Step Toward Deep Online Aggregation 2023 SIGMOD 4.1905499e-05
11,905 Capturing the Laws of (Data) Nature 2015 CIDR 4.1905499e-05
12,478 A Cost-Estimation Component for Statement Sequences 2007 VLDB 4.1905499e-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.0010813443
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
250 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030640525
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
3,631 A Semantics for Complex Objects and Approximate Queries 1988 PODS 6.8976535e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
1,867 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD 0.00010264932
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
995 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014745185
2,813 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0816314e-05
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8128138e-05
2,583 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.4973431e-05