Discovery of path nearby clusters in spatial networks

Shang, Shuo; Zheng, Kai; Jensen, Christian S.; Yang, Bin; Kalnis, Panos; Li, Guohe; Wen, Ji Rong

Discovery of path nearby clusters in spatial networks

Type

Article

Authors

Shang, Shuo
Zheng, Kai
Jensen, Christian S.
Yang, Bin

Kalnis, Panos

Li, Guohe
Wen, Ji Rong

KAUST Department

Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division
Computer Science Program

Date

2015-06-01

Abstract

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. © 2014 IEEE.

Citation

Shang, S., Zheng, K., Jensen, C. S., Yang, B., Kalnis, P., Li, G., & Wen, J.-R. (2015). Discovery of Path Nearby Clusters in Spatial Networks. IEEE Transactions on Knowledge and Data Engineering, 27(6), 1505–1518. doi:10.1109/tkde.2014.2382583

Acknowledgements

This work is partly supported by the National Natural Science Foundation of China (NSFC. 61402532), the Science Foundation of China University of Petroleum-Beijing (No. 2462013YJRC031), the Excellent Talents of Beijing Program (No. 2013D009051000003), and by a grant from the Obel Family Foundation. Guohe Li is the corresponding author.