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.00030506096
Overall Rank: 254 | 98.24%
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
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621
501	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.00021529047
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
1,009	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014658958
3,908	Dynamic And Order Preserving Data Partitioning For Database Machines	1985	VLDB	6.6380291e-05
4,493	A Multidimensional Digital Hashing Scheme for Files With Composite Keys	1985	SIGMOD	6.1371575e-05
4,957	A Multikey Hashing Scheme Using Predicate Trees	1984	SIGMOD	5.8036922e-05
5,145	The Interpolation-Based Grid File	1985	PODS	5.6596839e-05
6,324	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.1067137e-05
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05
8,064	A Dynamic Hash File for Random and Sequential Accessing	1983	VLDB	4.5900019e-05
13,008	Order Preserving Linear Hashing Using Dynamic Key Statistics	1986	PODS	4.1905499e-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.0018380955
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,054	A Dynamic Perfect Hash Function Defined By An Extended Hash Indicator Table	1984	VLDB	4.1905499e-05
13,008	Order Preserving Linear Hashing Using Dynamic Key Statistics	1986	PODS	4.1905499e-05
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
4,090	External Perfect Hashing	1985	SIGMOD	6.454673e-05
4,493	A Multidimensional Digital Hashing Scheme for Files With Composite Keys	1985	SIGMOD	6.1371575e-05
4,279	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.2850695e-05
1,708	A Single-File Version Of Linear Hashing With Partial Expansions	1982	VLDB	0.00010802316
5,372	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	5.5424242e-05
6,324	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.1067137e-05
5,145	The Interpolation-Based Grid File	1985	PODS	5.6596839e-05