Computer Science – Data Structures and Algorithms
Scientific paper
2010-07-08
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper we describe a new efficient (in fact optimal) data structure for the {\em top-$K$ color problem}. Each element of an array $A$ is assigned a color $c$ with priority $p(c)$. For a query range $[a,b]$ and a value $K$, we have to report $K$ colors with the highest priorities among all colors that occur in $A[a..b]$, sorted in reverse order by their priorities. We show that such queries can be answered in $O(K)$ time using an $O(N\log \sigma)$ bits data structure, where $N$ is the number of elements in the array and $\sigma$ is the number of colors. Thus our data structure is asymptotically optimal with respect to the worst-case query time and space. As an immediate application of our results, we obtain optimal time solutions for several document retrieval problems. The method of the paper could be also of independent interest.
Karpinski Marek
Nekrich Yakov
No associations
LandOfFree
Top-K Color Queries for Document Retrieval does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Top-K Color Queries for Document Retrieval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Top-K Color Queries for Document Retrieval will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-102934