Improved Time and Space Bounds for Dynamic Range Mode

Authors Hicham El-Zein, Meng He, J. Ian Munro, Bryce Sandlund



PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.25.pdf
  • Filesize: 475 kB
  • 13 pages

Document Identifiers

Author Details

Hicham El-Zein
  • Cheriton School of Computer Science, University of Waterloo, Canada
Meng He
  • Faculty of Computer Science, Dalhousie University, Canada
J. Ian Munro
  • Cheriton School of Computer Science, University of Waterloo, Canada
Bryce Sandlund
  • Cheriton School of Computer Science, University of Waterloo, Canada

Cite AsGet BibTex

Hicham El-Zein, Meng He, J. Ian Munro, and Bryce Sandlund. Improved Time and Space Bounds for Dynamic Range Mode. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.25

Abstract

Given an array A of n elements, we wish to support queries for the most frequent and least frequent element in a subrange [l, r] of A. We also wish to support updates that change a particular element at index i or insert/ delete an element at index i. For the range mode problem, our data structure supports all operations in O(n^{2/3}) deterministic time using only O(n) space. This improves two results by Chan et al. [Timothy M. Chan et al., 2014]: a linear space data structure supporting update and query operations in O~(n^{3/4}) time and an O(n^{4/3}) space data structure supporting update and query operations in O~(n^{2/3}) time. For the range least frequent problem, we address two variations. In the first, we are allowed to answer with an element of A that may not appear in the query range, and in the second, the returned element must be present in the query range. For the first variation, we develop a data structure that supports queries in O~(n^{2/3}) time, updates in O(n^{2/3}) time, and occupies O(n) space. For the second variation, we develop a Monte Carlo data structure that supports queries in O(n^{2/3}) time, updates in O~(n^{2/3}) time, and occupies O~(n) space, but requires that updates are made independently of the results of previous queries. The Monte Carlo data structure is also capable of answering k-frequency queries; that is, the problem of finding an element of given frequency in the specified query range. Previously, no dynamic data structures were known for least frequent element or k-frequency queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • dynamic data structures
  • range query
  • range mode
  • range least frequent
  • range k-frequency

Metrics

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

References

  1. Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. Approximate range mode and range median queries. In Annual Symposium on Theoretical Aspects of Computer Science, 2005. Google Scholar
  2. 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
  3. Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson. Linear-space data structures for range mode query in arrays. Theory of Computing Systems, 55:719-741, 2014. Google Scholar
  4. Timothy M. Chan, Stephane Durocher, Matthew Skala, and Bryan T. Wilkinson. Linear-space data structures for range minority query in arrays. Algorithmica, 72:901-913, 2015. Google Scholar
  5. Timothy M Chan and Konstantinos Tsakalidis. Dynamic orthogonal range searching on the ram, revisited. In LIPIcs-Leibniz International Proceedings in Informatics, volume 77. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  6. Paul F. Dietz. Optimal algorithms for list indexing and subset rank. In Workshop on Data Structures and Algorithms, pages 39-46, 1989. Google Scholar
  7. Amr Elmasry, Meng He, J Ian Munro, and Patrick K Nicholson. Dynamic range majority data structures. In International Symposium on Algorithms and Computation, pages 150-159. Springer, 2011. Google Scholar
  8. Gereon Frahling, Piotr Indyk, and Christian Sohler. Sampling in dynamic data streams and applications. International Journal of Computational Geometry &Applications, 18(1/2):3-28, 2008. Google Scholar
  9. Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 135-143, 1984. Google Scholar
  10. Travis Gagie, Meng He, and Gonzalo Navarro. Compressed dynamic range majority data structures. In Data Compression Conference (DCC), 2017, pages 260-269. IEEE, 2017. Google Scholar
  11. Michael T. Goodrich and John G. Koss II. Tiered vectors: Efficient dynamic arrays for rank-based sequences. In Workshop on Data Structures and Algorithms, 1999. Google Scholar
  12. Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, and Jakob Truelsen. Cell probe lower bounds and approximations for range mode. In International Colloquium on Automata, Languages, and Programming, 2010. Google Scholar
  13. Meng He, J. Ian Munro, and Patrick K. Nicholson. Dynamic range selection in linear space. In International Symposium on Algorithms and Computation, 2011. Google Scholar
  14. Danny Krizanc, Pat Morin, and Michiel Smid. Range mode and range median queries on lists and trees. In International Symposium on Algorithms and Computation., pages 517-526, 2003. Google Scholar
  15. Mihai Pătraşcu and Emanuele Viola. Cell-probe lower bounds for succinct partial sums. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 117-122. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  16. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the forty-second annual ACM symposium on Theory of computing, pages 603-610, 2010. Google Scholar
  17. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the fourty-fourth annual symposium on theory of computing, 2012. 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