Path queries on functions

Abstract

Let f: [1.n] → [1.n] be a function, and i: [1.n] → [1.σ] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For example, we can find the minimum label in fk(i) for a given i and any k ≥ 0 in a given range [k1.k2], using nlgn + O(n) bits, or the minimum label in f-k(i) for a given i and k > 0, using 2n lg n + O(n) bits, both in time O(lg n/lg lg n). By using n lg σ + o(n lg σ) further bits, we can also count, within the same time, the number of labels within a range, and report each element with such labels in O(1 + lg σ/lg lg n) additional time. Several other possible queries are considered, such as top-t queries and τ-majorities.