ACM SIGMOD Anthology TKDE dblp.uni-trier.de

Using Tries to Eliminate Pattern Collisions in Perfect Hashing.

Marshall D. Brain, Alan L. Tharp: Using Tries to Eliminate Pattern Collisions in Perfect Hashing. IEEE Trans. Knowl. Data Eng. 6(2): 239-247(1994)
@article{DBLP:journals/tkde/BrainT94,
  author    = {Marshall D. Brain and
               Alan L. Tharp},
  title     = {Using Tries to Eliminate Pattern Collisions in Perfect Hashing},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {6},
  number    = {2},
  year      = {1994},
  pages     = {239-247},
  ee        = {db/journals/tkde/BrainT94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Many current perfect hashing algorithms suffer from the problem of pattern collisions. In this paper, a perfect hashing technique that uses array-based tries and a simple sparse matrix packing algorithm is introduced. This technique eliminates all pattern collisions, and because of this, it can be used to form ordered minimal perfect hash functions on extremely large word lists. This algorithm is superior to other known perfect hashing functions for large word lists in terms of function building efficiency, pattern collision avoidance, and retrieval function complexity. It has been successfully used to form an ordered minimal perfect hashing function for the entire 24, 481 element Unix word list without resorting to segmentation. The item lists addressed by the perfect hashing function formed can be ordered in any manner, including alphabetically, to easily allow other forms of access to the same list.

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[1]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Francine Berman, Mary Ellen Bock, Eric Dittert, Michael J. O'Donnell, Darrell Plank: Collections of Functions for Perfect Hashing. SIAM J. Comput. 15(2): 604-618(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Marshall D. Brain, Alan L. Tharp: Near-perfect Hashing of Large Word Sets. Softw., Pract. Exper. 19(10): 967-978(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Marshall D. Brain, Alan L. Tharp: Perfect hashing using sparse matrix packing. Inf. Syst. 15(3): 281-290(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
Richard J. Cichelli: Minimal Perfect Hash Functions Made Simple. Commun. ACM 23(1): 17-19(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
C. C. Chang: The Study of an Ordered Minimal Perfect Hashing Scheme. Commun. ACM 27(4): 384-387(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
M. W. Du, T. M. Hsieh, K. F. Jea, D. W. Shieh: The Study of a New Perfect Hash Scheme. IEEE Trans. Software Eng. 9(3): 305-313(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Edward A. Fox, Qi Fan Chen, Lenwood S. Heath, S. Datta: A More Cost Effective Algorithm for Finding Perfect Hash Functions. ACM Conference on Computer Science 1989: 114-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Edward A. Fox, Lenwood S. Heath, Qi Fan Chen, Amjad M. Daoud: Practical Minimal Perfect Hash Functions for Large Databases. Commun. ACM 35(1): 105-121(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31(3): 538-544(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Yeong-Shiou Hsiao, Alan L. Tharp: Adaptive hashing. Inf. Syst. 13(1): 111-127(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Gerhard Jaeschke: Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions. Commun. ACM 24(12): 829-833(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
...
[17-1]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley 1968
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17-2]
Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms. Addison-Wesley 1969
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17-3]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Per-Åke Larson, M. V. Ramakrishna: External Perfect Hashing. SIGMOD Conference 1985: 190-200 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Ted G. Lewis, Curtis R. Cook: Hashing for Dynamic and Static Internal Tables. IEEE Computer 21(10): 45-56(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
Thomas J. Sager: A Polynomial Time Generator for Minimal Perfect Hash Functions. Commun. ACM 28(5): 523-532(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Robert Endre Tarjan, Andrew Chi-Chih Yao: Storing a Sparse Table. Commun. ACM 22(11): 606-611(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
...
[26]
Francis A. Williams: Handling Identifiers as Internal Symbols in Language Processors. Commun. ACM 2(6): 21-24(1959) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
...

Referenced by

  1. Paolino Di Felice, Ugo Madama: Reducing the Storage Requirements of a Perfect Hash Function. IEEE Trans. Knowl. Data Eng. 10(6): 1005-1007(1998)

Copyright © Mon Nov 2 21:57:54 2009 by Michael Ley (ley@uni-trier.de)