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.0001806593
Overall Rank
450 | 96.99%
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.00051942573
115 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00031623329
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
563 Graph Summarization with Bounded Error 2008 SIGMOD 0.00016294243
844 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013498392
935 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012968914
1,044 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.0001232071
1,439 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010641857
1,668 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9190265e-05
2,661 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1414177e-05
3,263 Approximate XML Query Answers 2004 SIGMOD 7.4679565e-05
4,000 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.8489751e-05
4,473 Bounded Conjunctive Queries 2014 VLDB 6.570529e-05
5,049 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.287033e-05
5,636 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0385837e-05
5,800 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9735022e-05
6,964 Querying Big Data by Accessing Small Data 2015 PODS 5.617412e-05
7,266 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.55407e-05
7,342 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5329816e-05
8,315 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 5.341013e-05
8,870 Data Driven Approximation with Bounded Resources 2017 VLDB 5.246202e-05
9,140 Delay Aware Querying with Seaweed 2006 VLDB 5.2082006e-05
9,422 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1672232e-05
9,608 A Step Toward Deep Online Aggregation 2023 SIGMOD 5.1376962e-05
10,346 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0197268e-05
11,353 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9605343e-05
12,438 Capturing the Laws of (Data) Nature 2015 CIDR 4.9605343e-05
13,001 A Cost-Estimation Component for Statement Sequences 2007 VLDB 4.9605343e-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.00076079812
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047770864
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023327437
4,603 A Semantics for Complex Objects and Approximate Queries 1988 PODS 6.493817e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 285 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,435 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 277 Optimal Histograms with Quality Guarantees 1998 VLDB
7 868 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
8 2,661 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD
9 2,014 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD
10 7,584 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS