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

Gagie, Travis ; He, Meng ; Navarro, Gonzalo

Path Queries on Functions

pdf-format:
LIPIcs-CPM-2017-5.pdf (0.5 MB)

Abstract

Let f : [1..n] -> [1..n] be a function, and l : [1..n] -> [1..s] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For example, we can find the minimum label in f^k (i) for a given i and any k >= 0 in a given range [k1..k2], using n lg n + O(n) bits, or the minimum label in f^(-k) (i) for a given i and k > 0, using 2n lg n + O(n) bits, both in time O(lg n/ lg lg n). By using n lg s + o(n lg s) further bits, we can also count, within the same time, the number of elements within a range of labels, and report each such element in O(1 + lg s / lg lg n) additional time. Several other possible queries are considered, such as top-t queries and t-majorities.

BibTeX - Entry

@InProceedings{gagie_et_al:LIPIcs:2017:7327,
  author =	{Travis Gagie and Meng He and Gonzalo Navarro},
  title =	{{Path Queries on Functions}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7327},
  URN =		{urn:nbn:de:0030-drops-73274},
  doi =		{10.4230/LIPIcs.CPM.2017.5},
  annote =	{Keywords: succinct data structures, integer functions, range queries, trees and permutations}
}

Keywords: succinct data structures, integer functions, range queries, trees and permutations
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

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