一种对时空信息的kNN查询处理方法

来源：软件学报杂志2016年第9期北京时间：

作者：李晨,申德荣,朱命冬,寇月,聂铁铮,于戈

单位：李晨，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081911,申德荣，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081902,朱命冬，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081903,寇月，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081904,聂铁铮，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081905,于戈，东北大学 计算机科学与工程学院, 辽宁 沈阳 11081906

摘要：互联网上每天都会产生大量的带地理位置标签和时间标签的信息，比如微博、新闻、团购等等，如何在众多的信息中找到在时间和空间地理位置上都满足用户查询需求的信息十分重要.针对这一需求，提出了一种对地理位置和时间信息的k近邻查询（ST-kNN查询）处理方法.首先，利用时空相似度对数据对象的地理位置变量和时间变量进行映射变换，将数据对象映射到新的三维空间中，用三维空间中两点之间的距离相似度来近似代替两个对象之间实际的时空相似度；然后，针对这个三维空间设计了一种ST-Rtree（spatial temporal rtree）索引，该索引综合了空间因素和时间因素，保证在查询时每个对象至多遍历1次；最后，在该索引的基础上提出了一种精确的k近邻查询算法，并通过一次计算确定查询结果范围，从而找到前k个结果，保证了查询的高效性.基于大量数据集的实验，证明了该查询处理方法的高效性.

关键词：地理位置;时间;时空相似度;索引;k最近邻查询

基金资助：国家自然科学基金（61472070）；国家重点基础研究发展计划（973）（2012CB316201）