DBScholar

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
hc3eb4443fc5f1b1c
Venue
VLDB
Year
1999
Pagerank
0.00018121533
Overall Rank
448 | 97.00%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ioannidis_vldb99,
        title = {{Histogram-Based Approximation of Set-Valued Query Answers}},
        author = {Ioannidis, Yannis E. and Poosala, Viswanath},
        journal = {PVLDB},
        series = {{VLDB} '99},
        pages = {174--185},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
115 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00031727517
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021376597
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019822444
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
563 Graph Summarization with Bounded Error 2008 SIGMOD 0.00016319495
843 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013534623
930 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013009255
1,041 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012354465
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010676907
1,662 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9502569e-05
2,654 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1670397e-05
3,248 Approximate XML Query Answers 2004 SIGMOD 7.4912478e-05
3,988 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.8694751e-05
4,452 Bounded Conjunctive Queries 2014 VLDB 6.5918046e-05
5,025 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3078009e-05
5,623 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0586084e-05
5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9933192e-05
6,948 Querying Big Data by Accessing Small Data 2015 PODS 5.6350267e-05
7,249 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.5722715e-05
7,324 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5512232e-05
8,301 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 5.3587028e-05
8,851 Data Driven Approximation with Bounded Resources 2017 VLDB 5.2634608e-05
9,121 Delay Aware Querying with Seaweed 2006 VLDB 5.2253958e-05
9,396 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1843659e-05
9,583 A Step Toward Deep Online Aggregation 2023 SIGMOD 5.154741e-05
10,318 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0363234e-05
11,298 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9769913e-05
12,395 Capturing the Laws of (Data) Nature 2015 CIDR 4.9769913e-05
12,959 A Cost-Estimation Component for Statement Sequences 2007 VLDB 4.9769913e-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
9 Online Aggregation 1997 SIGMOD 0.00076265429
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047864281
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
4,586 A Semantics for Complex Objects and Approximate Queries 1988 PODS 6.5150868e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 284 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
2 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD
3 1,428 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD
4 518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD
5 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
6 275 Optimal Histograms with Quality Guarantees 1998 VLDB
7 867 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
8 2,654 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD
9 2,003 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD
10 7,574 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS