Path queries on functions

DOI10.1016/J.TCS.2018.10.021MaRDI QIDQ1740690zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Meng He, Gonzalo Navarro

Publication date 2 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.10.021

zbMATH Keywords

integer functionspermutationsrange queriessuccinct data structurestrees

Mathematics Subject Classification ID

Data structures (68P05)

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.

Recommendations

• Path queries on functions
• Succinct indices for path minimum, with applications
• Succinct indices for path minimum, with applications to path reporting
• Tree path majority data structures
• Automata, Languages and Programming

Cites work

• A simple storage scheme for strings achieving entropy bounds
• A uniform paradigm to succinctly encode various families of trees
• Asymptotically optimal encodings of range data structures for selection and top-k queries
• Data structures for path queries
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Orthogonal range searching on the RAM, revisited
• Path queries on functions
• Range majorities and minorities in arrays
• Representing trees of higher degree
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Space-efficient data-analysis queries on grids
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Data Structures for Path Queries
• Succinct indices for path minimum, with applications to path reporting
• Succinct ordinal trees based on tree covering
• Succinct ordinal trees with level-ancestor queries
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct representation of balanced parentheses and static trees
• Succinct representation of labeled trees
• Succinct representations of permutations and functions
• Theory and practice of monotone minimal perfect hashing
• Time-optimal top-k document retrieval

Cited in

(2)

• Path queries on functions
• Tree path majority data structures

This page was built for publication: Path queries on functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1740690)