Document Open Access Logo

On Approximate Range Mode and Range Selection

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.57.pdf
  • Filesize: 0.58 MB
  • 14 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
Yakov Nekrich
  • Department of Computer Science, Michigan Technological University, USA
Bryce Sandlund
  • Cheriton School of Computer Science, University of Waterloo, Canada

Cite As Get BibTex

Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich, and Bryce Sandlund. On Approximate Range Mode and Range Selection. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.57

Abstract

For any epsilon in (0,1), a (1+epsilon)-approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor (1+epsilon) smaller than the true mode. For this problem, we design a data structure occupying O(n/epsilon) bits of space to answer queries in O(lg(1/epsilon)) time. This is an encoding data structure which does not require access to the input sequence; the space cost of this structure is asymptotically optimal for constant epsilon as we also prove a matching lower bound. Furthermore, our solution improves the previous best result of Greve et al. (Cell Probe Lower Bounds and Approximations for Range Mode, ICALP'10) by saving the space cost by a factor of lg n while achieving the same query time. In dynamic settings, we design an O(n)-word data structure that answers queries in O(lg n /lg lg n) time and supports insertions and deletions in O(lg n) time, for any constant epsilon in (0,1); the bounds for non-constant epsilon = o(1) are also given in the paper. This is the first result on dynamic approximate range mode; it can also be used to obtain the first static data structure for approximate 3-sided range mode queries in two dimensions.
Another problem we consider is approximate range selection. For any alpha in (0,1/2), an alpha-approximate range selection query asks for the position of an element whose rank in the query range is in [k - alpha s, k + alpha s], where k is a rank given by the query and s is the size of the query range. When alpha is a constant, we design an O(n)-bit encoding data structure that can answer queries in constant time and prove this space cost is asymptotically optimal. The previous best result by Krizanc et al. (Range Mode and Range Median Queries on Lists and Trees, Nordic Journal of Computing, 2005) uses O(n lg n) bits, or O(n) words, to achieve constant approximation for range median only. Thus we not only improve the space cost, but also provide support for any arbitrary k given at query time. We also analyse our solutions for non-constant alpha.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • data structures
  • approximate range query
  • range mode
  • range median

Metrics

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

References

  1. Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. Approximate Range Mode and Range Median Queries. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, pages 377-388, 2005. Google Scholar
  2. Gerth Stølting Brodal, Beat Gfeller, Allan Grønlund Jørgensen, and Peter Sanders. Towards optimal range medians. Theoretical Computeer Science, 412(24):2588-2601, 2011. Google Scholar
  3. Gerth Stølting Brodal and Allan Grønlund Jørgensen. Data Structures for Range Median Queries. In Proceedings of the 20th International Symposium on Algorithms and Computation, pages 822-831, 2009. Google Scholar
  4. 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(4):719-741, 2014. Google Scholar
  5. Timothy M. Chan and Bryan T. Wilkinson. Adaptive and Approximate Orthogonal Range Counting. ACM Trans. Algorithms, 12(4):45:1-45:15, 2016. Google Scholar
  6. Paul F. Dietz. Fully Persistent Arrays (Extended Array). In Proceedings of Workshop on Algorithms and Data Structures (WADS), pages 67-74, 1989. URL: https://doi.org/10.1007/3-540-51542-9_8.
  7. Hicham El-Zein, Meng He, J. Ian Munro, and Bryce Sandlund. Improved Time and Space Bounds for Dynamic Range Mode. In Proceedings of the 26th Annual European Symposium on Algorithms, pages 25:1-25:13, 2018. Google Scholar
  8. Johannes Fischer and Volker Heun. Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. SIAM Journal on Computing, 40(2):465-492, 2011. Google Scholar
  9. M. L. Fredman and D. E. Willard. BLASTING Through the Information Theoretic Barrier with FUSION TREES. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC '90, pages 1-7, 1990. Google Scholar
  10. Travis Gagie, Simon J. Puglisi, and Andrew Turpin. Range Quantile Queries: Another Virtue of Wavelet Trees. In Proceedings of the 16th International Symposium on String Processing and Information Retrieval, pages 1-6, 2009. Google Scholar
  11. Pawel Gawrychowski and Patrick K. Nicholson. Optimal Encodings for Range Top- k k , Selection, and Min-Max. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 593-604, 2015. Google Scholar
  12. Beat Gfeller and Peter Sanders. Towards Optimal Range Medians. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pages 475-486, 2009. Google Scholar
  13. Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, and Jakob Truelsen. Cell Probe Lower Bounds and Approximations for Range Mode. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, pages 605-616, 2010. Google Scholar
  14. Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao. Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries. ACM Transactions on Algorithms, 13(2):28:1-28:31, 2017. Google Scholar
  15. Meng He, J. Ian Munro, and Patrick K. Nicholson. Dynamic Range Selection in Linear Space. In Proceedings of the 22nd International Symposium, pages 160-169, 2011. Google Scholar
  16. Allan Grønlund Jørgensen and Kasper Green Larsen. Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 805-813, 2011. Google Scholar
  17. Danny Krizanc, Pat Morin, and Michiel H. M. Smid. Range Mode and Range Median Queries on Lists and Trees. Nord. J. Comput., 12(1):1-17, 2005. Google Scholar
  18. M. Patrascu. Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 305-313, 2008. Google Scholar
  19. Holger Petersen. Improved Bounds for Range Mode and Range Median Queries. In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, pages 418-423, 2008. Google Scholar
  20. Holger Petersen and Szymon Grabowski. Range mode and range median queries in constant time and sub-quadratic space. Information Processing Letters, 109(4):225-228, 2009. 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