In this paper, we formulate a class of colored range query problems to model the multi-dimensional range queries in the presence
of categorical information. By applying appropriate sketching techniques on our framework, we obtained efficient data structures
that provide approximate solutions to these problems. In addition, the framework can be employed to attack other related problems
by finding the appropriate summary structures.
The work described in this paper was fully supported by a grant from the Research Grants Council of the Hong Kong Special
Administrative Region, China [Project No. CityU 1198/03E].