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

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