Database Paper Browser

Back to papers

Bloom Histogram: Path Selectivity Estimation for XML Data with Updates

Summary: Proposes Bloom Histogram, a compact path frequency estimator under tight space, enabling accurate path selectivity for dynamic data. Coupled with a dynamic summary layer for updates, it outperforms static and dynamic prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9219
Venue
VLDB
Year
2004
Pagerank
5.4014372e-05
Overall Rank
5,632 | 60.83%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
2,665 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.3498101e-05
3,511 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.0254052e-05
6,874 ROX: Run-time Optimization of XQueries 2009 SIGMOD 4.8978984e-05
7,742 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.6628263e-05
11,821 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
268 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00029662304
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021380733
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
781 Spectral Bloom Filters 2003 SIGMOD 0.00016741046
852 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015941524
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307
2,010 StatiX: Making XML Count 2002 SIGMOD 9.7970026e-05
2,137 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB 9.4719326e-05
2,316 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0419716e-05
3,113 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5469926e-05
4,660 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.014625e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
6,224 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.1495715e-05
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
7,302 Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods 2005 VLDB 4.7687064e-05
2,855 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.0059865e-05
3,113 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5469926e-05
7,742 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.6628263e-05
2,316 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0419716e-05
4,660 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.014625e-05
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307