Perfect hashing and related problems

Simple item page
dc.contributor.authorJuvvadi, Ramana Raoen
dc.contributor.committeechairHeath, Lenwood S.en
dc.contributor.committeememberAllison, Donald C. S.en
dc.contributor.committeememberShaffer, Clifford A.en
dc.contributor.committeememberFox, Edward A.en
dc.contributor.committeememberSherali, Hanif D.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T21:10:43Zen
dc.date.adate2006-05-04en
dc.date.available2014-03-14T21:10:43Zen
dc.date.issued1993-06-05en
dc.date.rdate2006-05-04en
dc.date.sdate2006-05-04en
dc.description.abstractOne of the most common tasks in many computer applications is the maintenance of a dictionary of words. The three most basic operations on the dictionary are find, insert, and delete. An important data structure that supports these operations is a hash table. On a hash table, a basic operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case, where n is the number of words in the dictionary. While an ordinary hash function maps the words in a dictionary to a hash table with collisions, a perfect hash function maps the words in a dictionary to a hash table with no collisions. Thus, perfect hashing is a special case of hashing, in which a find operation takes 𝑂(1) time in the worst case, and an insert or a delete operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case. This thesis addresses the following issues: Mapping, ordering and searching (MOS) is a successful algorithmic approach to finding perfect hash functions for static dictionaries. Previously, no analysis has been given for the running time of the MOS algorithm. In this thesis, a lower bound is proved on the tradeoff between the time required to find a perfect hash function and the space required to represent the perfect hash function . A new algorithm for static dictionaries called the musical chairs(MC) algorithm is developed that is based on ordering the hyperedges of a graph. It is found experimentally that the MC algorithm runs faster than the MOS algorithm in all cases for which the MC algorithm is capable of finding a perfect hash function. A new perfect hashing algorithm is developed for dynamic dictionaries. In this algorithm, an insert or a delete operation takes 𝑂(1) time in the average case, and a find operation takes 𝑂(1) time in the worst case. The algorithm is modeled using results from queueing theory . An ordering problem from graph theory, motivated by the hypergraph ordering problem in the Me algorithm, is proved to be NP-complete.en
dc.description.degreePh. D.en
dc.format.extentviii, 136 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-05042006-164527en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-05042006-164527/en
dc.identifier.urihttp://hdl.handle.net/10919/37704en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V856_1993.J888.pdfen
dc.relation.isformatofOCLC# 29179312en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V856 1993.J888en
dc.subject.lcshHashing (Computer science)en
dc.titlePerfect hashing and related problemsen
dc.typeDissertationen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V856_1993.J888.pdf
Size:
5.16 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Doctoral Dissertations