主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2019-2020年专刊出版计划 微信服务介绍 最新一期:2019年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李晨,申德荣,朱命冬,寇月,聂铁铮,于戈.一种对时空信息的kNN查询处理方法.软件学报,2016,27(9):2278-2289
一种对时空信息的kNN查询处理方法
kNN Query Processing Approach for Content with Location and Time Tags
投稿时间:2015-10-09  修订日期:2016-02-22
DOI:10.13328/j.cnki.jos.005046
中文关键词:  地理位置  时间  时空相似度  索引  k最近邻查询
英文关键词:ocation  time  temporal&spatial similarity  index  k nearest neighbor query
基金项目:国家自然科学基金(61472070);国家重点基础研究发展计划(973)(2012CB316201)
作者单位E-mail
李晨 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819 neu_LiChen@163.com 
申德荣 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819  
朱命冬 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819  
寇月 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819  
聂铁铮 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819  
于戈 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819  
摘要点击次数: 889
全文下载次数: 1408
中文摘要:
      互联网上每天都会产生大量的带地理位置标签和时间标签的信息,比如微博、新闻、团购等等,如何在众多的信息中找到在时间和空间地理位置上都满足用户查询需求的信息十分重要.针对这一需求,提出了一种对地理位置和时间信息的k近邻查询(ST-kNN查询)处理方法.首先,利用时空相似度对数据对象的地理位置变量和时间变量进行映射变换,将数据对象映射到新的三维空间中,用三维空间中两点之间的距离相似度来近似代替两个对象之间实际的时空相似度;然后,针对这个三维空间设计了一种ST-Rtree(spatial temporal rtree)索引,该索引综合了空间因素和时间因素,保证在查询时每个对象至多遍历1次;最后,在该索引的基础上提出了一种精确的k近邻查询算法,并通过一次计算确定查询结果范围,从而找到前k个结果,保证了查询的高效性.基于大量数据集的实验,证明了该查询处理方法的高效性.
英文摘要:
      Large amounts of content with location and time tags are generated every day on webs such as microblog, news, and group-buying. Thus, it is important to find top-k results that satisfy users' temporal and spatial requirements from the contents. In this paper, a novel kNN query (called ST-kNN query) processing approach is proposed for content with location and time tags. First, location variables and time variables of data objects are transformed via temporal & spatial similarity in order to map data objects to a new three-dimensional space. Next, the spatial similarity between two objects in the three-dimensional space is used to approximate the actual temporal & spatial similarity. Then, a new index called ST-Rtree is designed in this three-dimensional space. The index combines location variables & time variables, and ensures every object is traversed no more than once. At last, an exact kNN query algorithm is proposed. The region is determined by computing only once to find top-k results, which guarantees high-efficiency in the query processing. Experiments on large datasets demonstrate that the presented query processing approach is very efficient.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利