Q+Tree: An Efficient Quad Tree based Data Indexing for Parallelizing Dynamic and Reverse Skylines
Q+Tree: An Efficient Quad Tree based Data Indexing for Parallelizing Dynamic and Reverse Skylines
复制标题
DOI：
10.1145/2983323.2983764
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Md. Saiful Islam;Chengfei Liu;Wenny Rahayu;Tarique Anwar
中科院分区：
文献类型：
--
作者：
Md. Saiful Islam;Chengfei Liu;Wenny Rahayu;Tarique Anwar
天际线查询在许多领域的多标准决策应用中起着重要作用。给定一个对象数据集，Skyline查询检索数据集中任何其他数据对象主导的数据对象。与标准的天际线查询不同，直接比较数据对象的不同方面，动态和反向的天际线查询遵循附近语义的问题，这可以通过比较数据对象的相对距离W.R.T.实现。给定的查询。但是，有许多关于平行标准天际线查询的作品，但只有少数作品专门用于动态和反向天际线查询的并行计算。本文介绍了一个高效的基于四轮树的数据索引方案，称为Q+树，用于平行动态和反向天际线查询的计算。我们将Q+树的性能与现有的基于Quad-Tree的索引方案进行了比较。我们还提出了几种优化启发式方法，以进一步提高两个索引方案的性能。实验和合成数据集的实验验证了所提出的索引方案和优化启发式方法的效率。
Skyline queries play an important role in multi-criteria decision making applications of many areas. Given a dataset of objects, a skyline query retrieves data objects that are not dominated by any other data object in the dataset. Unlike standard skyline queries where the different aspects of data objects are compared directly, dynamic and reverse skyline queries adhere to the around-by semantics, which is realized by comparing the relative distances of the data objects w.r.t. a given query. Though, there are a number of works on parallelizing the standard skyline queries, only a few works are devoted to the parallel computation of dynamic and reverse skyline queries. This paper presents an efficient quad-tree based data indexing scheme, called Q+Tree, for parallelizing the computations of the dynamic and reverse skyline queries. We compare the performance of Q+Tree with an existing quad-tree based indexing scheme. We also present several optimization heuristics to improve the performance of both of the indexing schemes further. Experimentation with both real and synthetic datasets verifies the efficiency of the proposed indexing scheme and optimization heuristics.