DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.29

Enumerating Range Modes

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

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{sumigawa_et_al:LIPIcs.ISAAC.2020.29,
  author =	{Sumigawa, Kentaro and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{Enumerating Range Modes}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.29},
  URN =		{urn:nbn:de:0030-drops-133732},
  doi =		{10.4230/LIPIcs.ISAAC.2020.29},
  annote =	{Keywords: range mode, space-efficient data structure, enumeration algorithm}
}

Search Results

Documents authored by Sumigawa, Kentaro

Enumerating Range Modes

Abstract

Cite as

Thanks for your feedback!

Could not send message