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
8749
Venue
VLDB
Year
1999
Pagerank
0.000185063
Overall Rank
435 | 97.02%
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.00052982574
114 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00032363776
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
307 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021792475
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
365 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00020041735
548 Graph Summarization with Bounded Error 2008 SIGMOD 0.00016694936
817 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013823702
909 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013291205
1,028 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012557617
1,397 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010906135
1,634 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 0.00010163938
2,608 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.347674e-05
3,180 Approximate XML Query Answers 2004 SIGMOD 7.6599179e-05
3,945 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 7.0055154e-05
4,393 Bounded Conjunctive Queries 2014 VLDB 6.7280426e-05
4,926 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.4428362e-05
5,490 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.200262e-05
5,650 Extended Wavelets for Multiple Measures 2003 SIGMOD 6.1337629e-05
6,841 Querying Big Data by Accessing Small Data 2015 PODS 5.7574257e-05
7,123 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.6966694e-05
7,177 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.6806091e-05
8,121 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 5.4834308e-05
8,701 Data Driven Approximation with Bounded Resources 2017 VLDB 5.3828806e-05
8,953 Delay Aware Querying with Seaweed 2006 VLDB 5.3458888e-05
9,209 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.3058708e-05
9,392 A Step Toward Deep Online Aggregation 2023 SIGMOD 5.2755515e-05
10,094 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.1530576e-05
10,891 Cardinality Estimation for Having-Clauses 2025 VLDB 5.093636e-05
12,096 Capturing the Laws of (Data) Nature 2015 CIDR 5.093636e-05
12,663 A Cost-Estimation Component for Statement Sequences 2007 VLDB 5.093636e-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.00077458002
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00048351457
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
149 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00029226907
222 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00024193708
235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023783792
4,491 A Semantics for Complex Objects and Approximate Queries 1988 PODS 6.6652483e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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