Browse Prior Art Database

Time for Space Tradeoff for External Hashing Schemes

IP.com Disclosure Number: IPCOM000087229D
Original Publication Date: 1976-Dec-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Rosenberg, AL: AUTHOR

Abstract

Disclosed herein is a technique for obtaining multiplicative savings in storage at the cost of additive loss in speed of access when designing external hashing schemes.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 2

Time for Space Tradeoff for External Hashing Schemes

Disclosed herein is a technique for obtaining multiplicative savings in storage at the cost of additive loss in speed of access when designing external hashing schemes.

In informal terms, an external hashing scheme works as follows. One has a set K of keys to be stored. To this end, one devises a hash function HASH: K --> {1,2,3,...}. Associated with each hash address HASH(k) is a bucket, in reality a balanced search tree, that is constructed as needed to store all synonyms of item k, that is, items with the same hash address. An access in such an external hashing scheme comprises a single evaluation of the function HASH to determine which bucket the sought item resides in, followed by an indeterminate number of probes into that bucket-tree to find the sought item among its synonyms. External hashing schemes are described in more detail in [1,2].

Central to the disclosed technique is the notion of a compacting function. Definition: The function C:Reals --> Reals is a compacting function if it satisfies the following conditions: (1) C(1) >/- 1;,

(2) C(x) is nondecreasing for positive x;,

(3) The function F(x) = x/C(x) is eventually

increasing for positive x and satisfies: There is a positive integer n such that for all sufficiently large positive x, F(x+nùC(x)) >/- F(x)+1.

Examples: (a) For any positive integer n, the constant function C(x) <eth> n is a compacting function.

(b) For every positive integer n, the function

C(x) = (log Cx+1))/...