Title :
New order preserving access methods for very large files derived from linear hashing
Author :
Hachem, Nabil I. ; Berra, P. Bruce
Author_Institution :
Dept. of Comput. Sci., Worcester Polytech. Inst., MA, USA
fDate :
2/1/1992 12:00:00 AM
Abstract :
A class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as the dynamic random-sequential access method (DRSAM) and is derived from linear hashing. A new logical to physical mapping that is based on sequential bucket allocations in hash order is proposed. With respect to previous methods, this allocation technique has the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order preserving (OPH) schemes should result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. Under specific conditions, this approach outperforms the partial expansion method previously proposed by P.-A. Larson (1982)
Keywords :
file organisation; dynamic hashing structures; dynamic random-sequential access method; elastic buckets; file growth; linear hashing; order preserving access methods; partial expansion method; physical mapping; range queries; sequential bucket allocations; sequential processing; very large files; Analytical models; Artificial intelligence; Computer science; Cost function; Knowledge management; Military computing;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on