Multidimensional extendible hashing for partial-match queries |
| |
Authors: | Shou-Hsuan Stephen Huang |
| |
Affiliation: | (1) Department of Computer Science, University of Houston, 77004 Houston, Texas |
| |
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.This research was partially supported by a Research Initiation Grant from the University of Houston. |
| |
Keywords: | Hashing extendible hashing multidimensional data structures partial-match queries |
本文献已被 SpringerLink 等数据库收录! |