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.SEA.2017.12
URN: urn:nbn:de:0030-drops-76158
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7615/
Go to the corresponding LIPIcs Volume Portal

Baumstark, Niklas ; Gog, Simon ; Heuer, Tobias ; Labeit, Julian

Practical Range Minimum Queries Revisited

pdf-format:
LIPIcs-SEA-2017-12.pdf (0.7 MB)

Abstract

Finding the position of the minimal element in a subarray A[i..j] of an array A of size n is a fundamental operation in many applications. In 2011, Fischer and Heun presented the first index of size 2n+o(n) bits which answers the operation in constant time for any subarray. The index can be computed in linear time and queries can be answered without consulting the original array. The most recent and currently fastest practical index is due to Ferrada and Navarro (DCC'16). It reduces the range minimum query (RMQ) to more fundamental and well studied queries on binary vectors, namely rank and select, and a RMQ query on an array of sublinear size derived from A. A range min-max tree is employed to solve this recursive RMQ call. In this paper, we review their practical design and suggest a series of changes which result in consistently faster query times. Specifically, we provide a customized select implementation, switch to two levels of recursion, and use the sparse table solution for the recursion base case instead of a range min-max tree.

We provide an extensive empirical evaluation of our new implementation and also compare it to the state of the art. Our experimental study shows that our proposal significantly outperforms the previous solutions on established benchmarks (up to a factor of three) and furthermore accelerates real world applications such as traversing a succinct tree or listing all distinct elements in an interval of an array.

BibTeX - Entry

@InProceedings{baumstark_et_al:LIPIcs:2017:7615,
  author =	{Niklas Baumstark and Simon Gog and Tobias Heuer and Julian Labeit},
  title =	{{Practical Range Minimum Queries Revisited}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7615},
  URN =		{urn:nbn:de:0030-drops-76158},
  doi =		{10.4230/LIPIcs.SEA.2017.12},
  annote =	{Keywords: Succinct Data Structures, Range Minimum Queries, Algorithm Engineering}
}

Keywords: Succinct Data Structures, Range Minimum Queries, Algorithm Engineering
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

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