On the Space Complexity of Storing Small Sets in the Bitprobe Model

Show simple item record

dc.contributor.author Baig, Mirza Galib Anwarul Husain
dc.date.accessioned 2021-01-27T05:26:17Z
dc.date.available 2021-01-27T05:26:17Z
dc.date.issued 2020
dc.identifier.other ROLL NO.146201003
dc.identifier.uri http://gyan.iitg.ernet.in/handle/123456789/1797
dc.description Supervisor: Deepanjan Kesh en_US
dc.description.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. en_US
dc.language.iso en en_US
dc.relation.ispartofseries TH-2351;
dc.title On the Space Complexity of Storing Small Sets in the Bitprobe Model en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record



My Account