Practical performance of Bloom filters and parallel free-text searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Practical performance of Bloom filters and parallel free-text searching

Full text

Pdf (337 KB)

Source

Communications of the ACM archive
Volume 32 , Issue 10 (October 1989) table of contents

Pages: 1237 - 1239

Year of Publication: 1989

ISSN:0001-0782

Author

M. V. Ramakrishna

Michigan State Univ., East Lansing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 106, Citation Count: 13

Additional Information:

abstract references cited by index terms review 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/67933.67941 What is a DOI?

ABSTRACT

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 the filter error rate is the focus of this article.

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	Jon Bentley, Programming pearls: a spelling checker, Communications of the ACM, v.28 n.5, p.456-462, May 1985 [doi>10.1145/3532.315102]
	2	Carter, L. J., and Wegman, M. L. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2 (1979), 143-154.
	3	Lee L. Gremillion, Designing a Bloom filter for differential file access, Communications of the ACM, v.25 n.9, p.600-604, Sept 1982 [doi>10.1145/358628.358632]
	4	McKenney, P. E. High-speed event counting and classification using a dictionary hash technique. In Proceedings of the Intl. Conference on Parallel Processing (Chicago, Ill., Aug. 8-12, 19891, pp. III-71-III-75.
	5	James K. Mullin, A second look at bloom filters, Communications of the ACM, v.26 n.8, p.570-571, Aug. 1983 [doi>10.1145/358161.358167]
	6	Robert Nix, Experience with a space efficient way to store a dictionary, Communications of the ACM, v.24 n.5, p.297-298, May 1981 [doi>10.1145/358645.358654]
	7	M V Ramakrishna, Perfect hashing for external files, University of Waterloo, Waterloo, Ont., Canada, 1986
	8	Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]

CITED BY 13

	Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States
	Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002
	J. Aguilar-Saborit , P. Trancoso , V. Muntes-Mulero , J. L. Larriba-Pey, Dynamic count filters, ACM SIGMOD Record, v.35 n.1, p.26-32, March 2006
	Jonathan Ledlie , Jacob M. Taylor , Laura Serban , Margo Seltzer, Self-organization in peer-to-peer systems, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France
	Eran Gabber , Abraham Silberschatz, Agora: a minimal distributed protocol for electronic commerce, Proceedings of the 2nd conference on Proceedings of the Second USENIX Workshop on Electronic Commerce, p.13-13, November 18-21, 1996, Oakland, California
	Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, ACM SIGARCH Computer Architecture News, v.33 n.2, p.494-505, May 2005
	W. J. Liu , J. Gong, Double sampling for flow measurement on high speed links, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.11, p.2221-2226, August, 2008
	Danyu Zhu , Matt Mutka, Cooperation among peers in an ad hoc network to support an energy efficient IM service, Pervasive and Mobile Computing, v.4 n.3, p.335-359, June, 2008
	J. Aguilar-Saborit , P. Trancoso , V. Muntes-Mulero , J. L. Larriba-Pey, Dynamic adaptive data structures for monitoring data streams, Data & Knowledge Engineering, v.66 n.1, p.92-115, July, 2008
	Michael Mitzenmacher , Salil Vadhan, Why simple hash functions work: exploiting the entropy in a data stream, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.746-755, January 20-22, 2008, San Francisco, 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
	Ming Zhong , Pin Lu , Kai Shen , Joel Seiferas, Optimizing data popularity conscious bloom filters, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Mahesh V. Tripunitara , Bogdan Carbunar, Efficient access enforcement in distributed role-based access control (RBAC) deployments, Proceedings of the 14th ACM symposium on Access control models and technologies, June 03-05, 2009, Stresa, Italy

INDEX TERMS

Primary Classification:
E. Data
E.2 DATA STORAGE REPRESENTATIONS
Subjects: Hash-table representations

Additional Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.2 Physical Design
Subjects: Access methods
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.3 Information Search and Retrieval
Subjects: Search process

General Terms:
Design, Performance

REVIEW

"Daniele Gardy : Reviewer"

This short communication deals with a special kind of hash function called “Bloom filters.” These filters are used, for example, to search a differential file containing updates to a main file. The paper recalls theoretical results o more...

Collaborative Colleagues:

M. V. Ramakrishna: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player