(数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 100872)
Efficient Compressed Index for Top-k Spatial Keyword Query
ZHOU Xin,ZHANG Xiao,AN Run-Gong,XUE Zhong-Bin,WANG Shan
(Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education (Renmin University of China), Beijing 100872, China;School of Information, Renmin University, Beijing 100872, China)
Chart / table
Similar Articles
Article :Browse 1550   Download 1495
Received:May 07, 2014    Revised:August 19, 2014
> 中文摘要: 基于位置的服务可以指引用户找到在特定位置或区域内能够提供所需要服务的对象(比如找某个高校附近(经纬度标识)的咖啡店).向这类服务提交一个查询位置和多个关键词,该类服务返回k个最相关的对象,对象和查询的相关性同时考虑空间相近性和文本相似性.为了支持高效的top-k空间关键词查询,出现了多种混合索引,然而现有的这些索引为了提供实时响应均耗费大量存储空间.提出一种基于压缩技术的索引CSTI,该索引显著减少了存储开销(至少减少80%甚至到两个数据量级),同时保持高效的查询性能.大量基于真实和仿真数据集的实验结果表明,CSTI在空间开销和响应时间上均优于已有方法.
中文关键词: 压缩索引  top-k  空间关键词检索
Abstract:Location-Based services guide a user to find the object which provides services located in a particular position or region (e.g., looking for a coffee shop near a university). Given a query location and multiple keywords, location-based services return the most relevant objects ranked according to location proximity and text relevancy. Various hybrid indexes have been proposed in recent years which combine R-tree and inverted index to improve query efficiency. Unfortunately, the state-of-the-art approaches require more space in order to reduce response time. Cache mechanism is inefficient due to huge storage overhead. In this paper, a novel index based on index compressed technology (CSTI) is proposed, to answer top-k SKQ. CSTI significantly reduces storage overhead (by at least 80%), while maintaining efficient query performance. Extensive experiments based on real dataset and simulated dataset confirm CSTI is effective and efficient.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61070054);国家重点基础研究发展计划(973)(2014CB340403);国家高技术研究发展计划(863)(2012AA011001);中央高校基本科研业务费专项资金(10XNI018) 国家自然科学基金(61070054);国家重点基础研究发展计划(973)(2014CB340403);国家高技术研究发展计划(863)(2012AA011001);中央高校基本科研业务费专项资金(10XNI018)
Foundation items:
Reference text:


ZHOU Xin,ZHANG Xiao,AN Run-Gong,XUE Zhong-Bin,WANG Shan.Efficient Compressed Index for Top-k Spatial Keyword Query.Journal of Software,2014,25(S2):157-168