计算机应用 ›› 2015, Vol. 35 ›› Issue (11): 3146-3150.DOI: 10.11772/j.issn.1001-9081.2015.11.3146

• 2015年全国开放式分布与并行计算学术年会(DPCS 2015)论文 • 上一篇    下一篇

基于路网的群体出行计划查询算法

朱海泉, 李文根, 张毅超, 关佶红   

  1. 同济大学 计算机科学与技术系, 上海 201804
  • 收稿日期:2015-06-17 修回日期:2015-07-09 发布日期:2015-11-13
  • 通讯作者: 关佶红(1969-),女,辽宁开原人,教授,博士生导师,博士,CCF高级会员,主要研究方向:空间数据库、数据挖掘.
  • 作者简介:朱海泉(1991-),男,江苏南通人,硕士研究生,CCF会员,主要研究方向:空间关键词查询、数据挖掘; 李文根(1987-),男,四川南充人,博士研究生,CCF会员,主要研究方向:空间数据库、数据挖掘; 张毅超(1982-),男,上海人,助理教授, 博士,CCF会员,主要研究方向:复杂网络、数据挖掘.
  • 基金资助:
    国家自然科学基金资助项目(61373036).

Group trip planning queries on road networks

ZHU Haiquan, LI Wengen, ZHANG Yichao, GUAN Jihong   

  1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China
  • Received:2015-06-17 Revised:2015-07-09 Published:2015-11-13

摘要: 群体出行计划(GTP)查询旨在为一组用户查找共同的活动地点(通常以兴趣点(PoI)表示)以达到整体的出行开销最小.当前,对群体出行计划查询的研究大多仅限于欧氏空间,然而人们真实的出行却受到道路网络的约束.针对该问题,提出了两个基于路网的群体出行计划查询算法NE-GTP和ER-GTP.其中,NE-GTP通过扩展每个用户所在的边,来迭代地找到这组用户感兴趣的PoI; ER-GTP则是利用R树索引和欧氏距离是路网距离的下界这一条件来快速搜索满足关键词条件的PoI.实验结果表明,ER-GTP方法在查询速度上总体要比NE-GTP快一个数量级左右; 而且,当数据量很大时,ER-GTP也有很好的可扩展性.

关键词: 路网, 欧氏空间, 群体, 兴趣点, 群体出行计划查询

Abstract: Group Trip Planning (GTP) queries are targeting at finding some same activity sites for a group of users (usually expressed as Point of Interests (PoI)), in ordor to minimize the total travel cost. Existing researches on GTP queries are limited in Euclidean space, however, real travel is restricted by road network. Motivated by this observation, two algorithms (NE-GTP and ER-GTP) were designed to solve the GTP queries. NE-GTP expanded the network around every user's location to iteratively find the PoI, while ER-GTP used R-tree index and Euclidean distance to quickly get the results. The experimental results show that ER-GTP always performs on average an order of magnitude processing time faster than NE-GTP. In addition, when the dataset becomes large, ER-GTP also has good scalability.

Key words: road network, Euclidean space, group, Point of Interest (PoI), Group Trip Planning (GTP) query

中图分类号: