License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.29
URN: urn:nbn:de:0030-drops-133732
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13373/
Go to the corresponding LIPIcs Volume Portal

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

Enumerating Range Modes

pdf-format:
LIPIcs-ISAAC-2020-29.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{sumigawa_et_al:LIPIcs:2020:13373,
  author =	{Kentaro Sumigawa and Sankardeep Chakraborty and Kunihiko Sadakane and Srinivasa Rao Satti},
  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 =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13373},
  URN =		{urn:nbn:de:0030-drops-133732},
  doi =		{10.4230/LIPIcs.ISAAC.2020.29},
  annote =	{Keywords: range mode, space-efficient data structure, enumeration algorithm}
}

Keywords: range mode, space-efficient data structure, enumeration algorithm
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI