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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,286 | Balanced Multidimensional Extendible Hash Tree | 1986 | PODS | 6.2898839e-05 |
| 5,146 | The Interpolation-Based Grid File | 1985 | PODS | 5.6644798e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 255 | Interpolation-Based Index Maintenance | 1983 | PODS | 0.00030498284 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8126082e-05 |
| 8,811 | Tuning Hierarchical Learned Indexes on Disk and Beyond | 2022 | SIGMOD | 4.4441574e-05 |
| 1,488 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011699446 |
| 4,286 | Balanced Multidimensional Extendible Hash Tree | 1986 | PODS | 6.2898839e-05 |
| 5,146 | The Interpolation-Based Grid File | 1985 | PODS | 5.6644798e-05 |
| 948 | Distribution-Dependent Hashing Functions and Their Characteristics | 1975 | SIGMOD | 0.00015112484 |
| 8,767 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.456315e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 5,363 | A Mapping Function for the Directory of a Multidimensional Extendible Hashing | 1984 | VLDB | 5.5471634e-05 |
| 255 | Interpolation-Based Index Maintenance | 1983 | PODS | 0.00030498284 |