Document Open Access Logo

Enumerating Range Modes

Authors Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane , Srinivasa Rao Satti

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.29.pdf
  • Filesize: 1.16 MB
  • 16 pages

Document Identifiers

Author Details

Kentaro Sumigawa
  • Graduate School of Information Technology and Science, The University of Tokyo, Japan
Sankardeep Chakraborty
  • National Institute of Informatics, Tokyo, Japan
Kunihiko Sadakane
  • Graduate School of Information Technology and Science, The University of Tokyo, Japan
Srinivasa Rao Satti
  • Department of Computer Science and Engineering, Seoul National University, South Korea

Funding

  • Chakraborty, Sankardeep: Supported by JSPS KAKENHI Grant Number 18H05291, Japan.
  • Sadakane, Kunihiko: Supported by JST CREST Grant Number JPMJCR1402, Japan.

Cite AsGet BibTex

Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Enumerating Range Modes. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.29

Abstract

Given a sequence of elements, we consider the problem of indexing the sequence to support range mode queries - given a query range, find the element with maximum frequency in the range. We give indexing data structures for this problem; given a sequence, we construct a data structure that can be used later to process arbitrary queries. Our algorithms are efficient for small maximum frequency cases. We also consider a natural generalization of the problem: the range mode enumeration problem, for which there has been no known efficient algorithms. Our algorithms have query time complexities which are linear in the output size plus small terms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • range mode
  • space-efficient data structure
  • enumeration algorithm

Metrics

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

Related Versions

References

  1. 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, November 2014. URL: https://doi.org/10.1007/s00224-013-9455-2.
  2. Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Frequency estimation of internet packet streams with limited space. In Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, pages 348-360, 2002. Google Scholar
  3. Stephane Durocher and Jason Morrison. Linear-space data structures for range mode query in arrays. CoRR, abs/1101.4068, 2011. URL: http://arxiv.org/abs/1101.4068.
  4. Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman. Computing iceberg queries efficiently. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA, pages 299-310, 1998. URL: http://www.vldb.org/conf/1998/p299.pdf.
  5. J. Fischer and V. Heun. Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. SIAM Journal on Computing, 40(2):465-492, 2011. Google Scholar
  6. Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, and Jakob Truelsen. Cell probe lower bounds and approximations for range mode. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, pages 605-616, 2010. Google Scholar
  7. Danny Krizanc, Pat Morin, and Michiel Smid. Range mode and range median queries on lists and trees. Nordic J. of Computing, 12(1):1-17, March 2005. URL: http://dl.acm.org/citation.cfm?id=1195881.1195882.
  8. S. Muthukrishnan. Efficient algorithms for document retrieval problems. In Proceedings of ACM-SIAM SODA, pages 657-666, 2002. Google Scholar
  9. Holger Petersen. Improved bounds for range mode and range median queries. In Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, SOFSEM 2008: Theory and Practice of Computer Science, pages 418-423, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  10. 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. URL: https://doi.org/10.1016/j.ipl.2008.10.007.
  11. R. Raman, V. Raman, and S. R. Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms (TALG), 3(4), 2007. URL: https://doi.org/10.1145/1290672.1290680.
  12. Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Enumerating range modes. CoRR, abs/1907.10984, 2019. URL: http://arxiv.org/abs/1907.10984.
  13. Kentaro Sumigawa and Kunihiko Sadakane. Storing partitions of integers in sublinear space. The Review of Socionetwork Strategies, 13(2):237-252, 2019. URL: https://doi.org/10.1007/s12626-019-00044-2.
  14. Dan E. Willard. Log-logarithmic worst-case range queries are possible in space θ(n). Information Processing Letters, 17(2):81-84, 1983. URL: https://doi.org/10.1016/0020-0190(83)90075-3.
  15. Virginia Vassilevska Williams and Yinzhan Xu. Truly subcubic min-plus product for less structured matrices, with applications. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 12-29. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.2.
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 Imprint Privacy Contact