DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2020.23

Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP

Authors: Kotaro Matsuda, Kunihiko Sadakane, Tatiana Starikovskaya, and Masakazu Tateshita

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract

We propose a space-efficient data structure for orthogonal range search on suffix arrays. For general two-dimensional orthogonal range search problem on a set of n points, there exists an n log n (1+o(1))-bit data structure supporting O(log n)-time counting queries [Mäkinen, Navarro 2007]. The space matches the information-theoretic lower bound. However, if we focus on a point set representing a suffix array, there is a chance to obtain a space efficient data structure. We answer this question affirmatively. Namely, we propose a data structure for orthogonal range search on suffix arrays which uses O(1/(ε) n (H₀+1)) bits where H₀ is the order-0 entropy of the string and answers a counting query in O(n^ε) time for any constant ε>0. As an application, we give an O(1/(ε) n (H₀+1))-bit data structure for the range LCP problem.

Cite as

Kotaro Matsuda, Kunihiko Sadakane, Tatiana Starikovskaya, and Masakazu Tateshita. Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{matsuda_et_al:LIPIcs.CPM.2020.23,
  author =	{Matsuda, Kotaro and Sadakane, Kunihiko and Starikovskaya, Tatiana and Tateshita, Masakazu},
  title =	{{Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.23},
  URN =		{urn:nbn:de:0030-drops-121482},
  doi =		{10.4230/LIPIcs.CPM.2020.23},
  annote =	{Keywords: Orthogonal Range Search, Succinct Data Structure, Suffix Array}
}

Search Results

Documents authored by Tateshita, Masakazu

Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP

Abstract

Cite as

Thanks for your feedback!

Could not send message