  Document Type  :  Latin Dissertation  Language of Document  :  English  Record Number  :  53978  Doc. No  :  TL23932  Call number  :  MR35310  Main Entry  :  Mohammad Ziaur Rahman  Title & Author  :  Data structuring problems in the bit probe modelMohammad Ziaur Rahman  College  :  University of Waterloo (Canada)  Date  :  2007  Degree  :  M.Math.  student score  :  2007  Page No  :  77  Abstract  :  We study two data structuring problems under the bit probe model: the dynamic predecessor problem and integer representation in a manner supporting basic updates in as few bit operations as possible. The model of computation considered in this paper is the bit probe model. In this model, the complexity measure counts only the bitwise accesses to the data structure. The model ignores the cost of computation. As a result, the bit probe complexity of a data structuring problem can be considered as a fundamental measure of the problem. Lower bounds derived by this model are valid as lower bounds for any realistic, sequential model of computation. Furthermore, some of the problems are more suitable for study in this model as they can be solved using less than w bit probes where w is the size of a computer word. The predecessor problem is one of the fundamental problems in computer science with numerous applications and has been studied for several decades. We study the colored predecessor problem, a variation of the predecessor problem, in which each element is associated with a symbol from a finite alphabet or color. The problem is to store a subset S of size n; from a finite universe U so that to support efficient insertion, deletion and queries to determine the color of the largest value in S which is not larger than x; for a given x ∈ U. We present a data structure for the problem that requires O(k[special characters omitted]) bit probes for the query and O(k 2 [special characters omitted]) bit probes for the update operations, where U is the universe size and k is positive constant. We also show that the results on the colored predecessor problem can be used to solve some other related problems such as existential range query, dynamic prefix sum, segment representative, connectivity problems, etc. The second structure considered is for integer representation. We examine the problem of integer representation in a nearly minimal number of bits so that increment and decrement (and indeed addition and subtraction) can be performed using few bit inspections and fewer bit changes. In particular, we prove a new lower bound of Ω([special characters omitted]) for the increment and decrement operation, where n is the minimum number of bits required to represent the number. We present several efficient data structures to represent integers that use a logarithmic number of bit inspections and a constant number of bit changes per operation.  Subject  :  Pure sciences; Mathematics; 0405:Mathematics  Added Entry  :  University of Waterloo (Canada) 
     
   
http://lib.clisel.com/site/catalogue/53978

 