Introduction

Multidimensional data structures [25,30] have been widely applied in many data management areas. Indexing spatial data is their natural application but there are many applications in different domain areas. In the case of spatial data, structures often store two-and three-dimensional objects. In the case of multimedia data, there are spaces with dimension values of up to 100,000 to be indexed. There have been many data structures introduced in the past, e.g. R-tree [10], R * -tree [3], UB-tree [2], X-tree [5], and BUB-tree [7]. These data structures have been applied in many areas; the well-known R-tree is included in Oracle Spatial1 -an Oracle option for indexing spatial data. UB-tree [2] is applied for an implementation of more indices related to one table in the relational data model [23]. In addition, multidimensional data structures are applied in a wide range of applications, e.g. indexing XML data [9,15,14], terms [16,6], etc.

In the case of the R-tree, tuples are clustered in a tree's page when MBRs (Minimal Bounding Rectangles) are built. It supports various types of queries, e.g. point and range queries. As mentioned previously, multidimensional data structures may be applied as index data structures supporting the storage of tuples in relational or object-relational DBMS [8]. If B-tree or B + -tree are applied for the support, we must create one tree for each attribute to be indexed. Another alternative is to use the so-called compound-key which includes more attributes. In this case, some queries are processed by an often inefficient sequential scan. When we consider multidimensional data structures, one index is created for all attributes to be indexed. In this case, random accesses may influence the efficiency of query processing [19]. We must observe that the efficiency of range query processing in the B-tree is also influenced by this issue.

There are some applications where ordering of tuples in the result set is required. This order may be defined by ordering of values of one attribute. A common example is an SQL statement with the ORDER BY clause. In this case, we often define a restriction of attribute values, which means the range query can be applied for the processing of this query; however, we often require an ordering defined by the ORDER BY clause. If we consider multidimensional data structures, there is no support for the ordering; the result tuples must be sorted after the query is processed. Since the number of sort operations and the number of tuples in the result may be high in the case of DBMS, we must utilize an external sorting algorithm [13,29]. If large result sets are sorted, this operation is time consuming. When we consider a data structure without a support of ordering, we can not utilize lazy query processing. In the case of lazy query processing, a query is progressively processed and we can not store all tuples of the result in an additional data structure. When we consider multidimensional data structures without a support of ordering, this lazy evaluation is not possible; the query must be processed in one and result tuples must be inserted in a persistent data structure and sorted [20].

In this article, we introduce a multidimensional data structure with a support of ordering. A cost-based relational query optimizer [8] can simply utilize this data structure and decide when it is appropriate to utilize this data structure instead of common query processing and sorting of the result set. Since the Rtree is the most popular data structure we present the support of ordering for the R-tree.

Although it can be seen that there is a relation between multidimensional data structures and ordering, we only find data structures which enable the indexing of multidimensional data using an order. Such data structures include UB-tree [2,22] and BUB-tree [7] which utilize Z-ordering for indexing of multidimensional data. On the other hand, if we apply B-tree or B + -tree as the solution of this issue, a range query will be processed by an often inefficient sequential scan.

This paper is organized as follows: In Section 2, we present R-tree and its variants. We describe the motivation to the support of ordering in Section 3 in more detail. Section 4 includes some notices to ordering of the range query result. In Section 5, we describe our new variant of the R-tree and show the basic principles of this data structure. Experimental results are put forward in Section 6. In the last section we summarize the paper content and outline possibilities of our future work.

R-tree and its Variants

R-tree [10] can be thought of as an extension of B + -trees in a multi-dimensional space. It corresponds to a hierarchy of nested n-dimensional MBRs. If N is an inner page, it contains couples of the form (R i , P i ), where P i is a pointer to a child of the page N . If R is its MBR, then the rectangles R i corresponding to the children N i of N are contained in R. Rectangles at the same tree level may overlap. In this article, we consider only tuples stored in leaf nodes due to the fact that it corresponds to our application domain. Unless a page of the R-tree is the root, its number of entries is between m and M and it corresponds to a disk page. Other properties of the R-tree include the following:

-Whenever the number of a page's children drops below m, the page is deleted and its descendants are distributed among the sibling pages. The upper bound M depends on the size of the disk page. -The root page has at least two entries, unless it is a leaf.

-The R-tree is height-balanced; i.e. all leaves are at the same level. The height of an R-tree is at most log m N − 1 for N index records (N > 1).

Given a set of M +1 entries, each entry is assigned to one of the two produced pages, according to the criterion of minimum area, i.e. the selected page is the one that will be enlarged the least in order to include the new entry. It significantly affects the index performance. Three split techniques (Linear, Quadratic, and Exponential ) proposed in [10] are based on a heuristic optimization. R-tree performance is usually measured with respect to the retrieval cost (in terms of DAC) of queries. The majority of performance studies concerns point, range, and k-NN queries. Considering the R-tree performance, the concepts of page coverage and overlap between pages are important. Obviously, an efficient R-tree search requires that both the overlap and coverage are minimized. Minimal coverage reduces the amount of dead area covered by R-tree pages. The minimal overlap is even more critical than the minimal coverage, searching to objects falling in the area of k overlapping pages; up to k paths to the leaf pages, may have to be processed in such a way.

Variants of R-trees differ in the way they perform the split algorithm during insertions, i.e. which minimization criteria are used. Literature has identified a variety of criteria for the layout of keys on pages that affect retrieval performance. These criteria are: minimal page area, minimal overlap between pages, minimal page margins or maximized page utilization. It is impossible to optimize all of these parameters simultaneously.

Authors of [21,25] put forward many variants of the R-tree. The main feature of R * -trees [3] involves the page-splitting policy. Therefore, the R * -tree differs from the R-trees mainly in the insertion algorithm. Although original R-tree algorithms tried only to minimize the area covered by MBRs, the R * -tree algorithms also take other objectives into account. Clipping-based schemes do not allow any overlaps between bucket regions; they have to be mutually disjointed. A typical access method of this kind is the R + -tree [26] which allows no overlap between regions corresponding to pages at the same tree level and an object can be stored in more than one leaf page.

Other approaches to an improvement of original R-trees release some of their basic features. For example, the MBRs have been replaced by minimum bounding spheres or polygons. In [4], R + -trees are extended to support k-NN queries. In [17], authors introduce a variant for efficient processing of narrow range queries. In our best knowledge, R-tree variant supporting the ordered multidimensional data or multidimensional data structure supporting a general ordering do not exist in the literature.

Motivation

Although it can be seen that multidimensional indexing and ordering are in contradiction, there are real applications where we need to sort the range query result. Let us consider an implementation of indices in an RDBMS. Multidimensional data structures can be utilized for the implementation instead of more B-tree or B + -tree indices. Then an SQL statement is processed by a range query. Users often applied the ORDER BY clause which sorts a result set according to values of one or more attributes. In other words, we define an order on tuples of the result set.

A common way to evaluate these queries is to process the range query in a multidimensional data structure and sort the result set of the range query. Since the number of sort operations and tuples in the result can be high, we must utilize an external sorting algorithm [13,29]. In the case of large result sets the sorting is the time consuming operation. In this article, we introduce a multidimensional data structure supporting an order on multidimensional tuples. Since the R-tree is the most popular data structure, we present the support of ordering for the R-tree; we introduce the Ordered R-tree.

We assume that there are applications where we need always (or very often) use the ordering of a result set according the same attributes. We can apply B-tree or B + -tree indices for the support, but we must create one tree for each attribute to be indexed. Another alternative is to use so called compound-key which includes more attributes. In these cases some queries are processed by an often inefficient sequential scan. For example, let us consider the compound key

{A 1 , A 2 , A 3 } of a

Range Query Processing in R-tree

A range query is processed by a depth-first search algorithm [10]. If the query rectangle intersects an MBR then the node related to the MBR is retrieved and searched. In general, there is no order; therefore, tuples of a result set are sorted in the same order in which these tuples were inserted into leaf nodes and new MBRs were inserted into inner nodes. In the case of bulk-load algorithms, tuples are often sorted under an order and MBRs are created for these tuples [11]. We will show that the ordering of tuples in leaf nodes does not guarantee the ordered result set.

Example 1. (Range Query Processing) Let us consider two MBRs in Figure 1. A depth-first search range query algorithm retrieves tuples of M BR 0 1 (T 1 and T 2 ) and then it retrieves tuples of M BR 0 2 (T 3 and T 4 ); consequently, the result set includes:

T 1 , T 2 , T 3 , T 4 .

When we consider the previous depicted motivation, the ORDER BY clause, we want to retrieve tuples under the well-known Lexicographical order of tuples. This order is often utilized in the case of term ordering, however the ORDER BY clause applied on a set of ordered attributes works in the same way.

Definition 1. Lexicographical Order

Let Ω be an n-dimensional space and t 1 = (a 1,1 , a 1,2 , . . . , a 1,n ) and t 2 = (b 2,1 , b 2,2 , . . . , b 2,n ) be two tuples of this space. The Lexicographical order is defined:

t 1 < t 2 ⇐⇒ (∃m > 0)(∀i < m)(a 1,i = b 2,i ) ∧ (a 1,m < b 2,m ).

Example 2. Let us consider the space in Figure 1 and the Lexicographical order which prefers the attribute A 1 before the attribute A 2 . The tuples are sorted under this order as is follows: T 1 , T 3 , T 2 , T 4 . Let us consider space filling curves like C-curve, Z-curve or Hilbert curve [24] depicted in Figure 2. It is clear that the Lexicographical order is equivalent to C-ordering. One class of multidimensional data structures utilizes space filling curves. UB-tree [2,22] and BUB-tree [7] utilize Z-curve to order tuples, regions included in inner nodes are defined as intervals of the Z-curve. Another way is to use a space filling curve for clustering of tuples in a multidimensional space; however, regions are created according to a known data structure like R-tree. Examples of this way are Hilbert R-tree [12] or some bulk-loaded algorithms [11]. There are other data structures utilizing ordering to index multidimensional data [18] or applications which utilize ordering to multidimensional data processing, e.g. in [1] authors introduced a clustering methods based on an order.

There are two ways how to develop a data structure supporting an order. The first way is to create regions as intervals of the order used. The main problem of this way is that it is necessary to develop an algorithm checking if the MBR and the regions are intersected. This algorithm is then used by the range query algorithm. In [22,28] authors introduced this algorithm of UB-tree and Z-ordering. The similar algorithm must be implemented for each order used. The second way is to use a known data structure and change the build algorithm to guarantee the ordered result set. Since the R-tree is the most popular data structure we present the support of ordering for the R-tree.

5 Ordered R-tree

Introduction

Let us consider a total order O on a set of all tuples in a multidimensional space Ω = D 1 × D 2 × . . . × D n , where n is the space dimension. An MBR is defined by two tuples Q L and Q H . An MBR includes other MBRs in the case of inner nodes or tuples in the case of leaf nodes.

Definition 2. (MBR Order Condition)

Let us consider a total order O on all tuples of Ω. Let M BR 1 and M BR 2 be minimal bounding rectangles in the same level of the tree. MBR Order condition is defined as follows: M BR 1 ≤ M BR 2 iff each tuple of M BR 1 is lower or equal to all tuples of M BR 2 .

It is clear that if all couples of MBR's in each level of the tree meet the MBR Order condition, the result set of each range query is ordered under O. The first step to guarantee the order on tuples is to order tuples in each leaf node. The second step is to sort MBRs in each inner node. Since the R-tree is built by a hierarchy of MBR's which create different space regions compared to the regions created by the order, we can not order MBR's according to their Q L . In the next example, we show why we can not utilize Q L to the guarantee of the order on tuples in the R-tree.

Example 3. (Violation of the MBR Order Condition in the R-tree)

Let us suppose the M BR R in Figure 3(a) including tuples T 1 -T 4 . We use the order which prefers values of the first dimension before values of the second dimension. In this case, it is possible to split this node so that

Q L M BR1 ≤ Q L M BR2

and the MBR Order condition is met. A range query containing both MBRs returns the following correct result T 1 ,T 2 , T 3 , T 4 , where

T i ≤ T i+1 , 1 ≤ i ≤ 3.

After the tuple T 5 is inserted, M BR 1 and M BR 2 must be created to guarantee the order (see Figure 3(b)). In this case,

Q L M BR1 = (2, 3), Q L M BR2 = (2, 0), Q L M BR1 ≥ Q L M BR2

. A range query containing both MBRs, e.g. the range query represented by this statement: SELECT * FROM Ω WHERE A1 BETWEEN (2,4) and A2 BETWEEN(0,7) ORDER BY (A1,A2), where A i is the attribute corresponding to D i , 1 ≤ i ≤ 2, returns the following unordered result T 3 , T 5 , T 4 , T 1 , T 2 although tuples in both MBR's are ordered. It means, we can not utilize Q L to the guarantee of the order on tuples in the R-tree.

First Tuple Concept

To guarantee the MBR Order condition we must introduce the first tuple concept.

Definition 3. (The first tuple of an MBR)

Let O be an order on tuples of Ω and MBR be a minimal bounding rectangle. The first tuple of the MBR, F T M BR , is defined as follows: Since MBR of each node is stored in its parent node, we must handle first tuple of each node, except the root node, in an array to guarantee the tuple order.

F T M BR =

Operations of the Ordered R-tree

The main operation influenced by the Fist Tuple concept is the insert operation. In Algorithm 1 we see an algorithm of the insert operation including the first tuple management. For the sake of simplicity we do not differentiate between inner and leaf nodes as well as between inner and leaf items, therefore, we use overloading functions Insert and Split as well as overloading items and nodes. In Lines 1-6, the proper leaf node is found by an iteration through inner nodes, each inner node is put on the stack. In Lines 7-23, item is inserted in the node (Line 12) and indices are modified. The variable flagInsert is true if the Insert and Split operations are invocated in the current level of the tree. In this way, the changes of MBR are propagated to the root node.

On the other hand, the variable flagFirstTuple controls the propagation of FT to the root node. The procedure InsertOrUpdateFirstTuple works in this way: if the inserted tuple is the first tuple of the node, then insert or update this first tuple. In the procedure Insert, tuple (or MBR) is inserted in the leaf node (inner node). Items are sort-inserted in the both cases; in the case of inner nodes first tuples must be utilized. Obviously, the split operation utilizes the ordering when a node is split; the second node includes tuples > all tuples of the first node.

The find and range query operations are without any change. In the case of the delete operation, we must manage the update of first tuples. Consequently, find and delete operations work in O(log M ), where M is the number of tuples in the tree.

First Tuple Storage

To manage first tuples for all MBR's we can use a persistent array including all first tuples. This array contains couples (node id, first tuple), where node id references the tree node related to the first tuple. In Figure 4, we see an example of the proposed data structure. Since the size of the array is equal to the number of all nodes in the R-tree, we can often manage this data structure in the main memory; pages of this data structure are not retrieved from the secondary storage. For example, if the R-tree includes 10 6 tuples, the maximum number of items in leaf nodes is 200 and the maximum number of items in inner nodes is 100. The array includes approximately 12,000 items. Let us consider the space dimension=5, 4 B for one attribute value and node id, we get the total size of the array: 288,000 B = 281,25 kB. When we consider the delete operation, we can utilize hashing or B-tree for the implementation of the array. Fig. 4. A structure of the Ordered R-Tree

Experimental Results

In our experiments3 , we used the proposed real collection of meteorological data including 1,391,049 records. The scheme contains 6 attributes: STATION, ELEMENT, YEAR, MONTH, DAY, TIME. It means the space dimension is 6. The number of stations is 10; therefore, the attribute STATION has 10 possible values. The number of elements is 2. Other attributes include the time of the measurement for the station and element. All data structures have been implemented in C++. We built 2 data structures: R * -tree and Ordered R-tree. Their parameters are shown in Table 1. The page size 2,048 B is used for all trees. Data structures were built by a common tuple-by-tuple way. Since R-tree and Ordered R-tree create different regions, both build times are different for the same order of the inserted tuples.

In our experiments, we used 30 range queries with various selectivities; the result set includes 0-548,725 tuples. In Table 2, we show some queries in more detail. Terms min and max denote the minimum and maximum values of the domain, respectively. As usual, tests are processed with a cold cache (OS cache as well as cache buffer of indices). For all tests we measure query processing time and Disk Access Cost (DAC). Since in the case of R * -tree the range query's result set must be sorted, we measure the sorting time and DAC of the sort operation. For the time measurement, we repeat the tests 10× and calculate the average time. Since the range query is processed by random disk accesses, DAC is equal to the number of disk accesses during query processing [27]. We used Merge sort [13] as the algorithm sorting the result set. Although we show results of 10 queries in more detail, average results are calculated for all 30 queries. DAC results are shown in Table 3 and Figure 5(a). Whereas Table 3 includes DAC of the range query as well as sort operation, Figure 5(a) includes only DAC of the range query. Let us consider DAC of range query processing. We see that the DAC for the Ordered R-tree is 125% of DAC for the R * -tree. It is because the order influences the tree building. Although DAC for the range query and sort operation are not comparable due to the fact that it is simply possible to reduce the number of disk accesses using a cache buffer in the case of the sort operation, we see that DAC of the sort operation is enormous especially for queries with a large result set. Query processing time is shown in Table 3 and Figure 5(b). Moreover, Table 3 includes the time of the sort operation. We see that this time influences the query processing time especially for range queries with the large result set. We see that our Orderer R-tree saves 35% of the query processing time compared to the R *tree.

DAC of range query processing

Conclusion

In this article, we introduced a new data structure, a variant of the R-tree, supporting a storage of ordered tuples. In this way, the range query result is ordered without an application of any time consuming sort operation. Our experiments show an improvement of this data structure in comparison with the R-tree. Orderer R-tree saves 35% of the query processing time compared to the R * -tree. The new data structure is particularly efficient in the case of large result sets or in the case of lazy query processing when tuples are not retrieved immediately. In the case of the R-tree, range query must be processed completely and then the result set must be sorted. In our future work, we want to adopt this data structure for indexing XML data where the lazy query processing of ordered tuples can be applied.