位置相关社交网络中空间组偏好查询研究

摘要

随着在线社交网络及位置服务(Location-Based Services，LBS)的快速发展，根据社交网络中不同用户行为偏好，结合用户地理位置，为用户提供个性化的服务，成为近年来的研究热点，由此也催生了位置相关社交网络这一研究方向。位置相关社交网络中蕴含涉及用户历史行为偏好及商家店铺评分等多方面的信息。如何有效利用这些信息，在满足用户多样化需求的前提下提供令用户满意的服务，是目前位置相关社交网络中的核心问题之一。
　　本文以位置相关社交网络的发展为背景，以社交网络中的用户群组（如好友圈）为研究对象，定义了一类新的查询——空间组偏好查询，并提出了有效的查询处理算法。位置相关社交网络中的空间组偏好查询基于用户群组中不同用户的偏好、兴趣点（Point Of Interets，POI，如餐厅、旅店等）评分及POI间互相影响等多种约束下，返回满足要求的POI集合。空间组偏好查询在日常聚会地点的选择，众包游戏的任务分配等方面都有重要的意义。本文首先提出了一种基于用户偏好和POI匹配的空间组偏好查询算法，进而对该算法进行扩展，提出了基于语义扩展的空间组偏好查询算法。总体而言，本文的主要工作和贡献归纳如下:
　　(1)基于用户偏好和POI匹配的空间组偏好查询算法:针对位置相关社交网络中的组偏好问题，定义了结合用户当前位置和用户对POI偏好的空间组偏好查询，设计了用户群组满意度的计算公式，并提出了一种基于剪枝策略的查询处理算法OPA。在此基础上，为进一步提高查询性能，论文提出了一种带有位置语义类别标签及其他附加信息的索引结构——CR-tree，并基于CR-tree设计了OPC算法，对OPA的剪枝策略从空间、POI属性等方面进行了优化。在大规模数据集上的实验结果表明了OPA和OPC算法的有效性。
　　(2)基于语义扩展的空间组偏好查询算法:由于OPA和OPC算法均没有考虑查询中的语义相关性（例如查询词和POI类别词之间的相似度），因此论文进一步研究了语义扩展的空间组偏好查询问题，提出了基于语义扩展的空间组偏好查询算法OPS。在OPS算法中，我们建立语义树来描述不同POI位置描述间的层次关系，并基于此定义了POI对应的扩展位置语义模式。此外，我们结合语义树改进了最长公共子序列LCSS算法实现POI位置语义相似性的度量，并将POI语义相似性作为度量用户群组满意程度的重要因素。与此同时，为保证查询的高效执行并返回合理的查询结果，我们设计并实现了包含POI空间属性与位置语义属性的SR-tree索引和多种剪枝策略，两者结合共同对数据集中的POI进行空间过滤、POI偏好过滤及POI语义相似性过滤。在广州和上海两个真实POI数据集上的实验验证了OPS算法的有效性。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．1．1 位置相关社交网络

1．1．2 空间组偏好查询

1．1．3 语义扩展的空间组偏好查询

1．2 国内外研究现状

1．2．1 空间组查询

1．2．2 Top-k空间偏好查询

1．2．3 空间组偏好查询

1．2．4 集合关键字查询

1．3 论文研究内容

第2章 空间文本查询及相关技术

2．1 空间查询

2．2 空间文本查询

2．3 文本索引技术

2．4 空间索引技术

2．4．1 基于点区域划分的索引

2．4．2 基于面区域划分的索引

2．5 空间文本混合索引技术

2．6 本章小结

第3章 基于用户偏好和POI匹配的空间组偏好查询

3．1 相关工作

3．2 空间组偏好查询问题定义

3．3 用户群组满意度定义

3．4 查询处理算法

3．4．1 Baseline算法

3．4．2 基于剪枝策略的查询处理算法

3．5 CR-tree结构及查询算法

3．5．1 Category R-tree索引结构

3．5．2 基于CR-tree的剪枝策略

3．5．3 基于CR-tree的查询处理算法

3．6 实验与分析

3．6．1 数据集

3．6．2 评价方法

3．6．3 实验结果与分析

3．7 本章小结

第4章 语义扩展的空间组偏好查询算法

4．1 相关工作

4．2 问题定义

4．2．1 语义扩展的组偏好查询

4．2．2 查询形式化定义

4．3 位置语义相似性度量

4．3．1 POI集合位置语义关系描述

4．3．2 POI位置语义相似性度量

4．4 语义-满意度模型定义

4．5 Baseline查询处理算法

4．6 SR-tree结构及查询算法

4．6．1 SR-tree索引结构

4．6．2 基于SR-tree的剪枝策略

4．6．3 基于SR-tree的查询处理算法

4．7 实验与分析

4．7．1 数据集

4．7．2 评测方法

4．7．3 实验结果与分析

4．8 本章小结

第5章 总结与展望

5．1 论文工作总结

5．2 未来工作展望

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果