Interpolation-based index maintenance
Walter A. Burkhard · ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS) · 1983
A new interpolation-based order preserving hashing algorithm suitable for on-line maintenance of large dynamic external files under sequences of four kinds of operations insertion, update, deletion, and orthogonal range query is proposed. The scheme, an adaptation of linear hashing, requires no index or address directory structure and utilizes O(n) space for files containing n records, all of the benefits of linear hashing are inherited by this new scheme. File implementations yielding average successful search lengths much less than 2 and average unsuccessful search lengths much less than 4 for individual records are obtainable, the actual storage required is controllable by the implementor.
Cited by 46 works. doi:10.1145/588058.588070
Authors
References
- Multidimensional binary search trees used for associative searching
- Organization and maintenance of large ordered indexes
- The K-D-B-tree
- Extendible hashing—a fast access method for dynamic files
- Partial-Match Retrieval Algorithms
- A class of data structures for associative searching
- Expected Length of the Longest Probe Sequence in Hash Code Searching
- Virtual hashing: a dynamically changing hashing
- Linear hashing with partial expansions
- The grid file: An adaptable, symmetric multi-key file structure