Gao, Younan2023-08-312023-08-312023-08-31http://hdl.handle.net/10222/82902In 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.en2D colored orthogonal range countingstabbing queriesgeometric data structuresmin-plus productpath queriescolored path countingpath mode queriesapproximate colored path counting