空间网络数据库关键字查询的高效空中索引  

An efficient air index for keyword search on spatial network databases

作　　者：李艳红[1] 李国徽[2] 

机构地区：[1]中南民族大学计算机科学学院,湖北武汉430074 [2]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2016年第8期41-45,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61309002)

摘　　要：研究无线广播环境下空间网络数据库关键字查询问题,提出一种包含路网加权四叉树、各关键字四叉树和路网距离矩阵的空中索引结构(KSSN).讨论了kNN查询处理问题,提出了高效的查询处理算法.所提出的算法能综合利用路网距离信息和关键字信息高效地消减不存在查询结果对象的路网空间,提高查询处理的效率.KSSN索引结构可推广至其他类型的查询,比如范围查询、Rank查询.在一个真实路网上进行了仿真实验,验证了基于KSSN索引结构的查询处理算法的性能.实验结果表明:所提出算法的访问时间和调谐时间分别为参照的IRRDA算法的25.13%和12.31%.This paper addresses the issue of keyword search on spatial network（KSSN）databases,and proposes a novel air index,which combines a road network weighted quad-tree,several keyword quad-trees and a network distance array.It discusses kNN queries and proposes an efficient query processing algorithm.By using road network distance and keyword information simultaneously,the proposed algorithm can efficiently prune irrelevent regions of the road network which cannot include result objects,so as to greatly improve query processing efficiency.KSSN index structure can be extended to handling other types of queries,such as range query,Rank query.Finally,simulation experiments on a real road network are conducted to verify the performace of the KSSN-based query processing algorithm.The experiment results show that,the access time and tuning time of our proposed algorithm are only 25.13% and 12.31% of that of the compared IRRDA algorithm,respectively.

关 键 词：空间网络数据库 关键字查询 犽近邻查询 无线广播环境 空中索引 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]