面向车辆共乘问题的LBSN查询处理技术

In recent years, as the issues of energy resources shortage and air pollution becoming more important, carpooling problems has been got more and more concerns. Location-based social networks(LBSN) is a new application background for carpooling service, of which the query techniques faces many new challenges. Specially, exist query semantics and techniques could not meet the carpooling requirements of the LBSN users. This project takes taxi pooling service as an example, and it focuses on the key query techniques for carpooling problems in LBSN. We analyze the challenges of designing new query semantics, query optimization and the modeling of geo-social objects. According to the traits of carpooling applications, the project would study carpooling preference keyword query、optimum paths query for carpooling、optimum paths match issues and optimum carpooling groups query. As the difference of LBSN queries and traditional queries, the carpooling query optimization strategies and indexing techniques are our primary studies. A prototype system of LBSN query techniques for carpooling application would be designed and developed base on the above technologies.

近年来，随着能源紧缺，空气污染严重等问题不断突显，车辆共乘问题得到了越来越多的关注。基于位置的社交网络（Location-based Social Networks, LBSN）作为共乘服务的全新应用背景，其涉及到的查询处理技术面对许多新的挑战，特别是在支持带有位置与社交信息的用户共乘需求方面，现有的查询语义和技术无法满足这类复杂的应用需求。本课题以出租车共乘服务为例，研究LBSN中面向车辆共乘问题的查询关键技术，对查询语义设计，查询优化处理以及LBSN对象建模等问题面临的挑战进行分析，针对共乘应用的特点，分别研究了共乘偏好关键字查询、最优共乘路径查询、共乘路径匹配以及最优共乘组查询等四类查询技术，考虑到面向LBSN中共乘问题的查询技术与以往查询技术的不同，拟重点研究针对LBSN环境下的共乘查询优化技术和数据索引技术，并结合以上技术实现一个面向车辆共乘应用的LBSN查询原型系统。

本项目针对面向车辆共乘问题的LBSN查询处理技术展开深入研究。首先分析了基于位置服务下共乘系统存在的问题以及现有LBSN查询技术存在的局限，针对异构共乘空间环境下的共乘实体查询技术进行深入研究，对共乘服务中四类关键查询应用进行语义分析及查询定义，这四类查询分别为：面向共乘偏好的关键字查询、基于最优共乘路径的K近邻查询、基于共乘路径匹配的Top-K查询以及基于最优共乘组的Top-K查询。根据各类查询特点，在数据处理、索引设计以及查询优化等方面提出了一系列创新的高效解决方案，并在由http://snap.stanford.edu等网站提供的实际数据集上进行实验对比和分析，从可扩展性、有效性、实时性等多方面进行充分的实验验证，并在此基础上，实现了一个支持地理社交网络共乘服务的LBSN查询原型系统。项目执行期间，在《软件学报》等高水平期刊和会议上发表学术论文11篇，依托本课题培养博士生1名、硕士生2名。