Density-based similarity measures for content based search

We consider the query by multiple example problem where the goal is to identify database samples whose content is similar to a collection of query samples. To assess the similarity we use a relative content density which quantifies the relative concentration of the query distribution to the database distribution. If the database distribution is a mixture of the query distribution and a background distribution then it can be shown that database samples whose relative content density is greater than a particular threshold ¿ are more likely to have been generated by the query distribution than the background distribution. We describe an algorithm for predicting samples with relative content density greater than ¿ that is computationally efficient and possesses strong performance guarantees. We also show empirical results for applications in computer network monitoring and image segmentation.