An Adaptive Page-Replacement Strategy for Spatial Database Systems

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.