Succinct indices for path minimum, with applications to path reporting

Timothy M. Chan, Meng He, J. Ian Munro, Gelin Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the path minimum query problem, we preprocess a tree on n weighted nodes, such that given an arbitrary path, we can locate the node with the smallest weight along this path. We design novel succinct indices for this problem; one of our index structures supports queries in O(α(m,n)) time, and occupies O(m) bits of space in addition to the space required for the input tree, where m is an integer greater than or equal to n and α(m,n) is the inverse-Ackermann function. These indices give us the first succinct data structures for the path minimum problem, and allow us to obtain new data structures for path reporting queries, which report the nodes along a query path whose weights are within a query range. We achieve three different time/space tradeoffs for path reporting by designing (a) an O(n)-word structure with O(lgεn+occ ·lg εn) query time, where occ is the number of nodes reported; (b) an O(n lg lg n)-word structure with O(lg lg n+occ · lg lg n)query time; and (c) an O(n lgεn) -word structure with O(lg lg n+occ) query time. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries [8] which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than n, we further improve both the query time and the space cost of these three results.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer
Pages247-259
Number of pages13
ISBN (Print)9783662447765
DOIs
StatePublished - 2014
Externally publishedYes
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
Country/TerritoryPoland
CityWroclaw
Period9/8/149/10/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Succinct indices for path minimum, with applications to path reporting'. Together they form a unique fingerprint.

Cite this