Interpolation-Based Index Maintenance

Summary: Interpolation-based order-preserving hashing for online maintenance of dynamic external files supporting insert/update/delete and orthogonal range queries. Adapts linear hashing to eliminate index/address-directory, uses O(n) space, tunable storage, and achieves very small average search lengths (successful <<2, unsuccessful <<4). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 648
Venue: PODS
Year: 1983
Pagerank: 0.00030498284
Overall Rank: 255 | 98.23%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Walter A. Burkhard

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705
503	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.00021520176
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938
1,008	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014666726
3,903	Dynamic And Order Preserving Data Partitioning For Database Machines	1985	VLDB	6.6432116e-05
4,490	A Multidimensional Digital Hashing Scheme for Files With Composite Keys	1985	SIGMOD	6.1424256e-05
4,952	A Multikey Hashing Scheme Using Predicate Trees	1984	SIGMOD	5.8091931e-05
5,146	The Interpolation-Based Grid File	1985	PODS	5.6644798e-05
6,323	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.1114874e-05
6,571	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0061936e-05
8,060	A Dynamic Hash File for Random and Sequential Accessing	1983	VLDB	4.5943696e-05
12,997	Order Preserving Linear Hashing Using Dynamic Key Statistics	1986	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,043	A Dynamic Perfect Hash Function Defined By An Extended Hash Indicator Table	1984	VLDB	4.1945683e-05
12,997	Order Preserving Linear Hashing Using Dynamic Key Statistics	1986	PODS	4.1945683e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
4,086	External Perfect Hashing	1985	SIGMOD	6.4608969e-05
4,490	A Multidimensional Digital Hashing Scheme for Files With Composite Keys	1985	SIGMOD	6.1424256e-05
4,286	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.2898839e-05
1,708	A Single-File Version Of Linear Hashing With Partial Expansions	1982	VLDB	0.00010815668
5,363	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	5.5471634e-05
6,323	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.1114874e-05
5,146	The Interpolation-Based Grid File	1985	PODS	5.6644798e-05