zbMATH — the first resource for mathematics

Shared-constraint range reporting. (English) Zbl 1365.68170
Arenas, Marcelo (ed.) et al., 18th international conference on database theory, ICDT’15, Brussels, Belgium, March 23–27, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-79-8). LIPIcs – Leibniz International Proceedings in Informatics 31, 277-290 (2015).
Summary: Orthogonal range reporting is one of the classic and most fundamental data structure problems. \((2,1,1)\) query is a 3 dimensional query with two-sided 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 four-sided range reporting in three-dimension) asks to report all those \(K\) points within a query region \([a, b]\times(-\infty, c]\times[d, \infty)\). These queries have overall 4 constraints. In Word-RAM 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 [L. Arge et al., “On two-dimensional indexability and optimal range search indexing”, in: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’99. Philadelphia, PA, 1999. New York, NY: Association for Computing Machinery (ACM). 346–357 (1999; doi:10.1145/303976.304010)]. 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 four-sided, the number of independent constraints is only three. In other words, one constraint is shared. We call this as a Shared-Constraint 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 linear-space and \(O(\log N+K)\) query time solution, matching the best-known 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/O-optimal (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 top-\(k\) color reporting, range skyline reporting and ranked document retrieval.
For the entire collection see [Zbl 1329.68018].
68P05 Data structures
Full Text: DOI