On Approximate Colored Path Counting

Given an ordinal tree T on n nodes in which each node is assigned a color from \(\{0,1,\ldots ,C-1\}\) , an approximate colored path counting query asks for an approximation of the number, \(\texttt{occ}\) , of distinct colors assigned to nodes in a query path. We first present data structures that can compute a 2-approximate answer, i.e., a number in \([\texttt{occ}, 2\texttt{occ}]\) , and achieve three different time/space trade-offs: i) an O(n)-word structure with \(O(\lg ^{\lambda } n)\) query time for any constant \(0<\lambda <1\) , ii) an \(O(n\lg \lg n)\) -word structure with \(O(\lg \lg n)\) query time and iii) an \(O(n\lg ^{\lambda } n)\) -word structure with O(1) query time. The first trade-off beats the \(O(\lg n/\lg \lg n)\) query time of the linear-word 2-approximate structure in previous work. We then design an O(n)-word structure which can compute in \(O(\epsilon ^{-2}\lg n)\) time a \((1\pm \epsilon )\) -approximate answer, i.e, a number in \([(1-\epsilon )\texttt{occ}, (1+\epsilon ) \texttt{occ}]\) , for any \(\epsilon \in (0,1)\) . Previously, when the space cost is O(n) words, the only known solution computes a \((1\pm \epsilon )\) -approximate answer in \(O({\epsilon ^{-4}}\lg ^2 n)\) time with success probability no less than \(1-\delta \) , where \(\delta \) is an arbitrary constant in (0, 1); our solution not only has faster query time but also always returns a \((1\pm \epsilon )\) -approximation. When designing \((1\pm \epsilon )\) -approximate solutions, our techniques also yield an O(n)-word structure that can answer a colored type-2 path counting query in \(O(\texttt{occ})\) time; this query reports the number of occurrences of each distinct color in a query path. This result improves the best previous linear-word solution in which the query time is \(O(\texttt{occ}\lg \lg n)\) .