一种面向大规模空间文本数据的空间结构匹配算法

为了支持各类基于位置的服务,人们提出了各种查询和搜索空间文本数据的方法和技术.传统的空间关键字查询和近期提出的空间模式匹配不支持用户定义查询关键字对象以及对象之间细致的空间结构关系,使得查询结果集庞大但无效结果偏多,不能满足用户高效且精确的查询需求.本文因此提出了一种新的查询模式——空间结构匹配查询(Spatial Structure Matching,SSM),允许用户定义一组查询关键字对象并指定任意两个对象之间的距离和方向约束.为了解决SSM查询问题,本文首先提出了一种基于多路连接的基准方法,将SSM查询问题分解为单个对象的关键字匹配,两个对象的边匹配和多个对象的聚合匹配.为了提高SSM查询效率,本文提出了基于扫描线算法的边匹配计算,利用对象的地理位置信息来降低边匹配计算开销.本文利用同时满足查询关键字,距离和方向约束的空间对象构造对象连接图,从而将SSM查询问题转换为在对象连接图上搜索与SSM查询结构同构的子图匹配问题,并且利用经典的子图同构匹配算法求解获得最终的查询结果.在四个大规模空间文本数据集上的实验结果表明,本文所提算法的查询效率远高于对比算法,返回的查询结果集精简有效且在查询时间上提升至少3倍.

CoSTUR:面向用户评级的空间文本竞争选址

随着GPS定位技术和移动互联网的发展,各类LBS(location-based service)应用积累了大量带有位置和文本标记的空间文本数据,这些数据广泛应用于市场营销、城市规划等设施选址决策中.空间文本选址的目标是从候选位置集合中挖掘最佳地点新建设施,以期影响最多空间文本对象,如用户或车辆等,其中空间距离越接近且文本越相似则影响力越大.现有方案未考虑现实普遍存在的同行竞争,也忽略了用户对设施的评价因素.为更合理地在同行竞争环境结合用户评级进行选址决策,本文提出新的空间文本竞争选址问题CoSTUR.通过引入权衡影响的确定性和数量的阈值,解决传统模型中对象只能被单一设施影响的局限,建模了用户可能同时受多个设施影响的真实情况.借鉴经典的竞争均分模型,实现了不同评级设施间竞争量化.为降低大规模数据导致的高昂计算代价,构建了新型空间文本索引结构TaR-tree,并结合阈值设计基于影响范围的两个剪枝策略,实现基于分支定界思想的空间连接和范围查询两种方案.在真实和合成数据集上的实验结果显示,相比基线算法计算效率能够提升近一个量级,说明提出方法的有效性.

基于多维小波聚类的空间文本数据情感分布分析

【目的】构建基于多维小波聚类的空间文本数据情感分析模型,实现文本情感和空间位置的综合分析。【方法】将Yelp数据集进行整合以构建空间文本数据库,使用基于词典的情感分析方法构建特征向量。提出使用多维小波聚类的混合算法和文本–空间算法两种模型并进行分析。【结果】实验结果验证了使用db2和bior2.2小波基函数的多维小波聚类算法比DBSCAN和K-means算法在空间文本数据挖掘中能识别出更精确的聚类集合,且在十万级至千万级数据聚类中速度最佳。【局限】情感分析部分使用一元语言模型,缺乏对语句层面意义的分析。【结论】本文所提文本–空间算法模型能有效挖掘多维空间文本数据的情感倾向分布;混合算法模型为空间文本数据推荐系统提供了同时计算空间接近性和情感相似性的有效方案。

基于空间-文本数据流的单词频数近似查询索引分析

阐述一种基于sketch技术的网格索引,可以对空间-文本数据流中的数据对象进行索引,并且回答空间单词频数查询。该索引结构可以大幅度节省索引存储空间,加快查询速率,具有较高查询精度。