Efficiency Improvement of Narrow Range Query ⋆ Processing in R-tree

Abstract

Indexing methods for efficient processing of multidimensional data are very requested in many fields, like geographical information systems, drawing documentations etc. Well-known R-tree is one of the multidimensional data structures. The R-tree is based on bounding of spatial near points by multidimensional rectangles. This data structure supports various types of queries, e.g. point and range queries. The range query retrieves all tuples of a multidimensional space in the defined query box. Narrow range query is an important type of the range query including at least one narrow dimension. Despite many variants of R-trees, narrow range query processing is inefficient. In this paper, we depict a modification of Signature R-tree: data structure for the narrow range query processing. This data structure applies signatures for a description of tuples stored in a tree's page. We present an improvement of this technique.

Keywords

• multidimensional data structure
• narrow range query
• Rtree
• signature

-

Multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. Processing of multi-dimensional data is requested in almost all fields. There are a lot of applications of multi-dimensional data structures [ 15 ], e.g., data mining [ 10 ], term indexing [ 5, 12 ], XML documents [ 8, 11 ], text documents and images [ 4 ]. Query processing in high-dimensional spaces has therefore been a very prominent research area over the last few years. A number of new index structures and algorithms have been proposed.

There are two major approaches to multi-dimensional indexing [ 16 ]: data structures for indexing metric spaces and data structures for indexing vector spaces. The first approach includes, for example, n-dimensional B-tree [ 7 ], Rtree [ 9 ], R*-tree [ 2 ], Signature R-tree [ 13 ], X-tree [ 3 ], UB-tree [ 1 ] and BUBtree [ 6 ]. The second one includes M-tree [ 4 ], for example.

A multi-dimensional data structure often supports the range query. This query may be written as the following pseudo SQL statement: SELECT * FROM T WHERE ql1 ≤ t1 ≤ qh1 AND . . . AND qln ≤ tn ≤ qhn.

The narrow range query is special type of the range query, where at least one dimension is narrow. In Figure 1, we see examples of query boxes for the narrow range queries in spaces with the dimensions n = 2 and n = 3, respectively. Another example of this query is the following SQL statement: SELECT * FROM <table name> WHERE 1 < a0 < 10000 AND a1 = 2 AND a2 = 3

In paper [ 13 ], we depicted that the narrow range query processing is rather inefficient in current multidimensional data structures. Signature R-tree, handling point data, is introduced in this work. In our paper, we describe an improvement of the Signature R-tree called ESR-tree. In Section 2, we review existing approaches for the narrow range query processing. Section 3 presents our improvement of the Signature R-tree. Section 4 reviews possibilities of signature building for this data structure. In Section 4.3, we outline some implementation details of the improved data structure. In Section 5, we put forward experimental results. Finally, we conclude with a summary of contributions and discussion about future work. 2

Existing Approaches In this section, we describe two data structures which have been often applied for the narrow range query processing. These data structures, B-tree and Signature R-tree, are compared with the novel ESR-tree in Section 5. 2.1

B-trees The B-tree is an m-ary balanced tree introduced by Bayer in 1972. This structure guarantees the logarithmic complexity for the item searching. Due to the ordering, B-tree enables searching only by one attribute. In many cases, it is necessary to search by more than one attribute. Therefore, there are some improvements of B-tree for searching of multidimensional data, e.g. B-tree with compound keys. In this case, we create one compound index with keys related to each narrow dimension. Obviously, this technique is not as general as multidimensional data structures. For example, we create the compound index for dimensions 1, 3, and 10 for a 10-dimensional tuple collection. It means, narrow range query with these narrow dimensions is as efficient as possible. Moreover, no intermediate results are created. If want to process a query with the narrow dimensions: 1, 3, 10, and 5, we retrieve an intermediate result again. If we want to solve a general query without the intermediate result, we should create n! compound indices. Therefore, we do not suppose this technique in our article.

If the range query is concerned in B-tree, we must index each attribute (or dimension) in a separate B-tree. The range query is processed by a sequence of searching in B-trees, and individual intermediate results are joined. Obviously, there are two issues. If the size of an intermediate result >> the overall result, this processing is rather inefficient. The second issue is the size of the index file. In Section 5, we use this implementation for a comparison with our method. We propose that the index file built in this way is 3× larger in average than the index file of a multidimensional data storage. 2.2

Signature R-trees Since 1984 when Guttman proposed his method [ 9 ], R-trees have become the most cited and most used as reference data structure in this field. The R-trees can be thought of as an extension of B-trees in a multi-dimensional space. It corresponds to a hierarchy of nested n-dimensional minimum bounding boxes (MBB). There are many approaches based on an improvement of original Rtrees. In [ 13 ], Signature R-tree was introduced for more efficient processing of narrow range queries.

Signature R-tree is a variant of the R-tree including multidimensional signatures for a more efficient filtration of irrelevant tree nodes. In this case, irrelevant node does not contain any tuple of the query box. The multidimensional signature contains a signature of tuples in the node for each dimension (see Section 4.1). A general structure of the Signature R-tree is presented in Figure 2. Leaf nodes include tuples clustered into MBBs (MBB is defined by two multidimensional points). These MBBs are clustered into super-MBBs as well. This hierarchy is finished by MBBs in the root node. Consequently, MBBs are stored in inner nodes. In the case of Signature R-tree, the multidimensional signature is assigned to each MBB. It means that each inner node item includes the MBB definition together with multidimensional signature, where this signature is superimposed with signatures of the node’s children. Consequently, such a tree contains two hierarchies, the hierarchy of MBBs and hierarchy of signatures.

In [ 13 ], we show that many irrelevant nodes are skipped during the narrow range query processing if we compare Signature R-tree and R-tree. However, we distinguish some negative consequences of this data structure. If signatures are long, the inner node capacity is low. This issue results in a degeneration of the tree: inner node can contain only a trivial number of items and, therefore, the height of the tree is very high. Similar issue appears if we use more hash functions for each signature. Therefore, in this paper, we introduce an improvement of Signature R-tree supporting these refinements. 3 3.1

ESR-Tree – An Improvement of Signature R-tree

Introduction Signature R-tree significantly decreases the number of processed irrelevant nodes, however the number > 0 (see Section 6). In [ 13 ], we introduced the following quality measurement of the range query processing (so called relevance): cQ = Nr/Np, where Nr is the number of relevant nodes, Np is the number of all processed node. Obviously, if only relevant nodes are processed during a range query then cQ = 1.

If we want to reach the most efficient cQ value, we must use longer signatures, a higher number of hash functions (it means more signatures is related to one dimension), signatures with different lengths for different levels of a tree, and various hashing functions building the signatures. However, in the case of Signature R-tree, each this idea extends the size of inner node item and decreases the inner node capacity. Therefore, our improvement of Signature R-tree, called ESR-tree, removes signatures from inner nodes: the signatures are stored in a persistent array. A structure of the novel ESR-tree is presented in Figure 3.

The isolation of signatures from R-tree enables to enlarge signatures although the node capacity is not decreased. Moreover, we can use signatures with different lengths for different levels of the tree. In our paper, we use the inverted level number for the signature labeling. Consequently, we use S0 as the label of an MBB’s signature, S1 as the label of a super-MBB signature, and so on. Operations Insert, Delete and Find (or point query) are handled by algorithms of the selected R-tree variant. In the case of the Insert operation (see Algorithm 1), we must update the signature of the MBB which was changed. In this way, we must update signatures for each level of the tree from the current node to the root node. In this algorithm, we use the following variables: tuple is an inserted tuple, Z represents a stack containing the current path of the tree, and N is the current node.

Signature index may be created after all tuples are inserted into the tree. This bulkload algorithm must preordered process all tree nodes and create the signature for each MBB. Obviously, signatures may be created for an arbitrary level of the tree.

A common issue of ESR-tree is that the query processing efficiency of a common range query is not influenced by signatures. Signature R-tree includes signatures in tree’s nodes, therefore, signatures are read from the secondary storage although these signatures are not used for the node filtering. On the other hand, in the case of the narrow range query, we apply signatures for the more efficient filtration of irrelevant tree nodes.

Let us suppose the range query algorithm. Intersection operation computes whether an MBB is intersected by the query box in the linear time, on the other hand, AND operation is used as a test of the signature matching. If both operations are matched, the child node is processed.

Delete operation is based on the algorithm of the R-tree variant used. It is necessary to mention that after the item is deleted, unperfect signature may be related to the leaf node containing the deleted item. It means that the signature may contain bits describing a tuple that is not included in the R-tree anymore. Signatures for higher levels of the tree may be unperfect as well. Consequently, we may correct the signatures related the changed node. The complete description of this operation is out of scope of this paper. Algorithm 1: Insert algorithm

N .AddSignature(tuple.GetSignature()); splitted ← true ;

Signature Generating

Signature Methods

The signature is a bit string formed from the terms which are used to index records in a data file [ 14 ]. Each term is converted to a bit string by the hashing function. The number of 1’s in the signature S is called weight γ(S). In the case of a query, we build the query signature in the same way as record signatures have been created. If the query signature has 1’s in the same positions as the record signature, the record can be considered as a potential match. There can be a case where a record signature matches a query signature, however the record itself does not satisfy the query. This is called the false drop. 4.2

Signature Generating for the Irrelevant Node Filtering

The Hamming distance is applied for measuring of the signatures similarity. Signature data structures like S-tree [ 14 ] are based on clustering of signatures with the minimal Hamming distance. However, R-tree clusters tuples into MBBs. Nodes do not contain tuples with the minimal Hamming distance. If signatures of tuples in an MBB include many true bits, then the MBB’s signature contains almost only true bits. In this case, irrelevant node filtering is not successful. Consequently, one true bit is set for one tuple coordinate and the query signature includes only one true bit for each dimension. In other word, weight of the query signature is rather low.

Our improvement is based on the following assumptions. Query signature weight should be closed to 0.5 as it is known in signature methods [ 14 ]. However, signature weight for all tuples of an MBB should be closed to 0.5 as well. These two assumptions are in a contradiction. In this paper, we set more bits as well as we use more hashing functions for one tuple coordinate. In Section 5, we show the efficiency improvement of these novel features. 4.3

Implementation In the case of ESR-tree, signatures are stored out of the R-tree. In this way, tree height is not influenced by the signature length. The relation between an MBB and its signatures is provided by a conversion table. The conversion table contains couples hnode index in the R-tree, signature index in the persistent data structurei. 5

Experimental Results In our tests1, we compare ESR-tree with Signature R∗-tree, R∗-tree, and the proposed B-tree-based implementation. We have implemented B+-tree, R∗-tree, and ESR-tree in C++. Three collections have been chosen for these tests. We created two random collections with million tuples of dimensions 2 and 10. The third collection represents a set of paths in an XML document [ 11 ]. These paths are modeled as 10-dimensional tuples. All collections have been inserted into the multidimensional data structure (see Table 1 for index characteristics). In our experiments, we do not use the Signature R-tree, we use signatures with one true bit generated for one tuple coordinate as the Signature R-tree uses this. We call this signature as the simple signature. This fact has a significant impact on DAC as well as query processing time. However, result relevances are credible for a comparison of Signature R-tree and ESR-tree.

Efficiency of the narrow range query processing was measured by DAC, cQ, and query processing time. Tested range queries have various number of narrow dimensions |Nrq|. The 2 kB page size and random accesses are applied in the case of all data structure, therefore, we can measure DAC by the number of MBs read in the secondary storage. 1 The experiments were executed on an AMD Opteron 865 1.8Ghz, 2.0 MB L2 cache; 2GB of DDR333; Windows 2008 Server. In Table 2, DAC results are presented for the random collection of dimension 2. We use 2 hashing functions and 3 true bits in the signatures. Results are average values of 10 various queries. We measure DAC for R-tree (RT) and signature data structure (SA).

Obviously, DAC is 4× lower if we compare the R-tree and ESR-tree with the leaf signature of the length 512. DAC of signature reading is an essential part of overall DAC, therefore, we can not use longer signatures. Table 3 including the query processing time supports this conclusion. This time is 5.25× lower than in the case of R∗-tree. Obviously, we see that ESR-tree saves 20% of the query processing time of the simple signature.

Another view of the trend is the higher values of relevance. We use the various count of hashing functions, more true bits of the signature as well as various signature lengths. In Table 3, relevances for leaf and overleaf nodes are presented. Relevance rapidly increases with the increasing signature length. Summary Table 4 presents results for the relevance > 0.9. We suppose that the signature weight should be closed to 0.5. In the case of this experiment, we get the signature weight in the range 0.38 – 0.51. The second collection includes 10-dimensional randomly generated tuples. 3 narrow dimensions of range queries are used. In this case, we can use shorter signatures than in the case of the first test. It seems that this 10-dimensional space is sparser than the 2-dimensional space, therefore, shorter signatures can describe the tuple distribution as well. In Table 5, we can see that DAC of ESR-tree is much more lower than DAC of R∗-tree. The query processing time is improved 9×. Obviously, we can see the importance of overleaf signatures in this case. Summary Table 6 presents results for the relevances > 0.9. Third collection contains a set of paths in an XML document. We test 15 range queries Q1–Q15 with various narrow dimensions. We use the same signature lengths as in the case of the second collection. In Table 7, DAC and cQ are put forward. We use signature lengths 256/3584 with 2 hashing functions and 3 true bits. We see that the cQ of Signature R∗-tree significantly increases in the comparison with the common R∗-tree. Obviously, this relevance is not sufficient in many cases. ESR-tree overcomes the Signature R∗-tree and R∗-tree. In this test, we compare the efficiency of ESR-tree and B-tree (one B-tree was created for each dimension). We use the queries from the previous test. The join operation takes the most processing time (see Table 8). Obviously, B-tree is much more efficient in the case of small intermediate results. With the increasing size of intermediate results, join processing time increases. Table 8 includes information about all queries. We measure DAC for B-trees (BT) and tuple array (TA) including whole tuples. Obviously, ESR-tree clearly overcomes this B-tree based implementation, DAC is 7.5× lower in the case of ESR-tree. Another important issue is the index size. In Table 9, we see that the index size of the ESR-tree is 3× lower in all tested cases. The experiments show an significant improvement, e.g. applications of two hashing functions causes double increasing of the relevance. 6

Conclusion In this article, we present an improvement of Signature R-tree, data structure for the efficient processing of narrow range queries. Moreover, we introduce an enhanced signature creation that provides more efficient filtration characteristics. Since signatures are relevant only in higher levels of a tree, it is not appropriate to handle them to each MBB of an inner node. We show some advantages of longer signatures, however longer signatures mean the lower node’s capacity. Consequently, we put signatures of each MBB in a special data structure: a persistent array. In our experiment, we test range queries and compare the efficiency of our approach with R-tree, Signature R-tree, and B-tree based implementation. From DAC point of view, ESR-tree is up to 3× more efficient than R-tree and 6× than B-tree. Obviously, DAC of the signature retrieval is often rather high. Therefore, we want to develop a more efficient data structure for the storage of signatures. Query |Nrq|

References

1. R. Bayer . The Universal B-Tree for multidimensional indexing: General Concepts . In Proceedings of WWCA'97 , Tsukuba , Japan, 1997 .

2. N. Beckmann , H.-P. Kriegel , R. Schneider , and B. Seeger. The R ∗ -tree: An efficient and robust access method for points and rectangles . In Proceedings of the 1990 ACM SIGMOD , pages 322 - 331 .

3. S. Berchtold , D. A. Keim , and H.-P. Kriegel . The X-tree: An index structure for high-dimensional data . In Proceedings of the 22nd International Conference on VLDB , pages 28 - 39 , San Francisco, U.S.A., 1996 . Morgan Kaufmann Publishers.

4. P. Ciaccia , M. Pattela , and P. Zezula . M-tree: An Efficient Access Method for Similarity Search in Metric Spaces . In Proceedings of 23rd International Conference on VLDB , pages 426 - 435 , 1997 .

5. V. Dohnal , C. Gennaro , and P. Zezula . A Metric Index for Approximate Text Management . In Proceedings of IASTED International Conference Information Systems and Database - ISDB 2002 , 2002 .

6. R. Fenk . The BUB-Tree . In Proceedings of 28rd VLDB International Conference on VLDB, Hongkong, China , 2002 .

7. M. Freeston . A General Solution of the n-dimensional B-tree Problem . In Proceedings of SIGMOD International Conference , San Jose, USA, 1995 .

8. T. Grust . Accelerating XPath Location Steps . In Proceedings of ACM SIGMOD 2002 , Madison , USA, June 4-6, 2002 .

9. A. Guttman. R-Trees : A Dynamic Index Structure for Spatial Searching . In Proceedings of ACM SIGMOD 1984 , Annual Meeting , Boston, USA, pages 47 - 57 . ACM Press, June 1984 .

10. N. Karayannidis , A. Tsois , T. Sellis , R. Pieringer , V. Markl , F. Ramsak , R. Fenk , K. Elhardt , and R. Bayer . Processing Star Queries on Hierarchically-Clustered Fact Tables . In Proceedings of VLDB Conf . 2002 , Hongkong, China, 2002 .

11. M. Kr´atky´, J. Pokorny´, and V. Sn ´aˇsel. Implementation of XPath Axes in the Multidimensional Approach to Indexing XML Data . In Current Trends in Database Technology, Int'l Conference on EDBT 2004 , volume 3268 . Springer-Verlag, 2004 .

12. M. Kr´atky´, T. Skopal, and V. Sn´aˇsel. Multidimensional Term Indexing for Efficient Processing of Complex Queries. Kybernetika, Journal , 40 ( 3 ): 381 - 396 , 2004 .

13. M. Kr´atky´, V. Sn´aˇsel, P. Zezula , and J. Pokorny´. Efficient Processing of Narrow Range Queries in the R-Tree . In Proceedings of IDEAS 2006 . IEEE CS Press, 2006 .

14. Y. Manolopoulos , A. Nanopoulos , and E. Tousidou . Advanced Signature Indexing for Multimedia and Web Applications . Kluwer, 2003 .

15. Y. Manolopoulos , Y. Theodoridis , and V. Tsotras . Advanced Database Indexing . Kluwer Academic Publisher, 2001 .

16. C. Yu . High-Dimensional Indexing . Springer-Verlag, LNCS 2341 , 2002 .