Lecture Notes: Range Counting

So far all the problems we have discussed are reporting problems, where we want to report the data elements qualifying a predicate. There is another class of problems that aim at outputting a constant amount of information to summarize a subset of elements. In this lecture, we will discuss such a problem called range counting. Let P be a set of N points in R2. Given an axis-parallel rectangle q ∈ R, a range count query reports the number of points in P that are covered by q. The goal is to pre-process P into a data structure such that all queries can be answered efficiently. Although we defined the problem by specifying q as a 4-sided rectangle, it is sufficient to focus on 2-sided q in the form of (−∞, x] × (−∞, y]. A moment of thinking will reveal that the result of a 4-sided query can be obtained from four 2-sided queries. We will assume that each (computer) word has at least log2N bits, which is a common assump-tion in the literature with good justifications. Most algorithms in computer science (including the ones to be presented below) implicitly assume that each real number or integer fits in one word. Notice that log2N bits are needed to represent N itself. So a CPU with word length less than this many bits cannot even represent the problem size (which is also the largest result size for a range query) in one word. Furthermore, the N input points can have different x-coordinates. Hence, the word length should be at least long enough so that we can represent N distinct x-coordinates, thus necessitating log2N bits. We will introduce the CRB-tree [1] which uses O(N/B) space, and answers a range count query in O(logB N) I/Os. We will learn a technique that crams multiple integers into a single word— something that we have not attempted so far in this course. As usual, we will assume that P is in general position such that no two points in P share the same x- or y- coordinate.