Abstract | ||
---|---|---|
Hashing is a well-known technique for organizing direct access files. Extendible hashing removes the restriction on the expansion of the file and thus allows dynamic files. We generalize the technique to store multi-attribute keys. Exact-match queries (searching) can be done in constant time usingn-dimensional hashing. Ann-dimensional partial-match queries givenk attributes can be answered inO(N**((n -k)/n)) time whereN is the number of records stored. It is shown thatn-dimensional hashing is a special case of one-dimensional hashing, thus the storage utilization of the buckets is independent ofn. Simulation results are presented to show the advantages of multidimensional hashing. |
Year | DOI | Venue |
---|---|---|
1985 | 10.1007/BF00996923 | International Journal of Parallel Programming |
Keywords | Field | DocType |
hashing,extendible hashing,multidimensional data struc- tures,partial-match queries. | Extendible hashing,Computer science,Universal hashing,Theoretical computer science,Tabulation hashing,Consistent hashing,2-choice hashing,Dynamic perfect hashing,Hash table,Linear hashing | Journal |
Volume | Issue | ISSN |
14 | 2 | 1573-7640 |
Citations | PageRank | References |
2 | 0.36 | 0 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shou-hsuan Stephen Huang | 1 | 174 | 59.88 |