Applications of Quick-Combine for Ranked Query Models.
Wolf‐Tilo Balke, Werner Kießling, Ulrich Güntzer · OPUS (Augsburg University) · 2000
In digital libraries queries are often based on the similarity of objects, using several feature attributes like colors, texture or full-text searches.Such multi-feature queries return a ranked result set instead of exact matches.Recently we presented a new algorithm called Quick-Combine [5] for combining multi-feature result lists, guaranteeing the correct retrieval of the k top-ranked results.As benchmarks on practical data promise that we can dramatically improve performance, we want to discuss interesting applications of Quick-Combine in different areas.The applications for the optimization in ranked query models are manifold.Generally speaking we believe that all kinds of federated searches can be supported like e.g.content-based retrieval, knowledge management systems or multi-classifier combination. Query Optimization For Ranked Query ModelsToday's handling of multimedia data in information systems such as images, video or audio files poses an increasingly demanding problem.The query evaluation model typically does not retrieve a set of exact matches but rather a ranked result set, where an aggregated score is attached to each object returned.Only a few topranked results are normally of interest to the user.A query could for example ask for the top 10 objects from an image collection that are most similar to a fixed image in terms of visual properties; a query type which is often referred to as 'query by visual example'.Query optimization needs to be adapted to this essentially different query model for multimedia data.Some systems have already been implemented, e.g.visual retrieval systems like IBM's QBIC [1] or Virage's VIR [2].Database applications and middlewares like GARLIC [3] or the HERON project [4] have already started to use the capabilities of visual retrieval.A major challenge in all of these systems is that similarity between different objects cannot be defined precisely.To handle queries on similarity different kinds of information on the multimedia objects have to be stored.For example in the case of images this could be color histograms, shapes of occurring objects, features on textures and layout or related fulltext information describing the object.Queries on similarity do not have to focus on one single feature.In general multimedia queries will refer to at least some different features simultaneously.According to a potentially weighted combining function for each database object an aggregated score value is computed.The results are then sorted according to their scores and are returned with a rank number -the top-ranked object has the best score value of the entire database and so on.A query focusing on a single feature is called atomic.Complex multimedia queries are combinations of atomic subqueries.