Our previous research on one-probe access to large collections of data indexed by alphanumeric keys has produced the first practical minimal perfect hash functions for this problem. Here, a new algorithm is described for quickly finding minimal perfect hash functions whose specification space is very close to the theoretical lower bound, i.e., around 2 bits per key. The various stages of processing are detailed, along with analytical and empirical results, including timing for a set of over 3.8 million keys that was processed on a NeXTstation in about 6 hours.

Rapid access to information is essential for a wide variety of retrieval systems and applications.Hashing has long been used when the fastest possible direct search is desired, but is generally not appropriate when sequential or range searches are also required.This paper describes a hashing method, developed for collections that are relatively static, that supports both direct and sequential access.The algorithms described give hash functions that are optimal in terms of time and hash table space utilization, and that preserve any a priori ordering desired, Furthermore, the resulting order-preserving minimal perfect hash functions (OPMPHFS) can be found using time and space that are linear in the number of keys involve~this is close to optimal,

Rapid access to information is essential for a wide variety of retrieval systems and applications. Hashing has long been used when the fastest possible direct search is desired, but is generally not appropriate when sequential or range searches are also required. This paper describes a hashing method, developed for collections that are relatively static, that supports both direct and sequential access. Indeed, the algorithm described gives hash functions that are optimal in terms of time and hash table space utilization, and that preserve any a priori ordering desired. Furthermore, the resulting order preserving minimal perfect hash functions (OPMPHFs) can be found using space and time that is on average linear in the number of keys involved.

With the advent of the information society, many researchers are turning to artificial intelligence techniques to provide effective retrieval over large bodies of textual information. In the CODER system, the mission of which is to provide an environment for experiments in applying AI to information retrieval, a factual representation language (FRL) serves as a tool for knowledge engineering and experimentation. the FRL is a hybrid AI language supporting strong typing for attribute values, a frame system, and Prolog-like relational structures. Inheritance is enforced throughout, and the semantics of type subsumption and object matching are formally defined. A collection of type and object managers called the knowledge administration complex implements this common language for storing knowledge and communicating it within the system. Storage of large numbers of complete knowledge objects (statements in the language) is supported by a system of external knowledge bases. Of the three types of knowledge structures in the language, the frame facility has proven most useful in the retrieval domain. This article discusses the frame construct itself, the implementation of the relevant portions of the knowledge administration complex and external knowledge bases, and the use of frames in retrieval research. It closes with a discussion of the utility of the FRL.