近日，重点实验室陆嘉恒教授团队的论文《Efficient Algorithms and Cost Models for Reverse Spatial-Keyword k-Nearest Neighbor Search》被国际数据库研究领域顶级期刊ACM Transactions on Database Systems (TODS)全文录用。

该文章主要解决的问题是在空间数据管理中同时考虑地理位置接近性和文本描述相似性的kNN查询，该问题在在线地图和地理信息决策支持系统中有着广泛的应用。

ACM Transactions on Database Systems (TODS)，是中国计算机学会推荐的A类国际期刊，是世界数据库领域最顶级的期刊。该期刊全年在全世界范围不过收录30篇高水平论文。这是本院教师第一次在该期刊上发表论文。

本文的第一作者是陆老师指导的硕士研究生吕瑛，她2012年以优异成绩从信息学院毕业，获得北京市优秀毕业研究生称号，目前在美国南加州大学攻读博士学位。这篇文章的主要工作在人大攻读硕士学位期间完成。

论文信息：

Efficient Algorithms and Cost Models for Reverse Spatial-Keyword k-Nearest Neighbor Search Accepted by ACM Transactions on Database Systems (TODS) 2014

YING LU and JIAHENG LU, RenminUniversityofChina

GAO CONG, Nanyang Technological University

WEI WU, Institute for Infocomm Research,Singapore

CYRUS SHAHABI, University of Southern California

论文中文摘要：

带有文本描述的地理位置对象越来越常见，这使得空间关键字查询要考虑一个对象的地理位置和描述文本两个方面。具体地，一个对象和一个查询的相关程度由两者的空间-文本相似性决定，这取决于它们的空间接近程度和文本描述的相似程度。在这篇文章中，我们介绍了逆向空间-关键字的kNN查询(RSKkNN，Reverse Spatial-Keyword k-Nearest Neighbor)，旨在找出有查询作为其在空间-文本上最接近的k个对象之一的空间-文本对象。这种RSKkNN查询在在线地图和GIS决策支持系统中有着广泛的应用。

为了高效地回答RSKkNN查询，我们提出了一个混合索引树，叫做IUR-tree（Intersection-Union R-Tree），有效地结合了地理位置的接近性与文本相似性。随后，我们设计了基于IUR-tree的分支定界搜索算法。为了加快查询处理，我们利用文本描述的分布改进了IUR-tree，产生了IUR-tree的一些变种，称为CIUR-tree（clustered IUR-tree）和C2IUR-tree（combined clustered IUR-tree）。对于每一个变种，我们开发最优的算法。我们还提供了理论开销模型来分析我们的算法的效率。我们的实证研究表明，该算法是有效并且可扩展的。