Lee L. Gremillion
Abstract
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 problems by preventing most unnecessary searches of the differential file. Here, the design process for a Bloom filter for an on-line student database is described, and it is shown that a very effective filter can be constructed with a modest expenditure of system resources.
- 1 Bloom, B.H. Space/time tradeoffs in hash coding with allowable errors. Comm. ACM 13, 7 (July 1970), 422-426. How hash coding methods which involve a small but tolerable error rate can be used to reduce the amount of space required for hash coded information. Google Scholar
Digital Library
- 2 Martin, J. Computer Data Base Organization. Prentice-Hall, Englewood Cliffs, N.J., 1977, pp. 382-385. A comprehensive textbook on the physical and logical design of databases. Google ScholarDigital Library
- 3 Rappaport, R.L. File structure design to facilitate on-line instantaneous updating. Proc. 1975 ACM SIGMOD Conf., San Jose, Calif., May 1975, pp. 1-14. Desc-;bes a system that uses a type of differential file to facilitate database recovery after power failures. Google ScholarDigital Library
- 4 Severance, D.G., and Lob_man, G.M. Differential files: Their application to the maintenance of large databases. A CM Trans. Database Systs. 11, 3 (Sept. 1976), 257-267. Discusses the uses and advantages of differential files for database modifications. Google ScholarDigital Library
Index Terms
- Designing a Bloom filter for differential file access
Recommendations
Application and Research on Weighted Bloom Filter and Bloom Filter in Web Cache
WMWA '09: Proceedings of the 2009 Second Pacific-Asia Conference on Web Mining and Web-based ApplicationA Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters and their generalizations, weighted Bloom filters and compressed Bloom filters have been suggested as a ...
LayerBF: A Space Allocation Policy for Bloom Filter in LSM-Tree
Web and Big DataAbstractLSM-Tree based key-value stores commonly suffer from the issue of read amplification, as the retrieval of a particular key typically requires examination of multiple layers of SSTables. To enhance query performance, a bloom filter is commonly ...
The Bloom paradox: when not to use a Bloom filter
In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is harmful and should not be queried. We first analyze conditions under which the Bloom paradox occurs in a Bloom Filter and demonstrate that it depends on the a ...
Comments