A More Cost Effective Algorithm for Finding Perfect Hash Functions

Simple item page
dc.contributor.authorFox, Edward A.en
dc.contributor.authorChen, Qi-Fanen
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorDatta, Sanjeeven
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:35Zen
dc.date.available2013-06-19T14:36:35Zen
dc.date.issued1988-09-01en
dc.description.abstractAs the use of knowledge-based systems increases, there will be a growing need for efficient artificial intelligence systems and methods to access large lexicons. In the Composite Document Expert/extended/effective Retrieval (CODER) system we have, in order to provide rapid access to data items on CD-ROM's and to terms in a lexicon built from machine readable dictionaries, investigated the construction of perfect hashing functions. We have considered algorithms reported earlier in the literature, have made numerous enhancements to them, have developed new algorithms, and here report on some of our results. This paper covers an $O(n^3)$ algorithm that has been applied to building hashing functions for a collection of 69806 words on a CD-ROM. Most recently we have developed a much better algorithm and have succeeded in finding a perfect hash function for a set of 5000 words taken from the Collins English Dictionary.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000115/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000115/01/TR-88-30.pdfen
dc.identifier.trnumberTR-88-30en
dc.identifier.urihttp://hdl.handle.net/10919/19417en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleA More Cost Effective Algorithm for Finding Perfect Hash Functionsen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-88-30.pdf
Size:
738.53 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports