Path queries on functions

Let f: [ 1. . n ] → [ 1. . n ] be a function, and ℓ: [ 1. . n ] → [ 1. . σ ] indicate a label assigned to each element of the domain. We design several compact data structures that answer various kinds of summary queries on the labels of paths in f. For example, we can find either the minimum label in f k ( i ) for a given i and any k ≥ 0 in a given range [ k 1. . k 2 ], or the minimum label in f − k ( i ) for a given i and k > 0, using n lg ⁡ n + n lg ⁡ σ + o ( n lg ⁡ n ) bits and time O ( α ( n ) ), the inverse Ackermann function. Within similar space we can count, in time O ( lg ⁡ n / lg ⁡ lg ⁡ n ), the number of labels within a range, and report each element with such labels in O ( lg ⁡ n / lg ⁡ lg ⁡ n ) additional time. Several other tradeoffs and possible queries are considered, such as selection, top-r queries and τ-majorities. Finally, we consider queries that allow us navigate on the graph of the function, such as the nearest common successor of two elements, or the nearest successor or predecessor of an element within a range of labels.

Authors

• Travis Gagie
• Meng He
• Gonzalo Navarro

Keywords

• Succinct data structures
• Integer functions
• Range queries
• Trees and permutations