You are here
Categorical range reporting in 2D using Wavelet tree
 Date Issued:
 2018
 Abstract/Description:
 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 twodimension. 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 queryQ, 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.
Title:  Categorical range reporting in 2D using Wavelet tree. 
29 views
16 downloads 

Name(s): 
Kanthareddy Sumithra, Swathi, Author Valliyil Thankachan, Sharma, Committee Chair Sundaram, Kalpathy, Committee CoChair Jha, Sumit Kumar, Committee Member University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2018  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  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 twodimension. 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 queryQ, 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.  
Identifier:  CFE0007204 (IID), ucf:52275 (fedora)  
Note(s): 
20180801 M.S.Cp.E. Engineering and Computer Science, Electrical Engineering and Computer Engineering Masters This record was generated from author submitted information. 

Subject(s):  Categorical range reporting  wavelet tree  range counting  
Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0007204  
Restrictions on Access:  campus 20230815  
Host Institution:  UCF 