空间数据库中一种自适应的缓存替换策略  

An Adaptive Page-Replacement Strategy for Spatial Database Systems

作　　者：陈坤杰[1] 孙未未[1] 朱良[1] 刘未末[1] 

机构地区：[1]复旦大学计算机科学技术学院,上海201203

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

基　　金：国家自然科学基金项目(61073001)

摘　　要：随着近年来空间数据库研究和应用的不断深入,针对空间数据库中数据组织和查询的特征来设计缓存页面替换策略成为一个新的研究问题.Voronoi图是一种重要的空间数据库组织技术,在处理kNN查询时具有非常好的性能.针对Voronoi图组织的空间数据库,首先利用空间局部性提出了一种基于欧氏距离的替换策略,在发生页面失效时选择距离上一次访问页面欧氏距离最远的页面进行替换;进一步,针对不同kNN查询的搜索空间大小差异非常大的特点,在LIRS替换策略基础上提出一种自适应替换策略,通过对HIR页面占缓存比例自动调整来适应不同的查询.综合两者,形成基于欧氏距离的自适应缓存页面替换算法AELIRS.大量实验表明,在缓存大小与搜索空间大范围变动中,AELIRS始终优于其他替换策略.With the thorough investigations and applications of the spatial database systems in recent years, a page replacement strategy, especially designed for spatial database according to the characters of data organization and queries, has become a new topic. Voronoi diagram, which is a very important spatial data organization technique, performs remarkably in kNN query processing due to its outstanding partition technique and adjacent property. Focused on the spatial database organized by Voronoi diagram, this paper firstly presents a Euclidean distance-based replacement strategy in which a page with the maximum space distance to the last access page will be evicted first. Then, considering the various range of search area in kNN query, we formulate an adaptive page replacement strategy based on the LIRS strategy, whose HIR＇s proportion of the buffer is self-tuning to adapt to different kinds of queries. Combing these two strategies, an adaptive Euclidean distance-based LIRS page replacement strategy named AELIRS is proposed, which uses LIRS to manage pages＇ history information and the Euclidean distance-based replacement strategy to choose evicted page. AELIRS can balance the temporal locality and spatial locality component dynamically, adaptively and continually. Extensive experiments show that AELIRS outperforms other strategies in a wide range of the buffer size and search area.

关 键 词：空间数据库 VORONOI图 替换策略 局部性 最近邻 

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