Multiattribute hashing using Gray codes

ABSTRACT

Multiattribute hashing and its variations have been proposed for partial match and range queries in the past. The main idea is that each record yields a bitstring @@@@ (“record signature”), according to the values of its attributes. The binary value (@@@@)2 of this string decides the bucket that the record is stored. In this paper we propose to use Gray codes instead of binary codes, in order to map record signatures to buckets. In Gray codes, successive codewords differ in the value of exactly one bit position, thus, successive buckets hold records with similar record signatures. The proposed method achieves better clustering of similar records and avoids some of the (expensive) random disk accesses, replacing them with sequential ones. We develop a mathematical model, derive formulas giving the average performance of both methods and show that the proposed method achieves 0% - 50% relative savings over the binary codes. We also discuss how Gray codes could be applied to some retrieval methods designed for range queries, such as the grid file [Nievergelt84a] and the approach based on the so-called z-ordering [Orenstein84a].

REFERENCES

• Aho79a: Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
• Bentley75a: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• Cardenas75a: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• Fagin79a: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• Faloutsos85a: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• Gilbert58a: Gtlbert, E N, "Gray Codes and Paths on the n- Cube," Bell System Techn,cal Journal, vol 37, no 3, pp 815-826, May 1958
• Gray53a: Gray, F, Pulse Code Commumcatsons, US Patent 2632058, March 17, 1953
• Larson78a: Larson, P, "Dynamm Hashing," BIT, vol 18, pp 184-201, 1978
• Larson82a: Per-Åke Larson, Performance analysis of linear hashing with partial expansions, ACM Transactions on Database Systems (TODS), v.7 n.4, p.566-587, Dec. 1982 [doi>10.1145/319758.319763]
• Litwin80a: Lltwm, W, "Linear Hashing A new Tool for File and Table Addressing," Proc 6th Interaatsonal Conference on VLDB, pp 212-223, Montreal, Oct 1980
• Lloyd80a: Lloyd, J W, "Optimal Partial-Match Retrieval," BIT, vol 20, pp 406-413, 1980
• Lloyd82a: Lloyd, J W and K Ramamohanarao, "Partial- Match Retrieval for Dynamm Files," BIT, vol 22, pp 150-168, 1982
• Martin79a: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
• Nievergelt84a: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• Orenstein84a: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• Ramamohanarao83a: K. Ramamohanarao , James A. Thom , John W. Lloyd, Partial-match retrieval using hashing and descriptors, ACM Transactions on Database Systems (TODS), v.8 n.4, p.552-576, Dec. 1983 [doi>10.1145/319996.320006]
• Reingold77a: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• Rivest76a: Rlvest, R L, "Partial Match Retrieval Algorithms," SIAM J Compet, vol 5, no 1, pp 19-50, March 1976
• Robinson81a: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• Rothnie74a: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]

INDEX TERMS

Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Performance, Theory