Grid-Index Algorithm for Reverse Rank Queries
Grid-Index Algorithm for Reverse Rank Queries
复制标题
DOI：
10.5441/002/edbt.2017.28
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yuyang Dong;Hanxiong Chen;J. Yu;K. Furuse;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Yuyang Dong;Hanxiong Chen;J. Yu;K. Furuse;H. Kitagawa
在支持等级的查询处理中，反向等级查询已经引起了人们的极大兴趣。反向排序查询可以根据单个客户的偏好为给定产品找到匹配的客户。结果被用于许多现实生活中的应用，例如市场分析和产品植入。反向排序查询的有效处理是具有挑战性的，因为它需要考虑给定用户偏好数据集和产品数据集的组合。目前，有两种典型的反向排序查询：反向TOP-K和反向k-RANK。两者都喜欢一流的产品，它们最有效的算法都有一个共同的方法，即使用R-树对数据集进行索引和修剪。这种基于树的算法在高维数据中的性能急剧下降，而高维数据在实际应用中具有重要意义。本文提出了一种高效的扫描算法--网格索引算法(GIR)，用于高效地处理反向排序查询。GIR算法使用近似值索引来节省扫描时的计算量，并且只需要很小的存储开销。我们的理论分析保证了效率，实验结果证实了GIR在高维应用中比基于树的方法具有更好的性能。容器服务概念·计算理论→数据库查询处理与优化(理论)；c？2017，版权归作者所有。在Proc中发布。第20届扩展数据库技术国际会议，2017年3月21-24日，意大利威尼斯：ISBN978-3-89318-073-8，在OpenProceedings.org上。根据知识共享许可CC-by-NC-ND 4.0的条款，允许分发本文。图1：RTK和RKR查询示例。(A)：用户喜爱的TOP2手机。(B)：每部电话的RT-2。(C)：每个电话的秩列表和R1-R。
In Rank-aware query processing, reverse rank queries have already attracted significant interests. Reverse rank queries can find matching customers for a given product based on individual customers’ preference. The results are used in numerous real-life applications, such as market analysis and product placement. Efficient processing of reverse rank queries is challenging because it needs to consider the combination on the given data set of user preferences and the data set of products. Currently, there are two typical reverse rank queries: Reverse top-k and reverse k-ranks. Both prefer top-ranking products and the most efficient algorithms for them have a common methodology that indexes and prunes the data set using R-trees. This kind of tree-based algorithms suffers the problem that their performance in high-dimensional data declines sharply while high-dimensional data are significant for real-life applications. In this paper, we propose an efficient scan algorithm, named Grid-index algorithm (GIR), for processing reverse rank queries efficiently. GIR algorithm uses an approximate values index to save computations in scanning and only requires a little memory cost. Our theoretical analysis guarantees the efficiency and the experimental results confirm that GIR has superior performance compared to tree-based methods in high-dimensional applications. CCS Concepts •Theory of computation → Database query processing and optimization (theory); c ©2017, Copyright is with the authors. Published in Proc. 20th International Conference on Extending Database Technology (EDBT), March 21-24, 2017 Venice, Italy: ISBN 978-3-89318-073-8, on OpenProceedings.org. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0 Figure 1: Example for RTK and RKR queries. (a): the top2 cell phones appreciated by users. (b): the RT-2 of each phone. (c): the rank list and the R1-R of each phone.