Back to search

Central Florida

Categorical Range Reporting in 2D using Wavelet Tree

Abstract

dc:description.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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kanthareddy Sumithra, Swathi
Contributors dc:contributor
  • Valliyil Thankachan, Sharma

Subjects

dc:subject × 1

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0007204

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kanthareddy Sumithra, Swathi. Categorical Range Reporting in 2D using Wavelet Tree. https://stars.library.ucf.edu/etd/6048