Exact and Approximate Membership Testers
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.
L. J. Carter et al., "Exact and Approximate Membership Testers," Proceedings of the 10th Annual ACM Symposium on Theory of Computing (1978, San Diego, CA), pp. 59-65, Association for Computing Machinery (ACM), May 1978.
The definitive version is available at http://dx.doi.org/10.1145/800133.804332
10th Annual ACM Symposium on Theory of Computing (1978: May 1-3, San Diego, CA)
Keywords and Phrases
Article - Conference proceedings
© 1978 Association for Computing Machinery (ACM), All rights reserved.