خط مشی دسترسیدرباره ماپشتیبانی آنلاین
ثبت نامثبت نام
راهنماراهنما
فارسی
ورودورود
صفحه اصلیصفحه اصلی
جستجوی مدارک
تمام متن
منابع دیجیتالی
رکورد قبلیرکورد بعدی
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)