Abstract

The research involved optimizing the space and bounding the output time by the output size in categorical range reporting of points within the given rectangle query Q in two dimension using wavelet trees and range counting. The time taken to report those points and space to tore n points in set S can be done using wavelet tree and range counting. Consider set S consisting of n points in two-dimension. An orthogonal range reporting query rectangle Q = [a,b] x [c,d] on set S is sent to report the set of points in S which interacts with the query rectangle[Q]. The time taken to report these points is dependent on the output size. The categorical range reporting is an extension of orthogonal range reporting, where each point (xi; yi) in S is associated with a category c[i] belongs to [sigma] and the query is to report the set of distinct categories within the query region [a,b] x [c,d] once. In this paper, we present a new solution for this problem using wavelet trees. The points in S associated with categories are stored in a wavelet tree structure. Wavelet tree structure consists of bit map for these categories. To report the categories in the given rectangle query Q, rank and select operations on the wavelet tree is applied. It was observed that the space taken by the structure was O(n log sigma) space and query time is O(k log n log sigma). Notice that the new result is more efficient in space when log sigma = O(log n). The study provides a new and efficient way of storing large dataset and also bounds the time complexity by the output size k.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2018

Semester

Summer

Advisor

Valliyil Thankachan, Sharma

Degree

Master of Science in Computer Engineering (M.S.Cp.E.)

College

College of Engineering and Computer Science

Department

Electrical Engineering and Computer Engineering

Degree Program

Computer Engineering

Format

application/pdf

Identifier

CFE0007204

URL

http://purl.fcla.edu/fcla/etd/CFE0007204

Language

English

Release Date

August 2023

Length of Campus-only Access

5 years

Access Status

Masters Thesis (Open Access)

Download

Share

COinS