微信服务号

微信订阅号

2025年4月3日 14:25 星期四
首页 > 过刊浏览>2016年第27卷第9期 >2278-2289. DOI:10.13328/j.cnki.jos.005046
PDF HTML阅读 XML下载 导出引用 引用提醒
一种对时空信息的kNN查询处理方法
作者:
基金项目:

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


kNN Query Processing Approach for Content with Location and Time Tags
Author:
Fund Project:

National Natural Science Foundation of China (61472070); National Basic Research Program of China (973) (2012CB316201)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [25]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    [1] Chen L,Cong G,Jensen CS,Wu D.Spatial keyword query processing:An experimental evaluation.In:Proc.of the 39th Int'l Conf.on Very Large Data Bases (VLDB 2013).VLDB Endowment,2013.217-228.[doi:10.14778/2535569.2448955]
    [2] Cao X,Chen L,Cong G,Jensen CS,Qu Q,Skovsgaard A,Wu D,Yiu ML.Spatial keyword querying.In:Atzeni P,Cheung D,Sudha R,eds.Proc.of the ER 2012.LNCS 7532,Springer-Verlag,2012.16-29.[doi:10.1007/978-3-642-34002-4_2]
    [3] Chen YY,Suel T,Markowetz A.Efficient query processing in geographic Web search engines.In:Proc.of the Int'l Conf.on Management of Data (SIGMOD 2006).New York:ACM Press,2006.277-288.[doi:10.1145/1142473.1142505]
    [4] Guttman A.R-Trees:A dynamic index structure for spatial searching.In:Proc.of the Int'l Conf.on Management of Data (SIGMOD'84).ACM Press,1984.47-57.[doi:10.1145/602259.602266]
    [5] Chen C,Li F,Ooi BC,Wu Sai.TI:An efficient indexing mechanism for real-time search on Tweets.In:Proc.of the Int'l Conf.on Management of Data (SIGMOD 2011).New York:ACM Press,2011.649-660.[doi:10.1145/1989323.1989391]
    [6] Cao X,Cong G,Jensen CS.Retrieving top-k prestige-based relevant spatial web objects.In:Proc.of the 36th Int'l Conf.on Very Large Data Bases (VLDB 2010).2010.3(1-2):373-384.[doi:10.14778/1920841.1920891]
    [7] Zhang D,Chee YM,Mondal A,Tung AKH,Kitsuregawa M.Keyword search in spatial databases:Towards searching by document.In:Proc.of the 25th Int'l Conf.on Data Engineering (ICDE 2009).Shanghai:IEEE Computer Society,2009.688-699.[doi:10.1109/ICDE.2009.77]
    [8] Magdy A,Mokbel MF,Elnikety S,Nath S,He Y.Mercury:A memory-constrained spatio-temporal real-time search on microblogs.In:Proc.of the 30th Int'l Conf.on Data Engineering (ICDE 2014).Chicago:IEEE Computer Society,2014.172-183.[doi:10.1109/ICDE.2014.6816649]
    [9] Skovsgaard A,Sidlauskas D,Jensen CS.Scalable top-k spatio-temporal term querying.In:Proc.of the 30th Int'l Conf.on Data Engineering (ICDE 2014).Chicago:IEEE Computer Society,2014.148-159.[doi:10.1109/ICDE.2014.6816647]
    [10] Chen L,Cong G,Cao X,Tan KL.Temporal spatial-keyword top-k publish/subscribe.In:Proc.of the 31st Int'l Conf.on Data Engineering (ICDE 2015).Seoul:IEEE Computer Society,2015.255-266.[doi:10.1109/ICDE.2015.7113289]
    [11] Theodoridis Y,Sellis T,Papadopoulos AN,Manolopoulos Y.Specifications for efficient indexing in spatiotemporal databases.In:Proc.of the 10th Int'l Conf.on Scientific and Statistial Database Management.Capri:IEEE Computer Society,1998.123-132.[doi:10.1109/SSDM.1998.688117]
    [12] Theodoridis Y,Vazirgiannis M,Sellis T.Spatio-Temporal indexing for large multimedia applications.In:Proc.of the 3rd IEEE Int'l Conf.on Multimedia Computing and Systems.Hiroshima:IEEE Computer Society,1996.441-448.[doi:10.1109/MMCS.1996.535011]
    [13] Nascimento MA,Silva JRO.Towards historical R-trees.In:Proc.of the ACM Symp.on Applied Computing (SAC'98).New York:ACM Press,1998.235-240.[doi:10.1145/330560.330692]
    [14] Song Z,Roussopoulos N.K-Nearest neighbor search for moving query point.In:Proc.of the 7th Int'l Symp.on Advances in Spatial and Temporal Databases (SSTD 2001).London:Springer-Verlag,2001.79-96.[doi:10.1007/3-540-47724-1_5]
    [15] Lazaridis I,Porkaew K,Mehrotra S.Dynamic queries over mobile objects.In:Proc.of the 8th Int'l Conf.on Extending Database Technology (EDBT 2002).Springer-Verlag,2002.269-286.[doi:10.1007/3-540-45876-X_18]
    [16] Benetis R,Jensen CS,Karciauskas G,Saltenis S.Nearest neighbor and reverse nearest neighbor queries for moving objects.In:Proc.of the Int'l on Very Large Data Bases.New York:Springer-Verlag,2002.229-249.[doi:10.1007/s00778-005-0166-4]
    [17] Cong G,Jensen CS,Wu D.Efficient retrieval of the top-k most relevant spatial Web objects.In:Proc.of the Int'l Conf.on Very Large Data Bases (VLDB 2009).VLDB Endowment,ACM Press,2009.337-348.[doi:10.14778/1687627.1687666]
    [18] Felipe ID,Hristidis V,Rishe N.Keyword search on spatial databases.In:Proc.of the 24th Int'l Conf.on Data Engineering (ICDE2008).Cancun:IEEE Computer Society,2008.656-665.[doi:10.1109/ICDE.2008.4497474]
    [19] Lu J,Lu Y,Cong G.Reverse spatial and textual k nearest neighbor search.In:Proc.of the 2011 ACM SIGMOD Int'l Conf.on Management of Data.New York:ACM Press,2011.349-360.[doi:10.1145/1989323.1989361]
    [20] Mokbel MF,Ghanem TM,Aref WG.Spatio-Temporal access methods.IEEE Computer Society Technical Committee on Data Engineering,2003,26(2):40-49.
    [21] Zhou AY,Yang B,Jin CQ,Ma Q.Location-Based services:Architecture and progress.Chinese Journal of Computers,2011,34(7):1155-1171(in Chinese with English abstract).
    [22] Zhu SP,Zhao JJ.Research of spatio-temporal access method.Computer Technology and Development,2008,18(7):56-59(in Chinese with English abstract).
    附中文参考文献:
    [21] 周傲英,杨彬,金澈清,马强.基于位置的服务:架构与进展.计算机学报,2011,34(7):1155-1171.
    [22] 祝蜀平,赵瑾瑾.时空数据库索引方法研究.计算机技术与发展,2008,18(7):56-59.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李晨,申德荣,朱命冬,寇月,聂铁铮,于戈.一种对时空信息的kNN查询处理方法.软件学报,2016,27(9):2278-2289

复制
分享
文章指标
  • 点击次数:2531
  • 下载次数: 4958
  • HTML阅读次数: 1332
  • 引用次数: 0
历史
  • 收稿日期:2015-10-09
  • 最后修改日期:2016-02-22
  • 在线发布日期: 2016-09-02
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19780803位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号