Skyline query processing has recently received a lot of attention in database and data mining communities. However, most existing algorithms consider how to efficiently process skyline queries from base tables. Obviou...Skyline query processing has recently received a lot of attention in database and data mining communities. However, most existing algorithms consider how to efficiently process skyline queries from base tables. Obviously, when the data size and the number of skyline queries increase, the time cost of skyline queries will increase exponentially, which will seriously influence the query efficiency. Motivated by the above, in this paper, we consider improving the query efficiency via skyline views and propose a cost-based algorithm(abbr. CA) to efficiently select the optimal set of skyline views for storage. The CA algorithm mainly includes two phases:(i) reduce the skyline views selection to the minimum steiner tree problem and obtain the approximate optimal set AOS of skyline views, and(ii) adjust AOS and produce the final optimal set FOS of skyline views based on the simulated annealing. Moreover, in order to improve the extendibility of the CA algorithm, we implement it based on the map/reduce distributed computation model in cloud computing environments. The detailed theoretical analyses and extensive experiments demonstrate that the CA algorithm is both efficient and effective.展开更多
In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensio...In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensional space is proposed. This method takes the advantages of Hilbert R-tree which combines R-tree and Hilbert curve with high efficiency and dimensionality reduction. According to the number of query points, the proposed method in static query point environment is divided into single query point of SSQ method(SQ-HSKY algorithm) and multi-query points of SSQ method(MQP-HSKY algorithm). The SQ-HSKY method uses the spatial relationship between objects to propose pruning strategy and the skyline set in the filtering and refining process are computed. The MQP-HSKY method uses the topological relationship between data points and query points to prune non skyline points and generate the dominant decision circle to obtain the global skyline set. Theoretical study and experiments confirm the effectiveness and superiority of these methods on the skyline query.展开更多
As one of the commonly used queries in modern databases, skyline query has received extensive attention from database research community. The uncertainty of the data in wireless sensor networks makes the corresponding...As one of the commonly used queries in modern databases, skyline query has received extensive attention from database research community. The uncertainty of the data in wireless sensor networks makes the corresponding skyline uncertain and not unique. This paper investigates the Pr-Skyline problem, i.e., how to compute the skyline with the highest existence probability in a computational and energy-efficient way. We formulate the problem and prove that it is NP-Complete and cannot be approximated in a given expression. However, the proposed algorithm SKY-SEARCH with pruning techniques can guarantee the computational efficiency given relatively large input size, while the filter-based distributed optimization strategy significantly reduces the transmission cost and the required storage space of the sensor nodes. Extensive experiments verify the efficiency and scalability of SKY-SEARCH and the distributed optimizing strategy.展开更多
在移动互联网环境下,空间文本skyline查询可以有效支持用户在空间和关键词方面的查询。随着需求的多样性,基于用户经常会同时考虑空间距离、数值型信息、关键词和时间等因素对查询结果的影响,提出了基于时间的空间文本关键词skyline查询...在移动互联网环境下,空间文本skyline查询可以有效支持用户在空间和关键词方面的查询。随着需求的多样性,基于用户经常会同时考虑空间距离、数值型信息、关键词和时间等因素对查询结果的影响,提出了基于时间的空间文本关键词skyline查询(Time based Spatial Text Keyword Skyline Query,TSTKSQ),用来查找在空间、数值、关键词和时间都满足条件的优秀对象,设计了基于时间的空间文本关键词skyline查询的索引结构STTR-Tree,提出了关键词、时间和时空关键词相关性的评价函数,在裁剪策略的基础上提出了skyline查询算法。通过实验结果分析,验证了算法的准确性和有效性。展开更多
基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline增量的计算等进行了系统优化,...基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline增量的计算等进行了系统优化,使算法在通信负荷与反应延迟上达到了较好的综合性能.理论分析证明,在所有基于非共享策略的算法中,BOCS算法通信最优.大量的对比实验结果也表明,所提出的算法高效、稳定且具有良好的可扩展性.展开更多
基金supported by the National Natural Science Foundation of China(No.61772366)the Natural Science Foundation of Shanghai(No.17ZR1445900)the program of Further Accelerating the Development of Chinese Medicine Three Year Action of Shanghai(2014-2016)ZY3-CCCX-3-6002
文摘Skyline query processing has recently received a lot of attention in database and data mining communities. However, most existing algorithms consider how to efficiently process skyline queries from base tables. Obviously, when the data size and the number of skyline queries increase, the time cost of skyline queries will increase exponentially, which will seriously influence the query efficiency. Motivated by the above, in this paper, we consider improving the query efficiency via skyline views and propose a cost-based algorithm(abbr. CA) to efficiently select the optimal set of skyline views for storage. The CA algorithm mainly includes two phases:(i) reduce the skyline views selection to the minimum steiner tree problem and obtain the approximate optimal set AOS of skyline views, and(ii) adjust AOS and produce the final optimal set FOS of skyline views based on the simulated annealing. Moreover, in order to improve the extendibility of the CA algorithm, we implement it based on the map/reduce distributed computation model in cloud computing environments. The detailed theoretical analyses and extensive experiments demonstrate that the CA algorithm is both efficient and effective.
基金Supported by the National Natural Science Foundation of China(No.61872105)the Science and Technology Research Project of Heilongjiang Provincial Education Department(No.1253lz004)the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China(No.LC2018030)
文摘In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensional space is proposed. This method takes the advantages of Hilbert R-tree which combines R-tree and Hilbert curve with high efficiency and dimensionality reduction. According to the number of query points, the proposed method in static query point environment is divided into single query point of SSQ method(SQ-HSKY algorithm) and multi-query points of SSQ method(MQP-HSKY algorithm). The SQ-HSKY method uses the spatial relationship between objects to propose pruning strategy and the skyline set in the filtering and refining process are computed. The MQP-HSKY method uses the topological relationship between data points and query points to prune non skyline points and generate the dominant decision circle to obtain the global skyline set. Theoretical study and experiments confirm the effectiveness and superiority of these methods on the skyline query.
文摘As one of the commonly used queries in modern databases, skyline query has received extensive attention from database research community. The uncertainty of the data in wireless sensor networks makes the corresponding skyline uncertain and not unique. This paper investigates the Pr-Skyline problem, i.e., how to compute the skyline with the highest existence probability in a computational and energy-efficient way. We formulate the problem and prove that it is NP-Complete and cannot be approximated in a given expression. However, the proposed algorithm SKY-SEARCH with pruning techniques can guarantee the computational efficiency given relatively large input size, while the filter-based distributed optimization strategy significantly reduces the transmission cost and the required storage space of the sensor nodes. Extensive experiments verify the efficiency and scalability of SKY-SEARCH and the distributed optimizing strategy.
文摘在移动互联网环境下,空间文本skyline查询可以有效支持用户在空间和关键词方面的查询。随着需求的多样性,基于用户经常会同时考虑空间距离、数值型信息、关键词和时间等因素对查询结果的影响,提出了基于时间的空间文本关键词skyline查询(Time based Spatial Text Keyword Skyline Query,TSTKSQ),用来查找在空间、数值、关键词和时间都满足条件的优秀对象,设计了基于时间的空间文本关键词skyline查询的索引结构STTR-Tree,提出了关键词、时间和时空关键词相关性的评价函数,在裁剪策略的基础上提出了skyline查询算法。通过实验结果分析,验证了算法的准确性和有效性。
基金Supported by the National Natural Science Foundation of China under Grant Nos.60673138,60603046(国家自然科学基金)the Program for New Century Excellent Talents in University of China(新世纪优秀人才支持计划)the Program for Excellent Talents in Beijing of China under Grant No.35607025,(北京市优秀人才培养资助项目)
文摘基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline增量的计算等进行了系统优化,使算法在通信负荷与反应延迟上达到了较好的综合性能.理论分析证明,在所有基于非共享策略的算法中,BOCS算法通信最优.大量的对比实验结果也表明,所提出的算法高效、稳定且具有良好的可扩展性.
