Path queries on functions
type: Item
instance of: scholarly article
title: Path queries on functions
zbMATH Open document ID: 1473.68060
author: Travis Gagie
author: Meng He
author: Gonzalo Navarro
published in: Theoretical Computer Science
publication date: 2019-05-02T00:00:00Z
review text: In this article the authors propose several algorithms for creating compact data structures used to provide efficient answers to queries on paths like: minimum or maximum, selection, top-\(r\), \(\tau\)-majority and range queries. After a brief introduction of the theoretical concepts, the authors describe the algorithms for constructing the compact structures and querying them. For each algorithm the correctness is demonstrated and the complexity is analyzed in detail. The article is clearly and well written and structured.
reviewed by: Mihai Gabroveanu
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 7050144
zbMATH Keywords: succinct data structures
zbMATH Keywords: integer functions
zbMATH Keywords: range queries
zbMATH Keywords: trees
zbMATH Keywords: permutations
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.10.021
OpenAlex ID: W2897193193
cites work: Theory and practice of monotone minimal perfect hashing
cites work: Range majorities and minorities in arrays
cites work: Representing trees of higher degree
cites work: Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
cites work: Succinct Indices for Path Minimum, with Applications to Path Reporting
cites work: Orthogonal range searching on the RAM, revisited
cites work: A uniform paradigm to succinctly encode various families of trees
cites work: A simple storage scheme for strings achieving entropy bounds
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Path queries on functions
cites work: Succinct ordinal trees with level-ancestor queries
cites work: Q4471381
cites work: Asymptotically Optimal Encodings of Range Data Structures for Selection and Top- k Queries
cites work: Succinct ordinal trees based on tree covering
cites work: Succinct Data Structures for Path Queries
cites work: Data Structures for Path Queries
cites work: Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
cites work: Succinct representations of permutations and functions
cites work: Succinct representation of balanced parentheses and static trees
cites work: Time-Optimal Top-$k$ Document Retrieval
cites work: Space-efficient data-analysis queries on grids
cites work: Fully functional static and dynamic succinct trees
cites work: Succinct representation of labeled trees
DOI: 10.1016/J.TCS.2018.10.021
description: scientific article; zbMATH DE number 7050144