Adaptive Range Counting and Other Frequency-Based Range Query Problems

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii We consider variations of range searching in which, given a query range, our goal is to compute some function based on frequencies of points that lie in the range. The most basic such computation involves counting the number of points in a query range. Data structures that compute this function solve the well-studied range counting problem. We consider adaptive and approximate data structures for the 2-D orthogonal range counting problem under the w-bit word RAM model. The query time of an adaptive range counting data structure is sensitive to k, the number of points being counted. We give an adaptive data structure that requires O(n log log n) space and O(log log n+logw k) query time. Non-adaptive data structures on the other hand require Ω(logw n) query time (Pătraşcu, 2007). Our specific bounds are interesting for two reasons. First, when k = O(1), our bound