Designing a Bloom filter for differential file access

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Designing a Bloom filter for differential file access

Full text

Pdf (438 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 9 (September 1982) table of contents

Pages: 600 - 604

Year of Publication: 1982

ISSN:0001-0782

Author

Lee L. Gremillion

Indiana Univ., Bloomington

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 50, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358628.358632 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
	2	James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
	3	Robert L. Rappaport, File structure design to facilitate on-line instantaneous updating, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500082]
	4	Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]

CITED BY 8

	James K. Mullin, A second look at bloom filters, Communications of the ACM, v.26 n.8, p.570-571, Aug. 1983
	Timothy R. Hill , Ananth Srinivasan, Performance analysis in a differential file environment, Proceedings of the 17th conference on Winter simulation, p.278-283, December 11-13, 1985, San Francisco, California, United States
	Robert L. Ashenhurst, ACM forum, Communications of the ACM, v.26 n.4, p.243-244, April 1983
	M. V. Ramakrishna, Practical performance of Bloom filters and parallel free-text searching, Communications of the ACM, v.32 n.10, p.1237-1239, Oct. 1989
	Saar Cohen , Yossi Matias, Spectral bloom filters, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Robert A. Burnett , Paula J. Cowley , James J. Thomas, Management and display of data analysis environments for large data sets, Proceedings of the 2nd international workshop on Proceedings of the Second International Workshop on Statistical Database Management, p.22-31, September 27-29, 1983, Los Altos, California
	Prosenjit Bose , Hua Guo , Evangelos Kranakis , Anil Maheshwari , Pat Morin , Jason Morrison , Michiel Smid , Yihui Tang, On the false-positive rate of Bloom filters, Information Processing Letters, v.108 n.4, p.210-213, October, 2008