Different kinds of uses of data put directly in straightforward applications like payroll systems, inventory management, database applications, banking system and shipping systems. However research in database systems growing rapidly in traditional and non-traditional applications that have not foreseen in past decades. Further, the rapid growth of spatial systems increasing pervasively high in Geo-sciences and Spatial Database Systems (SDS) as voluminous data generating by non-traditional applications[1]. The growth is increasing vigorously in demand-driven applications in computer vision, Augmented and virtual reality, robotics, and Geographic Information Systems(GIS). Spatial data is more in quantity and high complex in relations and structures. To maintain large voluminous data, storage plays main role to access the required information. Indexing of data is a proper way to get optimization of query performance by reducing the number of disk accesses.
Indexing of spacial information could be a huge challenge in current days with huge and complicated information. compartmentalization could be a mechanism to urge question performance in optimized manner in an exceedingly information by minimizing the quantity of memory access. Indexing takes input of search key and returns cluster of matching records as nearer output. Spatio temporal classification is applied on all types of information like multi-dimensional information systems, transmission systems, massive flight movement information and complicated information systems. Transmission information systems embrace text, audio, images, and videos that need a lot of information to store and a decent classification is needed to access.
Many researchers has enforced and projected several improvement techniques in spacial calculations in numerous situations. A multi layer grid model consisting of latitude and longitude may be a Geo-SOT Grid model. These latitude and longitude points area unit changing into binary kind to cipher into specific string format. Earth subdivision model and cryptography technique, 1st one stipulates space divided into multi-scale subdivision small units with equal shapes and regular sizes later technique assigns distinctive identification string format code for every unit. Geo-spatial grid model is wide studied in domain, effective organization and applications of huge multi supply spatial information. The hierarchical spatial organization stores the data that divides area into grid shapes and obtains the info by exploitation of area filling curves, like Z-order, Hilbert curves and Piano curves. The Geo-hash offers a preciseness price as a prefix and step by step removes the top of the stream as a suffix to scale back the dimensions of the particular location. It shares a extended prefix for nearer Geo-hashes that square measure spatially nearer that they're along at an area.
Spatial indexing is the connection between logic records of spatial data to correspondence physical records among data that leads to efficient spatial data access. The basic method of indexing is dividing the space area into regions, boundaries and search areas to identify the given locations by certain order. Spatial indexing Common methods are Quad-Tree, Oct-Tree, k-d Tree, Grid index, QR Tree and their variants. Different indexing methods have advantages and disadvantages depending on their applications. The efficiency of query retrieval is relatively low from one index to another index.
A hierarchical data structure of Quad tree contains spatial data in two-dimensional coordinates. A quad tree with root, every internal node contains four children (NE,NW,SW,SE) and every node of Quad tree represents a rectangular area[2]. These are knowledge structure which encodes two dimensional space into required flexible cells. Single indexing structures can not overcome the problems occurs in organizing the large data. Many researchers forward to combine the idea of indexing in hybrid model structures. QR tree is the main indexing structure which follows quad area subdivision method and R tree region of objects which falls in Minimum Bounding Rectangle(MBR). Quad tree divides the whole index space into sub index spaces in multilevel indexing.
1.1 Quad Tree
Quad trees are the two dimensional object structures of space partition recursively subdividing the space into four quadrants. Each quadrant is equal in size and divided depends on the objects in each quadrant. Quad trees are mostly used in image compression, the deeper you traverse in the tree the clarity you will get the image.
Figure 1 shows the Quad tree representation of an area divided into different levels. If number of objects present in a specified region are more in number it can be subdivided into quadrants and added as a leaf nodes to the specific quadrant region. Quad tree is recursively decompose into sub quadrants of equal sizes to index the space data. Decomposition continues until each sub quadrant is fully occupied with image or no image. Each sub quadrant is referred as a leaf node. The non leaf nodes are relatively covering the image then they are further divided into sub quadrant. All these sub quadrant are sorted by space filling curves like Z order, Hilbert and piano in an order to index the data.
1.2 R Tree
R Tree is the basic index structure to store and access the spatial data. Each non leaf node is bounded with Minimum Bounding Box (MBB). Every MBB considered as internal node and stored as a sub tree in R Tree. Each MBB size is depending on the number of objects present in box and size of the objects in MBB. The R Tree average height is based on the tree index structure in the form of O(logN). B+ tree expansion of multidimensional space objects is R Tree. The main disadvantage of R Tree is overlapping of nodes and Minimum Bounding Rectangle (MBR). To overcome overlapping problem R Tree and maximize the searching capability in tree structure R* tree has been identified[3]. The overflow nodes are reinserted into R* tree and performance is improved better than R Tree. Still R* tree does not give a proper solution to overlapping between nodes. Individual structures will not have better performance to query operations. A hybrid structures of Quad and R Tree improves the performance based on certain area of quadrant and objects inserted to the nodes in the tree.
1.3 Hybrid indexed structure QR Tree
The hybrid data structure by combining of Quad tree and R Tree eliminates the problems in individual structures which occurred like overlapping and overflow of nodes. QR tree partitioned the whole space into small sub spaces of 2k (k is the number of dimensions of a given space). Each node in Quad tree is a node of R Tree. Every node is a internal or leaf node of R Tree in a space[4]. The following structures shows the space partition and QR structure of given objects in a space.
Figure 2(a) and 2(b) shows the QR Tree structure in space partition and R tree notation. Many indexing structures were used QR representation in two dimensional space. For multidimensional data can be represented by Oct trees. Many variations of QR trees came into literature as hybrid index structure eliminates the problems which occurred in alone structures. Quad and R Tree structures generates hybrid organization of data indexing. Hybrid structures which includes multi-dimensional databases consisting many indexing methods like QR-Tree, QR+-Tree, QR*-Tree[5].
This paper provides description of section 1. introduction to QR structure, 2. Related work for the new algorithm, 3. STAQR tree data structure, insertion, deletion, and search 4. Experiment results analysis, 5. Conclusion and future work.