Data Structures for Colored Counting in Grids and Trees

Abstract

In this thesis, we design data structures for colored counting queries. First, we consider the colored 2D orthogonal range counting problem and present four different time-space tradeoffs. Second, we consider the batched colored path counting problem. By reducing this problem to sparse matrix multiplication, we show a solution that answers n colored path counting queries in O(n^1.4071) time. Another related problem, batched path mode queries, is also considered. We present a solution that answers n queries in O(n^1.483814) time using the fast computation of min-plus products over structured matrices. Third, we design data structures for 2-approximate colored path counting with O(n) space and O(lg^lambda ⁡n ) query time, O(n lg⁡ lg⁡ n) space and O(lg⁡ lg n) time and O(n lg^lambda n) space and O(1) time, respectively, for any constant 0<lambda<1. We also present a linear space data structure that supports (1+-epsilon)-approximate colored path counting in O(epsilon^(-2) lg⁡ n) time, for any 0<epsilon<1.