A new range query algorithm for Universal B-trees

Tomáš Skopal

doi:10.1016/j.is.2004.12.001

2006-09-01

PRE

DOI：10.1016/j.is.2004.12.001

原文链接

原文求助

摘要

En 中文

In multi-dimensional databases the essential tool for accessing data is the range query (or window query). In this paper we introduce a new algorithm of processing range query in universal B-tree (UB-tree), which is an index structure for searching in multi-dimensional databases, The new range query algorithm (called the DRU algorithm) works efficiently, even for processing high-dimensional databases. In particular, using the DRU algorithm many of the UB-tree inner nodes need not to be accessed. We explain the DRU algorithm using a simple geometric model, providing a clear insight into the problem. More specifically, the model exploits an interesting relation between the Z-curve and generalized quad-trees. We also present experimental results for the DRU algorithm implementation. (C) 2005 Elsevier B.V. All rights reserved.

Keyword:

spatial access methods

multi-dimensional indexing

range query

UB-tree

DRU algorithm

Z-region

space filling curves