Ganguly, Arnab ;
Munro, J. Ian ;
Nekrich, Yakov ;
Shah, Rahul ;
Thankachan, Sharma V.
Categorical Range Reporting with Frequencies
Abstract
In this paper, we consider a variant of the color range reporting problem called color reporting with frequencies. Our goal is to preprocess a set of colored points into a data structure, so that given a query range Q, we can report all colors that appear in Q, along with their respective frequencies. In other words, for each reported color, we also output the number of times it occurs in Q. We describe an externalmemory data structure that uses O(N(1+log^2D/log N)) words and answers onedimensional queries in O(1 +K/B) I/Os, where N is the total number of points in the data structure, D is the total number of colors in the data structure, K is the number of reported colors, and B is the block size.
Next we turn to an approximate version of this problem: report all colors sigma that appear in the query range; for every reported color, we provide a constantfactor approximation on its frequency. We consider color reporting with approximate frequencies in two dimensions. Our data structure uses O(N) space and answers twodimensional queries in O(log_B N +log^*B + K/B) I/Os in the special case when the query range is bounded on two sides. As a corollary, we can also answer onedimensional approximate queries within the same time and space bounds.
BibTeX  Entry
@InProceedings{ganguly_et_al:LIPIcs:2019:10311,
author = {Arnab Ganguly and J. Ian Munro and Yakov Nekrich and Rahul Shah and Sharma V. Thankachan},
title = {{Categorical Range Reporting with Frequencies}},
booktitle = {22nd International Conference on Database Theory (ICDT 2019)},
pages = {9:19:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771016},
ISSN = {18688969},
year = {2019},
volume = {127},
editor = {Pablo Barcelo and Marco Calautti},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10311},
doi = {10.4230/LIPIcs.ICDT.2019.9},
annote = {Keywords: Data Structures, Range Reporting, Range Counting, Categorical Range Reporting, Orthogonal Range Query}
}
2019
Keywords: 

Data Structures, Range Reporting, Range Counting, Categorical Range Reporting, Orthogonal Range Query 
Seminar: 

22nd International Conference on Database Theory (ICDT 2019)

Issue date: 

2019 
Date of publication: 

2019 