Spatial R-Tree Index Based on Grid Division for Query Processing

International Journal of Database Management Systems ( IJDMS ) Vol.9, No.6, December 2017 DOI : 10.5121/ijdms.2017.9602 25 S PATIAL R-T REE I NDEX B ASED ON G RID D IVISION FOR Q UERY P ROCESSING Esraa Rslan 1 , Hala Abdel Hameed 1 and Ehab Ezzat 2 1 Faculty of Computers and Information, Fayoum University, Egypt 2 Faculty of Computers and Information, Cairo University, Egypt A BSTRACT Tracing moving objects have turned out to be essential in our life and have a lot of uses like: GPS guide, traffic monitor based administrations and location-based services. Tracking the changing places of objects has turned into important issues. The moving entities send their positions to the server through a system and large amount of data is generated from these objects with high frequent updates so we need an index structure to retrieve information as fast as possible. The index structure should be adaptive, dynamic to monitor the locations of objects and quick to give responses to the inquiries efficiently. The most wellknown kinds of queries strategies in moving objects databases are Rang, Point and K-Nearest Neighbour and inquiries. This study uses R-tree method to get detailed range query results efficiently. But using R-tree only will generate much overlapping and coverage between MBR. So R-tree by combining with Gridpartition index is used because grid-index can reduce the overlap and coverage between MBR. The query performance will be efficient by using these methods. We perform an extensive experimental study to compare the two approaches on modern hardware. K EYWORDS MOD, Spatial indexing, R-tree, grid. 1. I NTRODUCTION Moving object applications have become very important in our life and have a lot of usages, such as GPS car navigator and location-based services. Moving object database is a branch of the spatial-temporal database research that has been developed recent years, indexing moving object is one of the key technologies of the moving object database. Tracing the changing positions of objects has become a serious matter and played an essential role in location-based services, such as customers with cell phones and cars. These services need to know the current positions of objects quickly. The index structure should be adaptive and dynamic to keep track of the positions of objects and to provide quick answers to the expected queries [1]. An example for this is the traffic observing service for a population of 10 mega moving objects that are processed with speed 15 m/s. Another example is related to expecting objects positions of an exactness of no less than 100 meters. In this situation, we need up to 1 mega update rate every second. As the update frequency is growing, the workloads are also increasing. High workloads in Sidlauskas’s paper can't be managed by traditional disk-based techniques [2]. Rather, we propose a primary memory index that is compatible with the characteristic of parallelism accessible in multicore processors. The main goal of the index structure is to keep up a reliable database and get back the right results. Indexing techniques are divided into two main groups: tree based and grid based index. Examples of tree based index are R-tree and its variations R+tree, R*tree, TPR-tree and TPR*tree (Time International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 26 Parametric Rectangle) [3]. Examples of grid based index are a uniform, parallel, hierarchical, and LU (Luzy Update) grid. There are also many kinds of queries, such as point query and density query. The R-tree is famous for its efficiency to support information skew and various query types. It can be used to index moving objects in a specific region. The idea of the index structure is to utilize the Minimum Bounding Rectangle (MBR). In any case, due to overlapping between MBRs, the search might be necessary along different paths causing the exceeding of search paths [4]. With the expansion in the amount of index data, it will require more storage space. Subsequently, it will truly influence the search and update efficiency. Though R-tree is known for its power to support various query types, the main problem with the R-tree is its bad update leverage. On the other hand, using a grid index in moving objects is considerably faster than an R-tree in an update and query processing. It is obviously discernible and it can straight forwardly calculate all objects overlapping with the range query with no need to access the index entities. In this paper, a robust and scalable index technique is proposed. The main goal is to build a hybrid index technique that supports a different number of queries with the minimum cost update. We used the R-tree and grid index together by using R-tree at the root node and grid at the leaf node to achieve two main benefits. The important benefit is to take the advantage of the two indexes as the R-tree is good for searching and querying. Also, grid is efficient in update operations. Experimental studies have shown that the design of the index may help provide answers to range queries with a great number of moving objects. To verify the efficient and effectiveness of the three types of indexes (R-tree, Grid, and hybrid R-tree and Grid), we explore several experiments to make a comparison between them based on the response time with a range queries and the CPU time in updating objects. The remaining parts of this paper are organized as follows: in section two we introduce the background and related work; the aim herein is to briefly explain the R-tree structure and grid. In section three, the proposed index technique and associated algorithms are explained. In section four, an analysis of the index structure and the experimental results are shown. The conclusion is presented in section five. 2. B ACKGROUND A ND R ELATED W ORK In this section, we introduce two main types of moving objects indexing techniques: tree and grid based indexes. 2.1. Tree Based Index R-tree is a height balanced tree (all leaf nodes are at the same height). It consists of internal nodes and leaf nodes. The R-tree is known for its robustness to data skew and it supports different types of queries. Yet, it is poor in update performance. Numerous applications including indexing the location of moving objects display workloads described by updates expansion to continuous queries. Indexes are divided into two categories based on data to be stored: (1) indexing the historical location of objects and (2) indexing the current location and predicting the future location of moving objects [3]. An overview of spatial-temporal access techniques can be found in the two papers [5,6]. The two surveys focus on the indexing of past, current, and future objects' positions. Indexes are divided into two parts: the first part is from 1980 to 2003, such as the TPR-tree, the TPR*-tree, the Bxtree, and the Bdual-tree, STRIPES definition of spatial index is “the primary key to improve the efficiency of queries”; the second part dates back to the period from 2003 to 2010, such as MON tree, RTR-tree TPR-tree, Bx-tree and ST2B-tree. International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 27 Guttman[7] first presented an index structure called R-tree for spatial searching. It's known that R-tree is inefficient in update performance because of overlapping and the splitting of MBR, though it is efficient in supporting different types of queries. Six variants of R-tree variants are compared in Manolopouloset al.[8]. The most famous spatial techniques that utilize minimum bounding rectangles are R-trees [6]and their variation R-trees. In TPR-tree that expands the R-tree as objects move in linear motion function. Tao introduced the TPR*-tree that enhances the TPRtree with advanced insert, update, and delete process. R-tree, TPR-tree, and TPR*-tree have low efficiency in updates because of their node splitting and reinsertion operations. Other than Rtrees, B-trees, and Quadtrees[9] ,some indexes can likewise be utilized to moving entities. The B+-tree, proposed by Jensen et al.[10] utilizes space filling curves like Hilbert curves or Z-curves that are used in mapping dimensional locations. 2.1.1 Structure R-tree consists of internal nodes and leaf nodes [11]. The internal node has pointers to other nodes; leaf node has pointers to objects (entries). As shown in figure 1, R-tree satisfies the following properties: 1. Every leaf node has between m and M entries unless the node is the root node, where M is the maximum set of records in a node, m is the minimum number of records that can be held in a node and let m<=M/2. 2. For every index entity (I, tuple-identifier) in a leaf node, I is the smallest rectangle that has the object and tuple-identifier is a unique number that identifies the record in the database. 3. Each non-leaf node contains between m and M children. 4. For each entry (I, child-pointer) in a non-leaf node, I is the smallest rectangle that overlays all the rectangles in the child node, the child-pointer is the address of the lower node. 5. The root node contains at least two child nodes unless it is a leaf. 6. All leaf nodes should be at the same grade. Figure 1. An example of R-tree International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 28 Figure 2 shows the structure of R-tree in on every node, there are Node Size (ns) number of each node and Minimum Children (mc) a fraction of the full nodes which are the essential attributes in the R-tree [12]. A leaf node contains node metadata like a number of entries, MBR, leaf flag, the id of the parent node, a number of leaf entries and a pointer to the parent node at the end. Likely, internal node consists of the same metadata fields in the leaf node, but the differences between them are the child pointer and MBR, where the MBR is the smallest rectangle that gathers the spatial entities together. Figure 2. Structure of R-tree 2.1.2 Update, Insertion, and Deletion Every update operation deletes the object from place and inserts it in another one. Assume the point P (oldX, oldY) is needed to be updated; first we search the tree from root to leaves until we find the node with MBR that have point P (oldX, oldY), more than one path are visited because of the overlapping between MBRs, then delete the point, but be careful that no underflow occurs (less than the minimum number of entries, often denoted as m). After the deletion operation is done, the insertion is applied. The insertion traverses the tree from root to leaves to find the suitable leaf node and insert (newX, newY). Insertion may cause overflow node (extends the maximum number of objects denoted as M). There are many variations of the R-tree in the literature; the uniform R-tree in is only considered. 2.1.3 Query Processing Two main types of queries are discussed: Range Query and K-nearest neighbour query. A range query is processed by accessing the tree from the root to the leaves if the present node is not a leaf; check every internal node MBR that intersects or overlaps with the MBR of the range query. 2.2 Grid Based Index Grid is a pre-defined partitioning index in which the region is partitioned into rectangular cells because it indicates the pre-defined spatial region. Grid covers a part of the space that object position is inside the boundaries of a grid cell and this object belongs to this cell. Šidlauskaset al [12] proposed the grid index which is one of the principal framework index structures for moving International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 29 objects database. D-Grid [13] enhances U-Grid which it indexes both the location and velocity of moving objects in the dual space. The dual space is a 2-dimensional Euclidean space, with a first dimension for velocity and the other for location. Another index structure that is based on grid cell and continuous k-nearest neighbor query processing is proposed by Wei Zhang [14]. Existing Concurrency Control (CC) methods for multidimensional indexes are also introduced like Šidlauskaset al. [15] who proposed the TwinGrid and the PGrid[16]give high query and update performance. PGrid makes various duplicates of information on a request and at the object granularity (i.e., non-local objects). 2.2.1 Structure Grid is a 2-d array that every cell in the array matches to a square cell with a length of grid cell size. Every grid cell in the array has a link to a list of buckets which contains the data object [12]. Each bucket has bucket size bs and metadata fields where metadata contains the next bucket, the number of entries and pointer to the next bucket. Grid is defined by two main parameters: gcs, and bs. Figure 3. Grid index structure 2.2.2 Update, Insertion, and Deletion All updates operations are classified into two sets: local and nonlocal. The update is considered local when the new object location falls in the same cell and we need only to change the (oldX, oldY) with the (newX, newY). Otherwise, the update is non-local (new location not in the same cell) as the object will be deleted from its current cell, and it will then be inserted inside the new cell. During the insert operation, the new object is always put at the end of the first bucket. In the condition that the first bucket is complete and has no space, a new bucket is created and the pointers are upgraded to make the new bucket the first one. If the first bucket is empty, the next bucket becomes the first one. 2.2.3 Query Processing The range query divides the cells, which overlap in the range query into two categories: the completely and the partly covered cells. Only the objects that are partly covered are needed to be listed in order to know if they are inside the range or not. KNN algorithm is known by a point P and the numbers of nearest neighbour k, cells are divided into different sets. Every set has the minimum range to the point P. Similar to the KNN query in the tree index, the queue is used to store these cells as they are sorted from the nearest to the farthest. International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 30 3. P ROPOSED I NDEX T ECHNIQUE R-tree and grid-partition index is proposed, which give execution enhancements in handling different types of queries like range and KNN queries. The proposed index has two main standard data structures: the first is the R-tree and the second one is a grid index. The R-tree is used to divide the space into MBRs then a grid is used in non-leaf nodes to store the data object and to reduce the overlapping between MBRs.In grid implementation, divide space into M x M grid of squares, create linked list for each square, use 2D array to directly access relevant square. It performs less maintenance effort as no grid changes are needed to be done in a grid updates. It is known that if the number of objects increases a lot of overlapping and converging between MBRs will be generated, approximately; each single update will need about four tree traversals affecting the performance significantly. To reduce node splitting in the R-tree, a grid is used to store data objects at leaf level. The performance of grid in inserting, deleting, and updating algorithms is superior to the R-tree, so it can highly decrease the time complexity of an algorithm. Extensive and broad experiments reveal that our proposed index structure essentially outperforms and beats the existing grid index or R-tree index in single threaded environments. As shown in figure 4, the index structure has two data structures: the root level is R-tree and each non leaf node is in a grid index structure, taking the advantages of both Tree and Grid index. Rtree is very powerful in supporting different types of queries with minimum time response. In addition, the grid is the best choice in updates because no grid re-adjusting should be done through updates, also grids require less repair effort and index speed is quick. We take the advantage of each one of these indexes in update and query processing. In a query range, grids can number all index objects that cover the range query with no need to access to the index records. Figure 4. The new index structure International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 31 3.1 Index structure The R-tree is used to implement both root and parent levels, which utilize the MBR to partition the regions, and child node uses a grid to implement MBR with equal sized cells. The grid needs insignificant update costs. Hence, no framework re-adjusting is done when objects change their locations. The index structure is as follows: 1. It has a root node in R-tree. 2. Non-leaf node contains the internal nodes that have the tuple <mbr, ptr> where the mbr is the minimum bounding rectangle of the node and ptr is an indicator to point to the next level node. 3. Leaf node is in grid coordination that divides the MBR into M x M cells, the grid is a 2-d array that every cell in the array matches to a square cell with a length of Grid Cell Size (gcs). 4. At leaf node, grid squares store a pointer to the list of buckets which have the object data. In a huge size of data, getting the relationships from the grid index can highly minimize the complexity of the algorithm in contrast to the conventional R-tree methods. Grid coordinate makes the position of spatial entity objects clear, so reduces the repetition of storage. Also, to avoid the search operation costs. 3.2 Update, Insertion, and Deletion The R-tree operates every update as a companion of two processes: delete and insert, traversing the tree topdown to locate the suitable leaf and update it. Algorithm 1 is proposed for inserting the new object. The algorithm takes a new object as an input with a unique id, and then inserts it at the index. The first step, the algorithm searches the tree from the root t to leaf to find the suitable child node by searching in the node of min.x≦x≦max.x in x-dimension according to MBR coordinates (min.x, min.y, max.x, max.y) of this object. If it is true, go to the second step, then go to the fourth step. The second step, if the MBR is found, the insertion operation is done by inserting the object into the suitable grid cell based on (x, y) of the new object as the child node is implemented in grid coordination. The third step, the new object is always put at the end of the first bucket in the grid. If the first bucket is complete and has no space, a new bucket is created and the pointers are upgraded to make the new bucket the first one. Otherwise, the first bucket is empty, and then the following bucket is the first one. The first free location at the end of the bucket is located, and the new record is also inserted. The fourth step, if the no MBR is found, create a child node approximate to X-value, Y-value and its leaf node (x, y) and insert the new object into the grid expressed by the leaf node. Algorithm1: insert (ObjectTuple new(n), Cell cell) 1. Search object n in tree 2. if tree is non-leaf // then for each entry in n do 3. if EI overlaps n // true… insert new object in the index 4. firstBucket= *cell ; // the 1st bucket is equal to reference cell 5. if Full(firstBucket) // if firstbucket is full ..create new bucket and make it first ; 6. freePosition= firstBucket.entries[firstBucket.nO] // first free location of the first bucket is located 7. insertObject(n, freePosition); // the new object is inserted 8. elseCreate child node (ObjectTuple new(n)) //false…. No MBR found International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 32 The update process in algorithm 2 takes a new object (newx, newy) as an input. Based on its position, the tree is searched to find the MBR node that overlaps with the object. After locating the node that has the object to be updated according to its oldx, oldy. The information is retrieved from the primary index (the location of the object, current cell of object), then the algorithm determines the update type whatever is it local or not by contrasting the new and old positions. The out-dated object tuple is over-written with the new x and newly if the update is local as well, the old object tuple is deleted (call delete algorithm) and the new object tuple is inserted into the appropriate child node,” update is non-local”. Algorithm 2: update(ObjectTuple new (new)) 1. Search in obj Tree t 2. if EI overlaps obj 3. SearchSubTree(EP, obj) 4. newCell= computenewCell(newx, newy);// new cell is located for the object 5. if newCell = = oldCell // Local update .. in the same cell 6. overwriteObject(new, obj); // obj is overwritten new 7. else // Non-local update detete (obj);//delete the old object tuple insert(new); // insert the new object and update the index In algorithm 3, the delete operation is done as follows: First, search in the tree until finding the child node that contains the object that we want to delete. Second, as child node is implemented in grid coordination. Third, after finding the object the algorithm seeks to shift the last object of the first bucket into the place of the deleted object; all pointers (pointer1, pointer2, and idx) of the last object are modified accordingly in the secondary index. Fourth, if the first bucket was empty, it is erased and the following bucket is the first or the grid cell becomes empty, put a null pointer in the cell. Algorithm 3: delete(ObjectTuple obj) 1. Search obj in Tree t 2. if t is not a leaf //then for each entry E in t do 3. if EI overlaps obj 4. SearchSubTree(EP, obj) 5. firstBucket = * sindex.ldCell; // cell refers to the frist bucket 6. lastObject = firstBckt.entries[firstBckt.nO - 1]; 7. if firstBucket.nO == 0 then // is empty? 8. * sindex.ldCell = firstBucket.next; 9. free(firstBucket); 10. update all pointers of deleted object 3.3 Query Processing The range query is explained and how it works. 3.3.1 Range Query In range query, the resulting cells that overlap with the range query is divided into the completely and the partly covered cells. The objects that are partly covered are needed to be listed in order to know if they are inside the range or not. The input is the query box q (x0, y0, x1, y1) in which (x0, y0) and (x1, y1) are the lower-left and the upper-right corner coordinates respectively. First, the algorithm searches the node of x1 ≥x ≥x0 in dimension x based on the coordinates (x0, y0, x1, y1) of the q in the MBR of the child node; if it has the node of x value. Then, it searches each International Journal of Database Management Systems (IJDMS ) Vol.9, No.6, December 2017 33 node of Max.y1 ≥ y ≥ Min.y0 corresponding to the x-value; if there exists the node of y-value, go to bucket number 1and increment the reader (R) of a bucket before coming into it and decrement it when the bucket has been examined. Finally returns the objects which are covered by the query range in the result set. 4. E XPERIMENTAL R ESULTS In order to check the performance of the proposed technique, we compare it with both traditional R-tree and grid by providing an overview of the performance and showing the average CPU time of individual update, range and I/O visits. 4.1 Index Implementations The index structure is implemented using C++ and compiled with g++ under the Linux. The test environment uses Windows Seven with 64-bit OS, Core (TM) i3-2.10 GHz, 6GB RAM. The indexes are studied under massive datasets; these datasets are generated using an Open-source Moving Object Trace generator (MOTO) that is based on Brinkhoff [17] moving-object generator. Objects move into a network-based roads in five German cities. Table 1 shows the Experimental settings of the generator; the default values are in bold. Table1. The Experimental settings of the generator Dataset Parameters Values Number of objects (× 10  ) 5, 10, 20, 40, 80 Number of Updates (× 10  ) 300 Monitored region ( KM  ) 641 × 864 Velocity(kilometer/hour) 20, 30, 40, 50, 60, 90 Update/queryratio 250:1, …1000:1, …16000:1 Time through updates (s) 10, 20, 40, 80, 160 k nearest neighbor (× 10  ) 0.5,1,2, 4, 8, 16, 32 # network segments 32,750,494 # network nodes 28,933,679 4.2 Comparison of the Indexes A comparative experiment was done to compare the efficiency of the proposed hybrid index and the conventional R-tree and grid under different conditions and parameters. The different index behaviour of the total CPU update time and different number of moving objects are shown in Figure 5. When the number of objects exceeds, the new index outperforms both R-tree and the grid. With the Grid parameters, it still performs updates a little better and performs similar (range) query performance with the tree in figure 6.