Top-K color queries for document retrieval

摘要: In this paper we describe a new efficient (in fact optimal) data structure for the top-K color problem. Each element of an array A is assigned c with priority p(c). For query range [a, b] and value K, have to report K colors highest priorities among all that occur in A[a..b], sorted reverse order by their priorities. We show such queries can be answered O(K) time using O(N log σ) bits structure, where N number elements σ colors. Thus our asymptotically optimal respect worst-case space. As immediate application results, obtain solutions several document retrieval problems. The method could also independent interest.