在移动应用领域中,移动对象实时位置的区域查询在整个系统的分析、决策、预测等方面具有重要的作用,采用射频识别技术进行定位识别的实时定位系统具有对象分布区域化、不同子区域对象分布密度不均匀等特点.基于这些特点,提出了一种新的面向实时定位系统的区域索引机制,用以提高移动对象实时位置的区域查询的性能.该索引机制根据系统中对象的分布情况进行区域划分,利用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 objectlocations 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 grid cell are stored in a list of arrays. The size of each array is determined by the size of the CPU cache line. Experimental results show that the new index has better search performance than R-tree and grid, and still keeps quite prominent update performance while object density is skew. The optimized index also brings strong performance improvement because it sharply reduces the cache miss rate in range queries.
展开▼
