We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries, such as range counts. SuRF is based on a ...

Database management systems are powerful tools for processing large volumes of structured, or normalized, data. Much of the data to be stored in computer systems, however, differs from normalized data in both its logical uses and the storage structure ...

The importance of file migration is increasing because of its potential to improve the performance of distributed office, manufacturing and hospital information systems. To encourage research in the file migration problem, the authors summarize ...

Bloom filter technique of hashing finds several applications, such as in efficient maintenance of differential files, space efficient storage of dictionaries, and parallel free-text searching. The performance of hash transformations with reference to ...

Growth of distributed systems has attained unstoppable momentum. If we better understood how to think about, analyze, and design distributed systems, we could direct their implementation with more confidence.

A simple database language for personal computers has been implemented by selecting a subset of the ANS MUMPS language and enhancing it so as to meet the requirements of microcomputer end-users who are unfamiliar with computers. This database language ...

This note deals with a paper by Gremillion demonstrating the simulation approach to the design of a Bloom filter. It is shown that an analytical approach can yield insights into competing filter design and give expected values for the goodness-of-hash ...

The coalesced hashing method is one of the faster searching methods known today. This paper is a practical study of coalesced hashing for use by those who intend to implement or further study the algorithm. Techniques are developed for tuning an ...

The use of a differential file for a database update can yield integrity and performance benefits, but it can also present problems in providing current data to subsequent accessing transactions. A mechanism known as a Bloom filter can solve these ...

A requirement of many computer file processing systems is the ability to access data stored on a direct access storage device (DASD) both sequentially and randomly. A popular method which provides both types of access is the index sequential ...