Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

文章介绍

数据时代的到来使得越来越多带有时空信息的数据被分析挖掘。位置选择问题是研究新设施建立的最佳位置使新设施对给定对象的影响最大化。该问题作为时空数据研究的一个分支不仅具有重要的理论研究意义，还具有实际的应用价值。该研究可广泛应用于空间决策支持系统，如城市规划、物流等各类应用场景。

本文研究运动场景下考虑设施间竞争因素的影响力最大化位置选择问题。给定研究对象的历史位置数据以及竞争设施的位置数据，同时考虑对象的移动性以及已有设施的竞争性，从候选位置集合中选择出竞争环境下能影响最多运动对象的位置建立新的服务设施。本文针对该问题完成了如下研究工作：

（1）引入了一个更实用的位置选择问题，即CLS-M，该问题同时考虑了对象的移动性和设施间的竞争因素。

（2）提出了一种称为影响力剪枝算法（IPA）的高效算法来解决所提出的问题，该算法设计了两种剪枝策略来降低计算的复杂度。

（3）基于两个城市的真实用户运动数据进行了综合实验。结果表明，与相关研究中的基线算法（NA）以及最先进的算法（PIV）相比，本文提出的解决算法显著提高了运算效率。

实验效果

实验在两个具有真实移动用户签到的数据集Foursquare和Gowalla下进行，分别对NA、PIV和IPA算法的效率以及IPA算法中的剪枝策略效果进行了评估。Foursquare中用户的签到位置均位于新加坡，Gowalla用户的签到位置集中在加利福尼亚，表1描述了上述两个数据集的数据特征。

表1. 数据集特征

图1展示了运动对象数量（|Ω|）变化对算法性能的影响。为了突出|Ω|对于算法查询效率在数据量方面的可伸缩性，实验在小数据量真实数据集下以及大数据量合成数据集下进行，实验结果表明，IPA算法的查询效率均为最优。具体而言，图(a)为小数据量真实数据集下的实验结果，IPA的剪枝效果显著；图(b)为合成数据集大数据量下的实验结果，随着对象数量的增加，IPA的查询效率趋于稳定，而NA以及PIV的查询效率均呈线性增长，这意味着IPA对于大型数据集更加具有可扩展性。

图1.对象数量变化效率对比图

图2展示了候选位置数量（|C|）变化对算法性能的影响。如图显示，IPA的性能最优，其运行成本比NA至少低一个数量级。随着|C|线性增长，NA和PIV的运行效率并未发生明显变化。这是由于计算影响力得分之前，NA和PIV必须对所有的已有设施以及运动对象之间的影响关系进行判断。该过程需要对已有设施以及运动对象进行完整遍历，这意味着|C|的变化不会影响需要遍历的对象数量。相反，对于IPA，由于IPA的主要计算开销是对候选位置影响的对象与已有设施之间的影响关系的判断，所以随着计算需要访问的候选位置数量增加，受候选位置影响的运动对象数量也会随之增加，故IPA的计算开销也会随之增加。

图2. 候选位置数量变化效率对比图

图3展示了IPA运行时间与需要计算的运动对象数量之间的相似趋势。随着|C|增加，IPA的剪枝效果下降。当|C|数量较大时，IPA性能将退化为PIV，因为此时候选位置会影响几乎全部对象。

图3. 候选位置数量对剪枝效果影响对比图

图4展示了已有设施数量（|F|）变化对算法性能的影响。当|F|分别以指数（Foursquare）和线性（Gowalla）方式增加，所有算法的计算时间均以同样的方式进行增长。对于NA和PIV，其数据查询时间主要是对已有设施和运动对象进行线性遍历扫描，故其查询时间会随|F|的增加方式而增长。对于IPA，其数据查询时间集中在对已有设施与受候选位置影响的对象之间影响关系的判断，而随着|F|分别以指数和线性方式增加，IPA的查询时间也呈对应方式增长。出现这一规律的主要原因是该算法需要访问的对象数量基本稳定。实验结果表明，随|F|增加，IPA的数据查询时间以最慢的增长率显示出其优越性。这是由于IPA的剪枝策略发挥作用，|F|越大，该算法的剪枝效果越明显。

图4. 已有设施数量变化效率对比图

图5展示了结果数量（k）变化对算法性能的影响。如图所示，与NA相比，IPA的数据查询时间至少减少一个数量级，并且其表现明显优于PIV。随着k的增加，三种算法的效率均趋于稳定。对于IPA，由于算法中阈值的设置，剪枝策略发挥作用，实际被访问的对象数量并不会随着k的增加而显著增加。

图5. 结果数量变化效率对比图

图6展示了阈值（τ）变化对算法性能的影响。NA和PIV的运行成本在τ发生变化时未出现显著变化，而IPA的查询时间会随着τ的增大而减少。这是因为NA和PIV的计算成本主要是对已有设施与全部对象之间的影响关系的判断，而无论τ取何值都不会影响NA和PIV对已有设施和全部对象执行完整的遍历计算。当τ设置为0.1时，IPA的性能下降到PIV，这是由于影响关系的定义中τ代表距离和位置质量间的平衡，当τ设置为0.1时，距离对影响关系的贡献几乎可以不考虑。

图6. 阈值变化效率对比图

图7显示了阈值τ的数值设置对剪枝过程的影响。τ的值很小时，IPA访问的候选位置将影响几乎所有运动对象。此时，所有算法都需要对已有设施以及全部运动对象进行遍历。此外，随着τ值的增加，在位置选择过程中距离对影响关系的贡献变大，算法需要访问的对象数量将明显减少。因此，在注重距离对位置选择的影响情况下，τ值设置越大，IPA算法的剪枝效果越佳，算法性能越好。

图7. 阈值变化对剪枝效果影响对比图

结语

本文研究了一种称为CLS-M的新型竞争性位置选择问题，该问题考虑了在移动场景下已有设施的竞争因素。具体来说，设计基于竞争的设施影响力评分模型，选择得分排名前k的候选位置建立新的设施。为解决大数据场景下算法的运行效率问题，本文设计了一种称为IPA的算法，该算法利用两种剪枝策略完成对计算效率的提升。在两个真实数据集上的综合实验研究表明，与基线算法NA和最先进的位置选择算法PIV相比，本文设计的IPA算法在效率方面优势显着。在未来的工作中，我们将进一步考虑设施间的合作关系对位置选择的影响。

作者简介

刘平，西安电子科技大学计算机科学与技术学院硕士研究生。主要研究方向为时空数据管理。

王蒙，工学博士，硕士生导师，西安工程大学计算机科学学院讲师，ACM中国理事会西安分会“新星奖”获得者，西安工程大学“优秀教师”，先后于西安交通大学和西安电子科技大学获得学士、硕士和博士学位，研究方向为时空大数据、图数据、数据管理与数据挖掘。在ICDE，TKDE，CIKM，EDBT，TIST，Bioinformatics和Information Sciences等国际顶级会议和著名期刊发表十余篇学术论文，成果荣获陕西省科学技术奖自然科学奖二等奖，IEEE国际会议MDM最佳论文奖，授权多项国家发明专利。主持国家自然科学基金子课题及陕西省自然科学基础研究项目2项，作为项目骨干参与国家重点研发计划及多项国家级科研项目。

崔江涛，西安电子科技大学计算机科学与技术学院教授，博士生导师，主要研究方向有数据库管理与内核技术、时空数据管理-位置推荐与选址问题、基于哈希的大规模视觉搜索、区块链数据管理。

李辉，西安电子科技大学计算机科学与技术学院教授，博士生导师。主要研究方向为数据挖掘、信息检索、保护隐私的数据查询、社会计算。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73^rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

原文链接：http://link.springer.com/article/10.1007/s41019-021-00157-1