支持位置服务社交网络中多元偏好查询处理技术

Multi-variate preferences query processing over location based social network (LBSN for short) is one type of important queries. It formulates evaluation rules according to user preferences, and returns few valuable objects-groups to the user. Compared with traditional queries, it focus on the value generated by objects-group other than objects themselves, which also has many important applications. In order to efficiently support such queries, we have to face the following two vital challenges. For the first one, LBSN objects are very complex, their scale is very large. For another, multi-variate preference queries have to evaluate value generated by objects-group other than objects themselves, which also increases the difficulty of supporting such queries. Although many researchers have studied this type of queries, the challenges above still cannot be overcome. In this project, we address to study some vital technologies for supporting Multi-variate query processing over LBSN. In order to achieve this goal, we will study three problems, which are LBSN data model construction, data management, and query processing and optimization. For the first one, we will study how to evaluate the relationship different LBSN objects and how to effectively extract feature information of LBSN objects. For the second one, we will study the technologies of data storage and indexing. For the third one, we aim to achieve the goal of searching query targets quickly. Finally, we plan to implement an oriented prototype system. Theoretical and practical results will provide a more reliable guarantee for improving the LBSN service.

支持位置服务社交网络(缩写：LBSN)中的多元偏好查询是LBSN环境下的一类重要查询。它根据用户偏好制定评价规则，从而为用户返回少量最具价值的数据组合。和传统查询相比，此类查询注重不同数据在组合后所体现的价值，具有广泛的应用场景。LBSN数据规模庞大且结构复杂，而多元查询又需考虑多对象组合后所产生的价值，这给高效支持此类查询带来了巨大挑战。目前为止，虽有学者针对此类查询展开研究，但研究成果无法克服上述挑战。课题从数据模型构建、数据高效管理以及查询处理优化等三个方面，对面向LBSN的多元偏好查询处理关键技术进行研究。研究数据模型构建，实现异构数据间关系的度量和特征信息的提取；研究数据管理，实现数据高效存储与索引；研究查询处理与优化，实现查询结果快速返回。课题最终将实现一个原型系统，相关研究成果将为提升LBSN服务提供更加可靠的保证，具有十分重要的理论和现实意义。

面向基于位置社交网络（简称LBSN）环境下的偏好查询具有重要的应用价值，已被广泛研究。然而，面向LBSN的多元偏好查询却很少被研究。由于此类查询需要考虑对象和对象之间的关系，它们的计算代价和空间代价普遍较高，已有技术无法通常高效支持LBSN下的多元偏好查询。本项目针对LBSN环境下多元偏好查询及其拓展查询展开研究。具体包括：（1）LBSN数据模型构建策略；（2）针对不同类别多元偏好查询的索引技术；（3）针对不同类别多元偏好查询的查询处理及优化技术.主要成果如下：.(1)数据模型构建策略：利用相似性度量函数计算数据之间的相似性和关联性，为索引构建和查询处理优化奠定理论基础；.(2)索引构建策略：针对K代表轮廓查询、离群点检测，反 K近邻查询构建索引，通过索引拓扑结构反应数据间的关联关系和相似性关系，从而为多元偏好查询处理提供技术手段；.(3)查询处理与优化：项目组首先研究了LBSN中面向流数据的一元偏好查询处理算法。理论表明：算法的时间复杂度达到了问题复杂度；随后，项目组首次研究了LBSN环境下的近似k代表轮廓查询问题和数据流环境下基于位置-关键字的轮廓查询问题，所提算法证明可在大规模LBSN数据环境下高效工作。第三，项目组研究了LBSN中面向流数据的近似离群点检测问题，所提算法证明可在保证95%准去率的前提下高效执行离群点检测，计算效率提升了近80%.第四，项目组研究了LBSN中面向图数据的聚类问题，该问题是一个新问题，项目组通过研究SCAN算法和PSCAN算法的机理，提出有效算法实现了聚类结果的修复，提升了聚类质量。第五，项目组研究了LBSN中面向不一致数据的聚集查询问题。理论分析表明，可靠结果是真实查询结果的区间估计,可以保证真实查询结果在很大概率下实现高质量求解. 第六，项目组研究了LBSN中基于时空众包的在线匹配问题。针对此类问题，项目组首先研究了基于机器学习的路径规划问题，随后研究了基于热点区域的在线拼车问题。和前人所提算法相比，匹配数量了提高17%.