PhD Theses (Computer Science and Engineering)

Browse

Browsing PhD Theses (Computer Science and Engineering) by Author "Baig, Mirza Galib Anwarul Husain"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    On the Space Complexity of Storing Small Sets in the Bitprobe Model
    (2020) Baig, Mirza Galib Anwarul Husain
    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.