Approximate colored range and point enclosure queries

Abstract

Range queries and point enclosure queries are popular in myriads of database applications. In this thesis, we study the range and point enclosure queries in the presence of categorical information (modelled as colors). We formulate two classes of problems, namely the colored range query problems and the colored point enclosure query problems to model multi-dimensional range and point enclosure queries in colored context. We argue that many of these problems are difficult to solve. Based on a new framework of combining sketching techniques and traditional data structures, we obtain two sets of results in solving the problems approximately and efficiently. For the colored range query problems, only colored range counting and colored range reporting were studied before. Although there are efficient l-dimensional structures for the two problems, no good solutions are found for higher dimensions (d ≥ 2). With our framework, we produce efficient approximate data structures that solve the higher dimensional colored range counting and two other colored range query problems. For the colored point enclosure problems, much less is known. Gupta et al. [15] proposed static structures for the colored point enclosure counting in 1 and 2-dimensional contexts and no solutions are found for higher dimensions. We present two dynamic solutions (based on the segment tree and interval tree) to solve the colored point enclosure problems approximately and the solutions can be extended to higher dimensions using standard technique [5].

Date of Award	14 Jul 2006
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chung Keung POON (Supervisor)