RC-Index: Diversifying Answers to Range Queries
RC-Index: Diversifying Answers to Range Queries
复制标题
DOI：
10.14778/3192965.3192969
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Yue Wang;A. Meliou;G. Miklau
中科院分区：
文献类型：
--
作者：
Yue Wang;A. Meliou;G. Miklau
查询结果多样化广泛应用于数据探索、Web搜索和推荐系统中。返回多样化的查询结果的问题包括找到一个小的子集的有效的查询答案是代表性的，彼此不同，通常量化的多样性得分。大多数现有的查询多样化技术首先计算所有有效的查询结果，然后找到一个不同的子集。当有效查询结果的集合很大时，这些技术是低效的。其他工作已经提出了针对受限应用程序设置的有效解决方案，其中结果在多个查询之间共享。在本文中，我们的目标是支持结果多样化的一般范围查询在一个单一的关系。我们提出了RC索引，一种新的索引结构，通过减少必须由数据库检索的项目的数量来实现效率，以形成所需大小的不同集合（对于100万个项目的数据集，大约1秒）。此外，我们证明了RC指数提供了强近似保证。据我们所知，这是第一个基于索引的多样化方法，保证范围查询的近似比。
Query result diversification is widely used in data exploration, Web search, and recommendation systems. The problem of returning diversified query results consists of finding a small subset of valid query answers that are representative and different from one another, usually quantified by a diversity score. Most existing techniques for query diversification first compute all valid query results and then find a diverse subset. These techniques are inefficient when the set of valid query results is large. Other work has proposed efficient solutions for restricted application settings, where results are shared across multiple queries. In this paper, our goal is to support result diversification for general range queries over a single relation. We propose the RC-Index, a novel index structure that achieves efficiency by reducing the number of items that must be retrieved by the database to form a diverse set of the desired size (about 1 second for a dataset of 1 million items). Further, we prove that an RC-Index offers strong approximation guarantees. To the best of our knowledge, this is the first index-based diversification method with a guaranteed approximation ratio for range queries.