Discovery of Path Nearby Clusters in Spatial Networks
Discovery of Path Nearby Clusters in Spatial Networks
复制标题
空间网络中路径附近簇的发现
DOI：
10.1109/tkde.2014.2382583
复制
发表时间：
2015-06
影响因子：
8.9
通讯作者：
Ji-Rong Wen
中科院分区：
文献类型：
--
作者：
Shuo Shang;Kai Zheng;Christian S. Jensen;Bin Yang;Panos Kalnis;Guohe Li;Ji-Rong Wen
在大城市中发现感兴趣的区域是一个重要的挑战。我们提出并研究了一种称为路径邻近聚类（PNC）查询的新查询，该查询可以找到潜在感兴趣的区域（例如，观光地和商业区）。给定一组空间对象O（例如，POI、地理标记的照片或地理标记的推文）和查询路线q，如果集群c具有高空间对象密度并且在空间上接近q，则它由查询返回（集群是由中心和半径定义的圆形区域）。这种查询的目的是给用户带来重要的好处，在流行的应用程序，如旅行计划和位置推荐。PNC查询的高效计算面临两个挑战：如何在查询处理过程中修剪搜索空间，以及如何有效地识别高密度聚类。为了解决这些挑战，一种新的集体搜索算法的开发。从概念上讲，搜索过程是在空间和密度域同时进行的。在空间域中，采用网络扩展，从查询路径中选取一组顶点作为扩展中心。在密度域中，聚类根据其密度分布进行排序，并从最大值到最小值进行扫描。定义了一对上、下界，在两个域中全局修剪搜索空间。基于真实的和合成的空间数据对PNC查询的性能进行了广泛的实验研究。
The discovery of regions of interest in large cities is an important challenge. We propose and investigate a novel query called the path nearby cluster (PNC) query that finds regions of potential interest (e.g., sightseeing places and commercial districts) with respect to a user-specified travel route. Given a set of spatial objects O (e.g., POIs, geo-tagged photos, or geo-tagged tweets) and a query route q, if a cluster c has high spatial-object density and is spatially close to q, it is returned by the query (a cluster is a circular region defined by a center and a radius). This query aims to bring important benefits to users in popular applications such as trip planning and location recommendation. Efficient computation of the PNC query faces two challenges: how to prune the search space during query processing, and how to identify clusters with high density effectively. To address these challenges, a novel collective search algorithm is developed. Conceptually, the search process is conducted in the spatial and density domains concurrently. In the spatial domain, network expansion is adopted, and a set of vertices are selected from the query route as expansion centers. In the density domain, clusters are sorted according to their density distributions and they are scanned from the maximum to the minimum. A pair of upper and lower bounds are defined to prune the search space in the two domains globally. The performance of the PNC query is studied in extensive experiments based on real and synthetic spatial data.
登录
查看更多内容
DOI：
10.1145/956676.956677
发表时间：
2003-11
期刊：
--
影响因子：
--
作者：
Christian S. Jensen;Jan Kolárvr;T. Pedersen;Igor Timko
通讯作者：
Christian S. Jensen;Jan Kolárvr;T. Pedersen;Igor Timko
DOI：
10.1007/978-1-4614-1629-6
发表时间：
2011-10
期刊：
--
影响因子：
--
作者：
Yu Zheng;Xiaofang Zhou
通讯作者：
Yu Zheng;Xiaofang Zhou
DOI：
10.1002/9781444324044.ch9
发表时间：
2010-06
期刊：
--
影响因子：
--
作者：
Anil K. Jain;J. Mao;K. Mohiuddin
通讯作者：
Anil K. Jain;J. Mao;K. Mohiuddin
DOI：
10.1007/978-1-0716-0826-5
发表时间：
2004-08
期刊：
Artificial Neural Networks
影响因子：
--
作者：
Steven Walczak
通讯作者：
Steven Walczak
DOI：
10.1016/b978-155860869-6/50033-0
发表时间：
2002-08
期刊：
--
影响因子：
--
作者：
Yufei Tao;Dimitris Papadias;Qiongmao Shen
通讯作者：
Yufei Tao;Dimitris Papadias;Qiongmao Shen