In this paper we consider a special case of orthogonal point counting queries, called queries with distinct constraints. A d-dimensional orthogonal query range Q = [b1;b2] [b3;b4] ::: [b2d 1;b2d] is a range with r distinct constraints if there are r distinct values among b1, b2, :::, b2d. We describe a data structure that supports orthogonal range counting queries with r distinct constraints. We show that the space and query time complexity of such queries depend only on the number of distinct constraints r even if r is much smaller than d. An application of queries with r distinct constraints to persistent range counting is also considered.
['J. Ian Munro', 'Yakov Nekrich', 'Sharma V. Thankachan']
Range Counting with Distinct Constraints.