Abstract
Orthogonal range reporting is one of the classic and most fundamental data structure problems. (2,1,1) query is a 3 dimensional query with twosided constraint on the first dimension and one sided constraint on each of the 2nd and 3rd dimension. Given a set of N points in three dimension, a particular formulation of such a (2,1,1) query (known as foursided range reporting in threedimension) asks to report all those K points within a query region [a, b]X(infinity, c]X[d, infinity). These queries have overall 4 constraints. In WordRAM model, the best known structure capable of answering such queries with optimal query time takes O(N log^{epsilon} N) space, where epsilon>0 is any positive constant. It has been shown that any external memory structure in optimal I/Os must use Omega(N log N/ log log_B N) space (in words), where B is the block size [Arge et al., PODS 1999]. In this paper, we study a special type of (2,1,1) queries, where the query parameters a and c are the same i.e., a=c. Even though the query is still foursided, the number of independent constraints is only three. In other words, one constraint is shared. We call this as a SharedConstraint Range Reporting (SCRR) problem. We study this problem in both internal as well as external memory models. In RAM model where coordinates can only be compared, we achieve linearspace and O(log N+K) query time solution, matching the bestknown three dimensional dominance query bound. Whereas in external memory, we present a linear space structure with O(log_B N + log log N + K/B) query I/Os. We also present an I/Ooptimal (i.e., O(log_B N+K/B) I/Os) data structure which occupies O(N log log N)word space. We achieve these results by employing a novel divide and conquer approach. SCRR finds application in database queries containing sharing among the constraints. We also show that SCRR queries naturally arise in many well known problems such as topk color reporting, range skyline reporting and ranked document retrieval.
BibTeX  Entry
@InProceedings{biswas_et_al:LIPIcs:2015:4990,
author = {Sudip Biswas and Manish Patil and Rahul Shah and Sharma V. Thankachan},
title = {{SharedConstraint Range Reporting}},
booktitle = {18th International Conference on Database Theory (ICDT 2015)},
pages = {277290},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897798},
ISSN = {18688969},
year = {2015},
volume = {31},
editor = {Marcelo Arenas and Mart{\'i}n Ugarte},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4990},
URN = {urn:nbn:de:0030drops49900},
doi = {10.4230/LIPIcs.ICDT.2015.277},
annote = {Keywords: data structure, shared constraint, multislab, point partitioning}
}
Keywords: 

data structure, shared constraint, multislab, point partitioning 
Seminar: 

18th International Conference on Database Theory (ICDT 2015) 
Issue Date: 

2015 
Date of publication: 

19.03.2015 