Document Open Access Logo

On Range Summary Queries

Authors Peyman Afshani, Pingan Cheng, Aniket Basu Roy, Zhewei Wei

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.7.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Peyman Afshani
  • Aarhus University, Denmark
Pingan Cheng
  • Aarhus University, Denmark
Aniket Basu Roy
  • Aarhus University, Denmark
Zhewei Wei
  • Renmin University of China, Beijing, China

Funding

Peyman Afshani, Pingan Cheng: Supported by DFF (Det Frie Forskningsråd) of Danish Council for Independent Research under grant ID DFF-7014-00404.
  • Basu Roy, Aniket: Supported by DFF (Det Frie Forskningsråd) of Danish Council for Independent Research under grant ID DFF-7014-00404 and the Independent Research Fund Denmark (DFF) under a Sapere Aude Research Leader grant No. 1051-00106B.
  • Wei, Zhewei: Supported by National Natural Science Foundation of China (No. U2241212).

Cite As Get BibTex

Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.7

Abstract

We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter ε and a set P of n points in ℝ^d where each point is assigned a color from a set C, and the goal is to build a structure such that given any geometric range γ, we can efficiently find a list of approximate heavy hitters in γ∩P, i.e., colors that appear at least ε |γ∩P| times in γ∩P, as well as their frequencies with an additive error of ε |γ∩P|. In the latter problem, each point is assigned a weight from a totally ordered universe and the query must output a sequence S of 1+1/ε weights such that the i-th weight in S has approximate rank iε|γ∩P|, meaning, rank iε|γ∩P| up to an additive error of ε|γ∩P|. Previously, optimal results were only known in 1D [Wei and Yi, 2011] but a few sub-optimal methods were available in higher dimensions [Peyman Afshani and Zhewei Wei, 2017; Pankaj K. Agarwal et al., 2012]. 
We study the problems for two important classes of geometric ranges: 3D halfspace and 3D dominance queries. It is known that many other important queries can be reduced to these two, e.g., 1D interval stabbing or interval containment, 2D three-sided queries, 2D circular as well as 2D k-nearest neighbors queries. We consider the real RAM model of computation where integer registers of size w bits, w = Θ(log n), are also available. For dominance queries, we show optimal solutions for both heavy hitter and quantile problems: using linear space, we can answer both queries in time O(log n + 1/ε). Note that as the output size is 1/ε, after investing the initial O(log n) searching time, our structure takes on average O(1) time to find a heavy hitter or a quantile! For more general halfspace heavy hitter queries, the same optimal query time can be achieved by increasing the space by an extra log_w(1/ε) (resp. log log_w(1/ε)) factor in 3D (resp. 2D). By spending extra log^O(1)(1/ε) factors in both time and space, we can also support quantile queries. 
We remark that it is hopeless to achieve a similar query bound for dimensions 4 or higher unless significant advances are made in the data structure side of theory of geometric approximations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Computational Geometry
  • Range Searching
  • Random Sampling
  • Geometric Approximation
  • Data Structures and Algorithms

Metrics

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

Related Versions

References

  1. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 180-186, 2009. Google Scholar
  2. Peyman Afshani, Chris Hamilton, and Norbert Zeh. A general approach for cache-oblivious range reporting and approximate range counting. Computational Geometry: Theory and Applications, 43:700-712, 2010. preliminary version at SoCG'09. Google Scholar
  3. Peyman Afshani and Jeff M. Phillips. Independent Range Sampling, Revisited Again. In Symposium on Computational Geometry (SoCG), pages 4:1-4:13, 2019. Google Scholar
  4. Peyman Afshani and Zhewei Wei. Independent Range Sampling, Revisited. In Proceedings of European Symposium on Algorithms (ESA), volume 87, pages 3:1-3:14, 2017. Google Scholar
  5. Pankaj K. Agarwal. Range searching. In J. E. Goodman, J. O'Rourke, and C. Toth, editors, Handbook of Discrete and Computational Geometry. CRC Press, Inc., 2016. Google Scholar
  6. Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 23-34, 2012. Google Scholar
  7. Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Range majorities and minorities in arrays. Algorithmica, 83(6):1707-1733, 2021. Google Scholar
  8. Djamal Belazzougui, Travis Gagie, and Gonzalo Navarro. Better space bounds for parameterized range majority and minority. In Algorithms and data structures, volume 8037 of Lecture Notes in Comput. Sci., pages 121-132. Springer, Heidelberg, 2013. Google Scholar
  9. Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. Approximate range mode and range median queries. In Proceedings of Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2005. Google Scholar
  10. Gerth Stølting Brodal, Beat Gfeller, Allan Grønlund Jørgensen, and Peter Sanders. Towards optimal range medians. Theoretical Computer Science, 412(24):2588-2601, 2011. Google Scholar
  11. Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In Symposium on Computational Geometry (SoCG), volume 164, pages 28:1-28:15, 2020. Google Scholar
  12. Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Symposium on Computational Geometry (SoCG), pages 1-10, 2011. Google Scholar
  13. Timothy M. Chan and Gelin Zhou. Multidimensional range selection. In Algorithms and computation, volume 9472 of Lecture Notes in Comput. Sci., pages 83-92. Springer, Heidelberg, 2015. Google Scholar
  14. Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, and Matthew Skala. Range majority in constant time and linear space. Inform. and Comput., 222:169-179, 2013. Google Scholar
  15. P. Gupta, R. Janardan, and M. Smid. Further results on generalized intersection searching problems: Counting, reporting, and dynamization. Journal of Algorithms, 19(2):282-317, 1995. Google Scholar
  16. Xiaocheng Hu, Miao Qiao, and Yufei Tao. Independent range sampling. In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, pages 246-255. ACM, 2014. URL: https://doi.org/10.1145/2594538.2594545.
  17. Zengfeng Huang and Ke Yi. The communication complexity of distributed epsilon-approximations. SIAM Journal of Computing, 46(4):1370-1394, 2017. Google Scholar
  18. Allan Grønlund Jørgensen and Kasper Green Larsen. Range selection and median: Tight cell probe lower bounds and adaptive data structures. In Proc. 22ndProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 805-813, 2011. Google Scholar
  19. Marek Karpinski and Yakov Nekrich. Searching for frequent colors in rectangles. In Proceedings of the 20th Annual Canadian Conference on Computational Geometry, Montréal, Canada, August 13-15, 2008, 2008. Google Scholar
  20. Danny Krizanc, Pat Morin, and Michiel Smid. Range mode and range median queries on lists and trees. Nordic J. Comput., 12(1):1-17, 2005. Google Scholar
  21. Jiří Matoušek. Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics. Springer Berlin Heidelberg, 2009. Google Scholar
  22. Jeff M. Phillips. Coresets and sketches. CoRR, abs/1601.00617, 2016. URL: https://arxiv.org/abs/1601.00617.
  23. Zhewei Wei and Ke Yi. Beyond simple aggregates: Indexing for summary queries. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 117-128. ACM, 2011. Google Scholar
  24. Ke Yi, Lu Wang, and Zhewei Wei. Indexing for summary queries: Theory and practice. ACM Transactions on Database Systems (TODS), 39(1), January 2014. 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