On the Space Complexity of Storing Small Sets in the Bitprobe Model
No Thumbnail Available
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis, we study static membership problem which involves the study and construction of such data structures that can store an arbitrary subset S of size at most n from the universe U of size m such that membership queries of the form "Is x in S7' can be answered correctly and efficiently. A special category of the static membership problem is the bit probe model in which we evaluate our solutions w.r.t. the following resources-the size of the data structure. S required to store the subset S, and the number of bits, t, of the data structure read to answer membership queries. It is the second of these resources that lends the name to this model.
In this model, the design of data structures and query algorithms are known as schemes. For a given universe U and a subset S, the algorithm to set the bits of our data structure to store the subset is called the storage scheme whereas the algorithm to answer queries is called the query scheme. Schemes are divided into two categories depending on the nature of our query scheme. Upon a membership query for an element, if the decision to probe a particular bit depends upon the answers received in the previous bitprobes of this query, then such schemes are known as adaptive schemes. If the locations of the bitprobes are fixed for a given element of U, then such schemes are called non-adaptive schemes. Our work in this thesis gives better bounds for various values of n, m and t.
Description
Supervisor: Deepanjan Kesh
Keywords
COMPUTER SCIENCE AND ENGINEERING