Top-k spatial keyword queries on road networks
Top-k spatial keyword queries on road networks
复制标题
DOI：
10.1145/2247596.2247617
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
João B. Rocha-Junior;K. Nørvåg
中科院分区：
文献类型：
--
作者：
João B. Rocha-Junior;K. Nørvåg
随着GPS设备的普及，人们对基于位置的查询越来越感兴趣。在这种情况下，一个有趣的问题是处理top-k空间关键字查询。给出一组具有文本描述的对象（例如，餐馆的菜单）、查询位置（纬度和经度）以及一组查询关键字，前k个空间关键字查询返回根据到查询位置的距离和与查询关键字的文本相关性排序的k个最佳对象。迄今为止，对这一问题的研究都是假设欧氏空间。为了有效地处理这样的查询，结合R-树和倒排文件的空间文本索引。然而，对于大多数真实的应用程序，对象和查询位置之间的距离受到道路网络（最短路径）的约束，并且不能使用R树有效地计算。本文首次提出了在道路网络上处理top-k空间关键字查询的挑战性问题，其中查询位置和空间对象之间的距离是最短路径，我们形式化了新的查询类型，并提出了新的索引结构和算法，能够有效地处理这样的查询。最后，我们进行了实验评估，表明我们的方法的效率。
With the popularization of GPS-enabled devices there is an increasing interest for location-based queries. In this context, one interesting problem is processing top-k spatial keyword queries. Given a set of objects with a textual description (e.g., menu of a restaurant), a query location (latitude and longitude), and a set of query keywords, a top-k spatial keyword query returns the k best objects ranked in terms of both distance to the query location and textual relevance to the query keywords. So far, the research on this problem has assumed Euclidean space. In order to process such queries efficiently, spatio-textual indexes combining R-trees and inverted files are employed. However, for most real applications, the distance between the objects and query location is constrained by a road network (shortest path) and cannot be computed efficiently using R-trees. In this paper, we address, for the first time, the challenging problem of processing top-k spatial keyword queries on road networks where the distance between the query location and the spatial object is the shortest path. We formalize the new query type, and present novel indexing structures and algorithms that are able to process such queries efficiently. Finally, we perform an experimental evaluation that shows the efficiency of our approach.