Title

Exact and Approximate Membership Testers

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.

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.

Share

 
COinS