Buffering a hierarchical index of multi-dimensional data

A computer-implemented method of adaptively buffering a hierarchical index of multi-dimensional data, the method comprising:

• maintaining a hierarchical index of multi-dimensional data items, wherein said index comprises a set of nodes;
• maintaining a buffer configured to store a subset of said set of nodes;
• determining a frequency with which each node in said set of nodes is accessed during a first set of index operations;
• and
• storing in said buffer a first subset of said set of nodes, said first subset comprising the nodes accessed most frequently during said first set of index operations.

A method of caching nodes of a hierarchical index during operations performed on a plurality of multi-dimensional data items represented by the index, wherein the index comprises a set of nodes having associated bounding regions, the method comprising:

• maintaining in a cache a first subset of the set of nodes;
• receiving a request for an operation involving the plurality of data items;
• accessing an uncached node not included in said first subset of nodes;
• determining a difference in size between the bounding region of a first node in said first subset of nodes and the bounding region of a second node in said first subset of nodes;
• determining which of said first node and said second node provides less caching benefit, wherein greater caching benefit is provided by a node having a larger bounding region than a node having a smaller bounding region;
• and
• storing said uncached node in said cache in place of said node providing less caching benefit.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of buffering a hierarchical index of multi-dimensional data, wherein said index comprises a set of nodes having associated multi-dimensional data regions, the method comprising:

• maintaining a set of multi-dimensional data items on a computer system;
• maintaining a hierarchical index of said multi-dimensional data items;
• maintaining a buffer configured to store one or more nodes of said set of nodes;
• storing in said buffer a first node of said set of nodes having a largest associated data region;
• repeating said storing for a node in said set of nodes having a next largest associated data region than the node just stored in said buffer until one of:
• every node in said set of nodes has been stored in said buffer;
• and
• said node having a next largest associated data region is too large to fit in said buffer;
• receiving a request for an operation on said data items;
• and
• accessing one or more of said buffered nodes during execution of said operation.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of caching nodes of a hierarchical index during operations performed on a plurality of multi-dimensional data items represented by the index, wherein the index comprises a set of nodes having associated bounding regions, the method comprising:

• maintaining in a cache a first subset of the set of nodes;
• receiving a request for an operation involving the plurality of data items;
• accessing an uncached node not included in said first subset of nodes;
• determining a difference in size between the bounding region of a first node in said first subset of nodes and the bounding region of a second node in said first subset of nodes;
• determining which of said first node and said second node provides less caching benefit, wherein greater caching benefit is provided by a node having a larger bounding region than a node having a smaller bounding region;
• and
• storing said uncached node in said cache in place of said node providing less caching benefit.

An apparatus for managing a set of multi-dimensional data items, comprising:

• a storage device configured to store a set of multi-dimensional data items;
• a processor configured to manipulate said set of multi-dimensional data items;
• a hierarchical index of said set of multi-dimensional data items, wherein said index comprises a set of nodes;
• and
• a buffer configured to store a subset of said set of nodes to facilitate access to said nodes during an operation on said set of multi-dimensional data items;
• wherein said subset of nodes is stored in said buffer in accordance with predetermined criteria including one or more of:
• the size of each node's bounding region, the frequency with which each node is accessed during a first series of operations on the set of data items, and the recency with which each node has been accessed.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of adaptively buffering a hierarchical index of multi-dimensional data, the method comprising:

• maintaining a hierarchical index of multi-dimensional data items, wherein said index comprises a set of nodes;
• maintaining a buffer configured to store a subset of said set of nodes;
• determining a frequency with which each node in said set of nodes is accessed during a first set of index operations;
• and
• storing in said buffer a first subset of said set of nodes, said first subset comprising the nodes accessed most frequently during said first set of index operations.