Index Maintenance for Non-Uniform Record Distributions

Summary: Revisits external-memory file maintenance under non-uniform (skewed) key distributions, showing the common uniform-key analyses mispredict performance and space utilization for inserts/deletes/updates and range queries. Analyzes directory (O(log n)) and address-calculation/interpolation schemes (e.g., grid file, extendible hashing) and advocates incremental restructuring to bound disk I/Os and restore O(1)-amortized updates and O(r)/O(r+log n) range-query costs despite skew. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 695
Venue: PODS
Year: 1984
Pagerank: 5.862009e-05
Overall Rank: 6,497 | 55.43%
DOI: 10.1145/588011.588036

Incoming Non-self Citations Over Time

Authors

1. Walter A. Burkhard (University of California San Diego)

BibTeX Citation

@inproceedings{burkhard_pods84,
        address = {New York, NY, USA},
        series = {{PODS} '84},
        title = {{Index Maintenance for Non-Uniform Record Distributions}},
        url = {https://dl.acm.org/doi/10.1145/588011.588036},
        doi = {10.1145/588011.588036},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Burkhard, Walter A.},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,357	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.7463723e-05
5,377	The Interpolation-Based Grid File	1985	PODS	6.2410452e-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
507	Interpolation-Based Index Maintenance	1983	PODS	0.00017277375

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
2	8,214	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
3	1,512	On the Analysis of Indexing Schemes	1997	PODS
4	4,357	Balanced Multidimensional Extendible Hash Tree	1986	PODS
5	5,377	The Interpolation-Based Grid File	1985	PODS
6	2,961	Distribution-Dependent Hashing Functions and Their Characteristics	1975	SIGMOD
7	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
8	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
9	5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
10	507	Interpolation-Based Index Maintenance	1983	PODS