Storing routes in socio-spatial networks and supporting social-based route recommendation

ABSTRACT

Cellular phones and GPS-based navigation systems allow recording the location history of users, to find places the users frequently visit and routes along which the users frequently travel. This provides associations between users and geographic entities. Considering these associations as edges that connect users of a social network to geographical entities on a spatial network yields an integrated socio-spatial network. Queries over a socio-spatial network glean information on users, in correspondence with their location history, and retrieve geographical entities in association with the users who frequently visit these entities.

In this paper we present a graph model for socio-spatial networks that store information on frequently traveled routes. We present a query language that consists of graph traversal operations, aiming at facilitating the formulation of queries, and we show how queries over the network can be evaluated efficiently. We also show how social-based route recommendation can be implemented using our query language. We describe an implementation of the suggested model over a graph-based database system and provide an experimental evaluation, to illustrate the effectiveness of our model.

References

1. L. O. Alvares, V. Bogorny, B. Kuijpers, J. A. F. de Macedo, B. Moelans, and A. Vaisman. A model for enriching trajectories with semantic geographical information. In Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems - GIS '07, 2007.
2. Y. Doytsher, B. Galon, and Y. Kanza. Querying geo-social data by bridging spatial networks and social networks. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks - LBSN '10, 2010.
3. F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007.
4. H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. Sondag. Adaptive fastest path computation on a road network: A traffic mining approach. In Proceedings of the 33rd international conference on Very large data bases - VLDB '07, 2007.
5. B. Guc, M. May, Y. Saygin, and C. Körner. Semantic annotation of GPS trajectories. In 11th AGILE International Conference on Geographic Information Science, 2008.
6. C.-C. Hung, C.-W. Chang, and W.-C. Peng. Mining trajectory profiles for discovering user communities. In Proceedings of the 2009 International Workshop on Location Based Social Networks, LBSN 2009, 2009.
7. H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen. Discovery of Convoys in Trajectory Databases. Proceedings of the VLDB Endowment, 1(1), Feb. 2010.
8. H. Karimi, B. Zimmerman, A. Ozcelik, and D. Roongpiboonsopit. SoNavNet: a framework for social navigation networks. In Proceedings of the 2009 International Workshop on Location Based Social Networks, 2009.
9. J. Lee, J. Han, and K. Whang. Trajectory clustering: a partition-and-group framework. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, 2007.
10. J. W. Lee, P. O. Hyun, and K. H. Ryu. Temporal moving pattern mining for location-based service. Journal of Systems and Software, 73(3):481--490, 2004.
11. Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W. Ma. Mining user similarity based on location history. In Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008.
12. K. Xie, K. Deng, and X. Zhou. From trajectories to activities: a spatio-temporal join approach. In Proceedings of the International Workshop on Location Based Social Networks - LBSN '09, 2009.
13. Y. Ye, Y. Zheng, Y. Chen, J. Feng, and X. Xie. Mining Individual Life Pattern Based on Location History. In 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, May 2009.
14. J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS '10, 2010.
15. Y. Zheng, L. Zhang, X. Xie, and W. Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of the 18th International Conference on World Wide Web, WWW 2009, 2009.
16. B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10th international conference on Ubiquitous computing, 2008.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems