Importance

Loading Importance Indicators...

Abstract

Methods are provided for buffering nodes of a hierarchical index (e.g., R-tree, bang file, hB-tree) during operations on multi-dimensional data represented by the index. The methods are particularly suited for query operations, and a different method may be more suitable for one pattern of queries than another. Where queries are distributed in a relatively uniform manner across the domain or dataspace of an index, a node-area buffering method is provided. In this method nodes are cached or buffered in order of their respective areas (e.g., their minimum bounding areas), and a node having a smaller area will be replaced in cache before a node having a larger area. When, however, queries are not uniformly distributed, then a least frequently accessed buffering technique may be applied. According to this method statistics are maintained concerning the frequency with which individual index nodes are accessed. Those accessed less frequently are replaced in cache before those accessed more frequently. Yet another, generic, buffering strategy is provided that is suitable for all patterns of query distribution. In accordance with this method, whenever a node must be removed from cache in order to make room for a newly accessed node, cached nodes are compared to each other to determine which provides the least caching benefit and may therefore be ejected. A comparison may involve three factors--the difference in the nodes' areas, the difference in the frequency with which they have been accessed and the difference between their latest access times. These factors may be weighted to give them more or less effect in relation to each other.

Loading the Abstract Image...

First Claim