Article Preview
Top1. Introduction
Recently, cloud computing services are in demand because they provide inexpensive and powerful resources to the users (Armbrust et al., 2010). For managing cloud database, cloud storage services plays a very important role. For efficient accessing of these data sets indexing plays a very crucial role. Current systems based on Distributed hash table works well with key-value pairs to give best performance for exact matching through point queries. It does not support or provide good performance for multidimensional and complex queries.
Many advanced indexing strategies such as R tree, Quad Tree, Bitmap, Octree has been developed with many advantages and limitations for efficiently accessing multidimensional queries. Octree is considered suitable for multi-attribute data and multidimensional queries. 2014, a two level SNB-Index based on SkipNet and B+Tree is proposed (Zhou et al., 2014) which provides high availability and scalability and support range queries as well as similarity queries but the proposed model was efficient for single attribute queries not for multi-attribute queries. In (2015, 2016) a decentralized, scalable double layer indexing structure using probabilistic Skiplist and Octree has been proposed (Dong et al., 2015) (He et al., 2016), skip-list is used to speed up the searching process and provides hierarchical querying and support multidimensional query using Octree indexing technique. A Skiplist (Pugh, 1990) is an in-memory data structure which can be used in place of balanced trees. Instead of forced balancing algorithm randomized algorithm is used for balancing which gives better results. With the help of probabilistic pattern, insertion and deletion operations are faster as compared to balanced trees. While processing any query not all elements of the data are useful hence Skiplist provides a way to skip many data element as it is based on hierarchical ordered linked list. In Skiplist traversing is done only from the head node whereas SkipNet (Harvey et al., 2003) provides a facility to traverse from any node. In Skiplist, each data node maintains variable number of pointer and different amount of traversal traffic per data record. But in case of SkipNet each node maintains 2LogN pointers where N refers to the number of nodes in the form of routing table. Since these nodes are used to pass message traffic in between nodes with the help of these routing table.
SkipNet (Harvey et al., 2003) is distributed generalization of Skiplist with two advantages i.e. meticulous data placement and data guaranteed routing locality. SkipNet works based on these two locality properties content locality and path locality. Content locality refers to dynamically or distributed placement of data on the overlay nodes within the range of organization and path locality means if a message is passed between two overlay networks it should be routed within the same organization. SkipNet is double ring linked list so while traversing pointer can move in left or in right direction. Use of SkipNet instead of Skiplist provides various advantages like data retrieval, security, improved availability, performance, manageability.
Other overlay networks (Zou et al., 2013) like CAN, CHORD does not provide the control over data i.e. where data is stored and also, they do not provide any guarantee that message routed within same organization remains in that organization. Due to these advantages SkipNet is selected for implementing global indexing.
In this paper, a novel indexing technique based on SkipNet and Octree has been proposed. Key contributions of this study are as follows:
- 1.
A novel indexing technique based on SkipNet and compressed Octree has been proposed. To the best of our knowledge ours is the first work to construct secondary indexing using SkipNet and Octree;
- 2.
Range query algorithms have been proposed;
- 3.
Nearest neighbor query algorithms have been proposed.