近日，我校计算机科学学院王蒙副教授团队在数据挖掘领域取得重大突破，研究成果“MC²LS: Towards Efficient Collective Location Selection in Competition”被国际顶级期刊IEEE Transactions on Knowledge and Data Engineering（TKDE）全文录用，这是我校首次以第一署名单位被该权威期刊录用。TKDE期刊在计算机科学、人工智能、电子工程、计算机工程和其他相关领域具有很高的影响力，被中国计算机学会（CCF）列为A类顶级期刊，其收录的论文代表着该领域的最高研究水平。

该研究针对时空大数据中的最优位置挖掘问题，旨在从众多候选地点中筛选出一组能够共同吸引最大数量用户的最优位置组合。随着移动互联网和GPS技术的广泛应用，传统基于固定位置用户的研究模型已无法满足现实需求，而位置间的竞争关系也因计算复杂度极高而被长期忽视。王蒙团队创新地提出了MC²LS问题，首次在竞争环境下为移动用户探索最优位置选择策略。研究从理论上证明了MC²LS问题的NP-hard特性，因此其解在多项式时间内难以求得。通过深入研究，设计了两项基于计算几何学的剪枝规则，并结合Quad-tree结构，创新性地构建了IQuad-tree二维索引结构，这一结构不仅突破了用户活动区域重叠的限制，还充分利用了剪枝规则的层次性和批量处理优势，实现了高效且准确的解决方案。

实验结果表明，研究提出的解决方案在保证(1-1/e)近似最优解的同时，相较于现有最先进技术，在性能上实现了至少一个量级的显著提升。研究在动态用户与竞争环境中实现了数据挖掘的高效性和可用性，为智慧城市发展提供了全新技术驱动力。

据悉，该成果得到国家自然科学基金、陕西省自然科学基础研究、陕西省教育厅重点科学研究计划、西安市科技计划等项目支持；该论文合作者还包括我校硕士研究生赵梦霏，杨博副教授、薛涛教授，以及西安电子科技大学李辉教授、崔江涛教授。

（撰稿：刘俊华 审稿：樊威 闫小兵）

图1 两个新型剪枝策略示意图

图2 IQuad-tree索引结构示意图