On B-tree Indices for Skewed Distributions

Summary: Geometric growth for postings in B-tree indices under skewed distributions. Achieves 1-disk-access searches and uses 55–66% of the space of fixed-length postings lists, outperforming straightforward approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8275
Venue: VLDB
Year: 1992
Pagerank: 0.00012377809
Overall Rank: 1,059 | 92.74%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. H. V. Jagadish (AT&T)

BibTeX Citation

@article{faloutsos_vldb92,
        title = {{On B-tree Indices for Skewed Distributions}},
        author = {Faloutsos, Christos and Jagadish, H. V.},
        journal = {PVLDB},
        series = {{VLDB} '92},
        pages = {363},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
1,407	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB	0.00010856546
1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	9.3486136e-05
2,222	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.9255716e-05
2,574	The Rufus System: Information Organization for Semi-Structured Data	1993	VLDB	8.3995947e-05
4,222	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.8227421e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
6,053	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.9939282e-05
6,479	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.8671916e-05
7,071	The TEXTURE Benchmark: Measuring Performance of Text Queries on a Relational DBMS	2005	VLDB	5.711485e-05
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05
12,695	Trustworthy Keyword Search for Regulatory-Compliant Records Retention	2006	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
2	6,246	Compact B-Trees	1979	SIGMOD
3	1,492	BF-Tree: Approximate Tree Indexing	2014	VLDB
4	5,120	Multi-Disk B-trees	1991	SIGMOD
5	9,518	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
6	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
7	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
8	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
9	8,016	Two is Better Than One: The Case for 2-Tree for Skewed Data Sets	2023	CIDR
10	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD