The spatial skyline queries
The spatial skyline queries
复制标题
DOI：
--
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
M. Sharifzadeh;C. Shahabi
中科院分区：
文献类型：
--
作者：
M. Sharifzadeh;C. Shahabi
在本文中，我们首次介绍了空间天际线查询的概念（SSQ）。距离查询点的距离。空间统治取决于查询点的位置Q SSQ在我们的方法背后的主要直觉和新颖性等几个领域中都有应用。在p和q中的所有点对中。 |解决方案大小和Q的凸壳的顶点数量分别为静态查询点和一个算法VCS2提出两种算法B2S2和VS2，用于流Q，其点随时间变化的位置（例如，移动）会随时间变化的位置而变化。 VCS2利用Q的变化模式，以避免天际线的不必要的重新计算，因此有效地执行了我们的广泛实验。基于B2S2和基于Voronoi的VS2 OUT在处理时间方面执行最佳竞争者方法（在大多数情况下，要好得多4-6倍）。
In this paper, for the first time, we introduce the concept of Spatial Skyline Queries (SSQ). Given a set of data points P and a set of query points Q each data point has a number of derived spatial attributes each of which is the point's distance to a query point. An SSQ retrieves those points of P which are not dominated by any other point in P considering their derived spatial attributes. The main difference with the regular skyline query is that this spatial domination depends on the location of the query points Q SSQ has application in several domains such as emergency response and online maps. The main intuition and novelty behind our approaches is that we exploit the geometric properties of the SSQ problem space to avoid the exhaustive examination of all the point pairs in P and Q. Consequently, we reduce the complexity of SSQ search from O(|P|2|Q|) to O(|S|2|C|+√|P|), where |S| and |C| are the solution size and the number of vertices of the convex hull of Q, respectively.We propose two algorithms, B2S2 and VS2, for static query points and one algorithm, VCS2, for streaming Q whose points change location over time (e.g., are mobile). VCS2 exploits the pattern of change in Q to avoid unnecessary re-computation of the skyline and hence efficiently perform updates. Our extensive experiments using real-world datasets verify that both R-tree-based B2S2 and Voronoi-based VS2 out perform the best competitor approach in terms of processing time by a wide margin (4-6 times better in most cases).