Path queries on functions (Q1740690)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path queries on functions |
scientific article |
Statements
Path queries on functions (English)
0 references
2 May 2019
0 references
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.
0 references
succinct data structures
0 references
integer functions
0 references
range queries
0 references
trees
0 references
permutations
0 references