Colored top-K range-aggregate queries

• We consider colored top-K range-aggregate query, where color indicates a category.
• We consider colored, weighted points and intervals as input objects.
• We report best k colors with respect to aggregate functions Max/Min and Count.
• We propose efficient output sensitive solutions for functions Max/Min and Count.
• Techniques include transformation to the uncolored top-K problem and persistence.

Top-K query processing is an important building block for ranked retrieval, with numerous applications. Top-K queries return a ranked set of the k best data objects based on the ranks/scores of the objects, assigned by some ranking/scoring function. In many applications, including databases and network routing, input objects are partitioned into categories denoted by distinct colors and a query asks for reporting the set of top-K categories of objects based on different aggregation functions like “Max/Min”, “Count”, etc.We consider a set of problems defined on colored geometric objects (points/intervals) in RdRd (respectively in [0,U]2[0,U]2). We are given a set S of n   colored geometric objects in RdRd (respectively in [0,U]2[0,U]2). Optionally, each object p   has a weight w(p)⩾0w(p)⩾0. The number of colors is m⩽nm⩽n. For any color c and a query q  , let f(c,q)f(c,q) be an aggregation function defined over c-colored objects intersecting q  . For a given k∈[1…n]k∈[1…n], we define top  -K(q)K(q) to be the set of k colors with the highest k  f(c,q)f(c,q) values among the distinct colors of the objects intersecting q. (If the number of distinct colors in q is less than k, we simply include all such colors in top  -K(q)K(q).) Our goal is to preprocess S into a data structure so that given a query q   and an integer k∈[1…n]k∈[1…n], the colors in top  -K(q)K(q) can be reported efficiently.Efficient solutions are provided to instances of the above general problem in cases where (i) S is a set of colored points, q   is a query interval and f(c,q)f(c,q) is the maximum/minimum weight of points of color c in q, (ii) S is a set of colored intervals, q   is a query point and f(c,q)f(c,q) is the count of intervals of color c stabbed by q, (iii) S is a set of colored intervals, q   is a query point and f(c,q)f(c,q) is the maximum/minimum weight of intervals of color c stabbed by q  . In this paper static solutions are provided for case (i) in all d⩾1d⩾1 and for case (ii) and (iii) in d=1d=1 and dynamic solution is provided for case (i) in d=1d=1. For case (iii) a static solution is also provided in [0,U]2[0,U]2. Techniques include transformation to the uncolored top-K problem and persistence.