Document Open Access Logo

Further Results on Colored Range Searching

Authors Timothy M. Chan , Qizheng He, Yakov Nekrich

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.28.pdf
  • Filesize: 443 kB
  • 15 pages

Document Identifiers

Author Details

Timothy M. Chan
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Qizheng He
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Yakov Nekrich
  • Department of Computer Science, Michigan Technological University, Houghton, MI, USA

Funding

  • Chan, Timothy M.: Supported in part by NSF Grant CCF-1814026.

Cite As Get BibTex

Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.28

Abstract

We present a number of new results about range searching for colored (or "categorical") data:
1) For a set of n colored points in three dimensions, we describe randomized data structures with O(n polylog n) space that can report the distinct colors in any query orthogonal range (axis-aligned box) in O(k polyloglog n) expected time, where k is the number of distinct colors in the range, assuming that coordinates are in {1,…,n}. Previous data structures require O((log n)/(log log n) + k) query time. Our result also implies improvements in higher constant dimensions.
2) Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving O(k log n) expected query time. Previous data structures require O(k log²n) query time.
3) For a set of n colored points in two dimensions, we describe a data structure with O(n polylog n) space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is O((log n)/(log log n) + k log log n), where k is the number of distinct colors in the range. Naively performing k uncolored range counting queries would require O(k (log n)/(log log n)) time.
Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Data structures design and analysis
Keywords
  • Range searching
  • geometric data structures
  • randomized incremental construction
  • random sampling
  • word RAM

Metrics

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

Related Versions

References

  1. Peyman Afshani, Cheng Sheng, Yufei Tao, and Bryan T. Wilkinson. Concurrent range reporting in two-dimensional space. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 983-994, 2014. URL: https://doi.org/10.1137/1.9781611973402.73.
  2. Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi. Indexing uncertain data. In Proc. 28th ACM Symposium on Principles of Database Systems (PODS), pages 137-146, 2009. URL: https://doi.org/10.1145/1559795.1559816.
  3. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 198-207, 2000. URL: https://doi.org/10.1109/SFCS.2000.892088.
  4. Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms, 1(4):301-358, 1980. URL: https://doi.org/10.1016/0196-6774(80)90015-2.
  5. Panayiotis Bozanis, Nectarios Kitsios, Christos Makris, and Athanasios K. Tsakalidis. New upper bounds for generalized intersection searching problems. In Proc. 22nd International Colloquium on Automata, Languages and Programming (ICALP), pages 464-474, 1995. URL: https://doi.org/10.1007/3-540-60084-1_97.
  6. Timothy M. Chan. Random sampling, halfspace range reporting, and construction of (≤ k)-levels in three dimensions. SIAM J. Comput., 30(2):561-575, 2000. URL: https://doi.org/10.1137/S0097539798349188.
  7. Timothy M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM, 57(3):16:1-16:15, 2010. URL: https://doi.org/10.1145/1706591.1706596.
  8. Timothy M. Chan. Persistent predecessor search and orthogonal point location on the word RAM. ACM Transactions on Algorithms, 9(3):22, 2013. Google Scholar
  9. Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proc. 27th ACM Symposium on Computational Geometry (SoCG), pages 1-10, 2011. Google Scholar
  10. Timothy M. Chan and Yakov Nekrich. Towards an optimal method for dynamic planar point location. SIAM Journal on Computing, 47(6):2337-2361, 2018. Google Scholar
  11. Timothy M. Chan and Yakov Nekrich. Better data structures for colored orthogonal range reporting. In Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627-636, 2020. Google Scholar
  12. Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. Orthogonal point location and rectangle stabbing queries in 3-d. In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 31:1-31:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.31.
  13. Bernard Chazelle, Richard Cole, Franco P. Preparata, and Chee-Keng Yap. New upper bounds for neighbor searching. Information and Control, 68(1-3):105-124, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80030-4.
  14. Kenneth L Clarkson and Peter W Shor. Applications of random sampling in computational geometry, ii. Discrete & Computational Geometry, 4(5):387-421, 1989. Google Scholar
  15. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Google Scholar
  16. Mark de Berg, Marc van Kreveld, and Jack Snoeyink. Two-dimensional and three-dimensional point location in rectangular subdivisions. Journal of Algorithms, 18(2):256-277, 1995. Google Scholar
  17. Paul F. Dietz. Fully persistent arrays. In Proc. 1st Workshop on Algorithms and Data Structures (WADS), pages 67-74, 1989. URL: https://doi.org/10.1007/3-540-51542-9_8.
  18. Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct color searching in one dimension. In Proc. 28th International Symposium on Algorithms and Computation (ISAAC), pages 30:1-30:11, 2017. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2017.30.
  19. Travis Gagie, Juha Kärkkäinen, Gonzalo Navarro, and Simon J. Puglisi. Colored range queries and document retrieval. Theor. Comput. Sci., 483:36-50, 2013. URL: https://doi.org/10.1016/j.tcs.2012.08.004.
  20. Arnab Ganguly, J. Ian Munro, Yakov Nekrich, Rahul Shah, and Sharma V. Thankachan. Categorical range reporting with frequencies. In Proc. 22nd International Conference on Database Theory (ICDT), pages 9:1-9:19, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.9.
  21. Roberto Grossi and Søren Vind. Colored range searching in linear space. In Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 229-240, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_20.
  22. Prosenjit Gupta, Ravi Janardan, Saladi Rahul, and Michiel H. M. Smid. Computational geometry: Generalized (or colored) intersection searching. In Handbook of Data Structures and Applications, chapter 67, pages 1042-1057. CRC Press, 2nd edition, 2018. URL: https://www.csa.iisc.ac.in/~saladi/Papers/ds2-handbook.pdf.
  23. Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. Further results on generalized intersection searching problems: Counting, reporting, and dynamization. J. Algorithms, 19(2):282-317, 1995. URL: https://doi.org/10.1006/jagm.1995.1038.
  24. Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. Algorithms for generalized halfspace range searching and other intersection searching problems. Comput. Geom., 6:1-19, 1996. URL: https://doi.org/10.1016/0925-7721(95)00012-7.
  25. Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. A technique for adding range restrictions to generalized searching problems. Inf. Process. Lett., 64(5):263-269, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00183-X.
  26. Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. Algorithms for some intersection searching problems involving circular objects. International Journal of Mathematical Algorithms, 1:35-52, 1999. Google Scholar
  27. Joseph JáJá, Christian Worm Mortensen, and Qingmin Shi. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In Proc. 15th International Symposium on Algorithms and Computation (ISAAC), pages 558-568, 2004. URL: https://doi.org/10.1007/978-3-540-30551-4_49.
  28. Ravi Janardan and Mario A. Lopez. Generalized intersection searching problems. International Journal of Computational Geometry and Applications, 3(1):39-69, 1993. Google Scholar
  29. Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin. Efficient colored orthogonal range counting. SIAM J. Comput., 38(3):982-1011, 2008. URL: https://doi.org/10.1137/070684483.
  30. Haim Kaplan, Micha Sharir, and Elad Verbin. Colored intersection searching via sparse rectangular matrix multiplication. In Proc. 22nd ACM Symposium on Computational Geometry (SoCG), pages 52-60, 2006. URL: https://doi.org/10.1145/1137856.1137866.
  31. Kasper Green Larsen and Rasmus Pagh. I/O-efficient data structures for colored range and prefix reporting. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 583-592, 2012. URL: https://doi.org/10.1137/1.9781611973099.49.
  32. Kasper Green Larsen and Freek van Walderveen. Near-optimal range reporting structures for categorical data. In Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 256-276, 2013. Google Scholar
  33. Jiří Matoušek. Reporting points in halfspaces. Comput. Geom., 2:169-186, 1992. URL: https://doi.org/10.1016/0925-7721(92)90006-E.
  34. Christian Worm Mortensen. Generalized static orthogonal range searching in less space. Technical report, IT University Technical Report Series 2003-33, 2003. Google Scholar
  35. Ketan Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, 1994. Google Scholar
  36. S. Muthukrishnan. Efficient algorithms for document retrieval problems. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 657-666, 2002. URL: https://doi.org/10.1145/545381.545469.
  37. Yakov Nekrich. Efficient range searching for categorical and plain data. ACM Trans. Database Syst., 39(1):9, 2014. URL: https://doi.org/10.1145/2543924.
  38. Yakov Nekrich and Jeffrey Scott Vitter. Optimal color range reporting in one dimension. In Proc. 21st European Symposium on Algorithms (ESA), pages 743-754, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_63.
  39. János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Proc. 27th ACM Symposium on Computational Geometry (SoCG), pages 458-463, 2011. URL: https://doi.org/10.1145/1998196.1998271.
  40. Manish Patil, Sharma V. Thankachan, Rahul Shah, Yakov Nekrich, and Jeffrey Scott Vitter. Categorical range maxima queries. In Proc. 33rd ACM Symposium on Principles of Database Systems (PODS), pages 266-277, 2014. URL: https://doi.org/10.1145/2594538.2594557.
  41. Mihai Patrascu. Lower bounds for 2-dimensional range counting. In Proc. 39th ACM Symposium on Theory of Computing (STOC), pages 40-46, 2007. URL: https://doi.org/10.1145/1250790.1250797.
  42. Mihai Patrascu. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827-847, 2011. URL: https://doi.org/10.1137/09075336X.
  43. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985. Google Scholar
  44. Saladi Rahul. Approximate range counting revisited. In Proc. 33rd International Symposium on Computational Geometry (SoCG), pages 55:1-55:15, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.55.
  45. Raimund Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, pages 37-67. Springer-Verlag, 1993. Google Scholar
  46. Qingmin Shi and Joseph JáJá. Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines. Inf. Process. Lett., 95(3):382-388, 2005. URL: https://doi.org/10.1016/j.ipl.2005.04.008.
  47. Darren Erik Vengroff and Jeffrey Scott Vitter. Efficient 3-d range searching in external memory. In Proc. 28th ACM Symposium on Theory of Computing (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