Exact and Approximate Membership Testers

Author

Larry J. Carter
Robert Floyd
John Gill
George Markowsky, Missouri University of Science and TechnologyFollow
Mark N. Wegman

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.

Recommended Citation

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 https://doi.org/10.1145/800133.804332

Meeting Name

10th Annual ACM Symposium on Theory of Computing (1978: May 1-3, San Diego, CA)

Department(s)

Computer Science

Keywords and Phrases

Computer Programming

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1978 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 May 1978