Optimizing top-k selection queries over multimedia repositories
Optimizing top-k selection queries over multimedia repositories
复制标题
优化多媒体存储库的 top-k 选择查询
DOI：
--
复制
发表时间：
2004
影响因子：
8.9
通讯作者：
A. Marian
中科院分区：
文献类型：
--
作者：
S. Chaudhuri;L. Gravano;A. Marian
具有多种属性类型（例如，图像、文本）的多媒体对象存储库正变得越来越普遍。对这些属性的查询通常不仅请求一组对象，就像在传统的关系查询模型中那样（过滤），而且还请求与每个对象相关联的匹配等级，这表明对象与选择条件的匹配程度（排名）。此外，与关系模型不同的是，用户可能只需要k个排名靠前的对象来进行相对较小的k选择查询。除了查询模型的差异之外，多媒体存储库的另一个特点是，它们可能只允许通过索引访问每个对象的属性。我们研究了如何优化多媒体存储库上top-k选择查询的处理。存储库的访问特征和上述查询模型导致了查询优化中的新问题。特别是，用于搜索存储库的索引的选择对处理过滤条件的成本有很大影响。我们定义了一个搜索最小的执行空间，即搜索的索引集是最小的。尽管在搜索最小执行空间中选择最优计划的一般问题是np困难的，但我们提出了一种有效的算法，当查询中的谓词是独立的时，它可以最优地解决我们的成本模型和执行空间方面的问题。我们还表明，在许多情况下，优化top-k选择查询的问题可以看作是评估更传统的选择条件的问题。因此，这两个问题可以看作是一个扩展的过滤问题，查询处理和优化技术可以适用于这个问题。
Repositories of multimedia objects having multiple types of attributes (e.g., image, text) are becoming increasingly common. A query on these attributes will typically, request not just a set of objects, as in the traditional relational query model (filtering), but also a grade of match associated with each object, which indicates how well the object matches the selection condition (ranking). Furthermore, unlike in the relational model, users may just want the k top-ranked objects for their selection queries for a relatively small k. In addition to the differences in the query model, another peculiarity of multimedia repositories is that they may allow access to the attributes of each object only through indexes. We investigate how to optimize the processing of top-k selection queries over multimedia repositories. The access characteristics of the repositories and the above query model lead to novel issues in query optimization. In particular, the choice of the indexes used to search the repository strongly influences the cost of processing the filtering condition. We define an execution space that is search-minimal, i.e., the set of indexes searched is minimal. Although the general problem of picking an optimal plan in the search-minimal execution space is NP-hard, we present an efficient algorithm that solves the problem optimally with respect to our cost model and execution space when the predicates in the query are independent. We also show that the problem of optimizing top-k selection queries can be viewed, in many cases, as that of evaluating more traditional selection conditions. Thus, both problems can be viewed together as an extended filtering problem to which techniques of query processing and optimization may be adapted.