High Storage Utilisation for Single-Probe Retrieval Linear Hashing

Open Access
Publisher Website
Google Scholar
Abstract
Many information systems require expandable files. Linear hashing is a well-known technique for growing a file without requiring a complete reinsertion of the data. With the advantage of expandability comes greater retrieval costs as compared to static file methods. A recent modification of linear hashing, Linear Hashing with Separators (LHS), requires only a single access of auxiliary memory. However, this method too has limitations. It introduces secondary clustering which increases insertion costs and it has lower storage utilisation than might be desirable. After surveying linear hashing and LHS, this paper introduces an algorithm called High Storage Utilisation for Single-Probe Retrieval (HSUSPR is read SOO-SPRAH). HSUSPR linear hashing maintains the single probe retrieval of LHS but with lower insertion costs and greater auxiliary storage utilisation. To achieve these benefits HSUSPR does use more primary memory for storing index information. Extensive experimental results are given comparing HSUSPR with LHS. Experimental results also are provided which indicate that the performance of HSUSPR is independent of the distribution of the key data. HSUSPR is particularly useful for information systems with many insertions and/or those systems involving real-time updates.

This publication has 0 references indexed in Scilit: