Efficient Top-k Spatial Distance Joins
Efficient Top-k Spatial Distance Joins
复制标题
DOI：
10.1007/978-3-642-40235-7_1
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Shuyao Qi;Panagiotis Bouros;N. Mamoulis
中科院分区：
文献类型：
--
作者：
Shuyao Qi;Panagiotis Bouros;N. Mamoulis
考虑两组空间对象rand，其中每个对象被分配一个分数（例如，排名）。给定空间距离阈值ε和整数，top-k空间距离连接（k- SDJ）返回k对对象，它们在所有对象对中具有最高的组合分数（基于聚合函数γ） inR×Swhich的空间距离最多为ε。尽管该查询具有实际应用价值，但在过去并没有得到足够的重视。在本文中，我们通过提出利用来自对象的位置和分数信息的方法来填补这一空白，通过访问有限数量的对象来实现顶连接计算。大量的实验表明，通过对象分数访问mrandsordered数据块，然后使用基于ar树的模块将它们连接起来的技术在实践中表现最佳，并且在很大程度上优于替代解决方案。
Consider two sets of spatial objectsRandS, where each object is assigned a score (e.g., ranking). Given a spatial distance thresholdεand an integerk, the top-kspatial distance join (k- SDJ) returns thekpairs of objects, which have the highest combined score (based on an aggregate functionγ) among all object pairs inR×Swhich have spatial distance at mostε. Despite the practical application value of this query, it has not received adequate attention in the past. In this paper, we fill this gap by proposing methods that utilize both location and score information from the objects, enabling top-kjoin computation by accessing a limited number of objects. Extensive experiments demonstrate that a technique which accesses blocks of data fromRandSordered by the object scores and then joins them using an aR-tree based module performs best in practice and outperforms alternative solutions by a wide margin.