Exact and approximate membership testers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exact and approximate membership testers

Full text

Pdf (521 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the tenth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 59 - 65

Year of Publication: 1978

Authors

Larry Carter
Robert Floyd
John Gill
George Markowsky
Mark Wegman

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 33, Citation Count: 13

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/800133.804332 What is a DOI?

ABSTRACT

In this paper we consider the question of how much space is needed to represent a set. Given a finite universe U and some subset V (called the vocabulary), an exact membership tester is a procedure that for each element s in U determines if s is in V. An approximate membership tester is allowed to make mistakes: we require that the membership tester correctly accepts every element of V, but we allow it to also accept a small fraction of the elements of U - V.

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	J. Lawrence Carter , Mark N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.106-112, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803400]
	3	Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
	4	Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM (JACM), v.22 n.3, p.329-340, July 1975 [doi>10.1145/321892.321894]
	5	P. Erdös and J. Spencer,Probabilistic Methods in Combinatorics, Chapter 13, Academic Press, New York, 1974.
	6	Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
	7	J. Gill, "Computational Complexity of Probabilistic Turing Machines," SIAM Journal on Computing 6 (1977), pp. 675-695.
	8	D.A. Huffman, "A Method for the Construction of Minimum Redundancy Codes," Proc. IRE 40 (1952), pp. 1098-1101.
	9	A.N. Kolmogorov, "Three Approaches to the Definition of the Concept 'Quantity of Information'," Probl.Pederachi Inform. 1.(1965), pp. 3-11.
	10	M.O. Rabin, "Probabilistic Algorithms," Algorithms and Complexity: New Directions and Recent Results, J.F. Traub, ed., Academic Press, New York, 1976, pp. 21-40.
	11	W.S. Rosenbaum and J.J. Hilliard, "Multifont OCR Postprocessing System," IBM Journal of Research and Development 19 (1975), pp. 398-421.

CITED BY 13

	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States
	Steven R. Wood, Z - the 95% program editor, ACM SIGPLAN Notices, v.16 n.6, p.1-7, June 1981
	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
	Thomas N. Turba, Checking for spelling and typographical errors in computer-based text, ACM SIGPLAN Notices, v.16 n.6, p.51-60, June 1981
	Richard Cole , Alan Siegel, Optimal VLSI circuits for sorting, Journal of the ACM (JACM), v.35 n.4, p.777-809, Oct. 1988
	James Aweya , Michel Ouellette , Delfin Y. Montuno, Weighted proportional window control of TCP traffic, International Journal of Network Management, v.11 n.4, p.213-242, July–August 2001
	Thomas N. Turba, Length-segmented lists, Communications of the ACM, v.25 n.8, p.522-526, Aug 1982
	Gaston H. Gonnet, Unstructured data bases or very efficient text searching, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Anna Pagh , Rasmus Pagh , S. Srinivasa Rao, An optimal Bloom filter replacement, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	James Aweya , Michel Ouellette , Delfin Y. Montuno, Active queue management with flow proportional buffering, International Journal of Network Management, v.13 n.3, p.211-229, May 2003
	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
	Djamal Belazzougui , Paolo Boldi , Rasmus Pagh , Sebastiano Vigna, Monotone minimal perfect hashing: searching a sorted table with O(1) accesses, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.785-794, January 04-06, 2009, New York, New York
	Rasmus Pagh , Srinivasa Rao Satti, Secondary indexing in one dimension: beyond b-trees and bitmap indexes, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA