An O(n log n) Algorithm for Finding Minimal Perfect Hash Functions

摘要: We describe the first practical algorithm for finding minimal perfect hash functions that can be used to access very large databases. This method extends earlier work wherein an O(n3) was devised, building upon prior by Sager described O(n4) algorithm. Our new O(n log n) expected time makes use of three key insights: applying randomness whereever possible, ordering our search based on degree vertices in a graph represents word dependencies, and viewing value assignment terms adding circular patterns related words partially filled disk. While ultimately applicable wide variety data file needs, this has already proven useful aiding improving performance CD-ROM systems construction Large External Network Database (LEND) semantic networks hypertext/hypermedia collections. Virginia Disc One includes demonstration function running PC 130,198 list CD-ROM, several other microcomputer, minicomputer, parallel processor versions applications have also been developed. Tests with French 420,878 entries library catalog set over 1.2 million keys shown methods