面向实时定位系统的位置区域索引  

A Location Index for Range Query in Real-Time Locating System

作　　者：郭超[1] 李坤[1] 王永炎[1] 刘胜航[1] 王宏安[1] 

机构地区：[1]中国科学院软件研究所,北京100190

出　　处：《计算机研究与发展》2011年第10期1908-1917,共10页Journal of Computer Research and Development

基　　金："核高基"国家科技重大专项基金项目(2010ZX01042-001-001-05);国家"八六三"高技术研究发展计划基金项目(2008AA04A105)

摘　　要：在移动应用领域中,移动对象实时位置的区域查询在整个系统的分析、决策、预测等方面具有重要的作用.采用射频识别技术进行定位识别的实时定位系统具有对象分布区域化、不同子区域对象分布密度不均匀等特点.基于这些特点,提出了一种新的面向实时定位系统的区域索引机制,用以提高移动对象实时位置的区域查询的性能.该索引机制根据系统中对象的分布情况进行区域划分,利用R树对划分区域进行索引,并根据每个划分子区域对象的分布密度,用不同密度的网格索引位于该区域内部的对象的位置;同时进一步对提出的索引结构进行缓存感知的优化.实验结果表明,当对象分布不均时,该索引具有比R树和网格更优的区域查询性能,同时保持了良好的更新性能.The range query of moving objects＇ location is very important in many mobile applications, especially in analyzing, decision making, predicting, etc. Real-time locating system （RTLS） is a mobile system using RFID technology with the feature of skew object density. There are always storage wastes or performance decline while using existing indices in real-time locating system because of the skew object density~ In this paper, a novel index mechanism called RPI （region partition index） is proposed to answer the range queries in RTLS. It firstly divides the region of the RTLS into sub regions according to the object density, and then indexes the division regions with R-tree. The object locations in these division regions are indexed by grid. Furthermore, this index is optimized to be cache conscious. In the optimized index structure, the object locations in a of arrays. The size of each array is determined by the size of the CPU cache show that the new index has better search performance than R-tree and prominent update performance while object density is skew. The optimize performance improvement because it sharply reduces the cache miss rate in grid line grid cell are stored in a list ~ Experimental results and still keeps d index also brings s range queries. quite trong

关 键 词：位置索引 区域查询 射频识别技术 实时定位系统 R树 网格 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]