Document Open Access Logo

Shared-Constraint Range Reporting

Authors Sudip Biswas, Manish Patil, Rahul Shah, Sharma V. Thankachan

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.277.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Sudip Biswas
Manish Patil
Rahul Shah
Sharma V. Thankachan

Cite As Get BibTex

Sudip Biswas, Manish Patil, Rahul Shah, and Sharma V. Thankachan. Shared-Constraint Range Reporting. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 277-290, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.277

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 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]X(-infinity, c]X[d, infinity). 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 [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 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.

Subject Classification

Keywords
  • data structure
  • shared constraint
  • multi-slab
  • point partitioning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Peyman Afshani. On dominance reporting in 3d. In ESA, pages 41-51, 2008. Google Scholar
  2. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting in three and higher dimensions. In FOCS, pages 149-158, 2009. Google Scholar
  3. Peyman Afshani, Lars Arge, and Kasper Dalgaard Larsen. Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In Symposium on Computational Geometry, pages 240-246, 2010. Google Scholar
  4. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In FOCS, pages 198-207, 2000. Google Scholar
  5. Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. The priority r-tree: A practically efficient and worst-case optimal r-tree. In SIGMOD Conference, pages 347-358, 2004. Google Scholar
  6. Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. On two-dimensional indexability and optimal range search indexing. In PODS, pages 346-357, 1999. Google Scholar
  7. Jon Louis Bentley. Multidimensional divide-and-conquer. Commun. ACM, 23(4):214-229, 1980. Google Scholar
  8. Gerth Stølting Brodal and Kasper Green Larsen. Optimal planar orthogonal skyline counting queries. CoRR, abs/1304.7959, 2013. Google Scholar
  9. Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu. Orthogonal range searching on the ram, revisited. In Symposium on Computational Geometry, pages 1-10, 2011. Google Scholar
  10. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427-462, 1988. Google Scholar
  11. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988. Google Scholar
  12. Bernard Chazelle. Lower bounds for orthogonal range searching i. the reporting case. J. ACM, 37(2):200-212, 1990. Google Scholar
  13. Bernard Chazelle. Lower bounds for orthogonal range searching ii. the arithmetic model. J. ACM, 37(3):439-463, 1990. Google Scholar
  14. Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter. Space-efficient frameworks for top-k string retrieval. J. ACM, 61(2):9, 2014. Google Scholar
  15. Marek Karpinski and Yakov Nekrich. Top-k color queries for document retrieval. In SODA, pages 401-411, 2011. Google Scholar
  16. Casper Kejlberg-Rasmussen, Yufei Tao, Konstantinos Tsakalidis, Kostas Tsichlas, and Jeonghun Yoon. I/o-efficient planar range skyline and attrition priority queues. In PODS, pages 103-114, 2013. Google Scholar
  17. Kasper Green Larsen and Rasmus Pagh. I/o-efficient data structures for colored range and prefix reporting. In SODA, pages 583-592, 2012. Google Scholar
  18. S. Muthukrishnan. Efficient algorithms for document retrieval problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 657-666, 2002. Google Scholar
  19. Yakov Nekrich. External memory range reporting on a grid. In ISAAC, pages 525-535, 2007. Google Scholar
  20. Darren Erik Vengroff and Jeffrey Scott Vitter. Efficient 3-d range searching in external memory. In STOC, pages 192-201, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact