Research On Index Algorithms Based On A* Tree In Cloud Computing Environment

With the fast development of computer technology, the volume of data increases explosively with exponential speed. Traditional database has encountered a serious bottleneck in scalability. As a new computing mode, cloud computing emerges at the right moment, and it has been well studied and widely used in the academia and industry. In order to improve the query performance of data in cloud computing environment and meet the need of users for various queries, the paper mainly studies the data indexing technology and its query processing algorithms.Firstly, most index structures can only support a simple query in the cloud computing environment, and can not support range queries or more complex queries efficiently. So this paper presents A* tree, a index structure based on tree structure of the cloud computing environment. A* tree is the combination of R* tree and dynamic bloom filter. It can store and query the big dataset; at the same time, it will also be able to quickly handle point queries, range queries and nearest neighbor queries.Secondly, the paper handles spatial query based on the A* tree, such as point query, range query, nearest neighbor query. And the paper also proposes three kinds of query algorithms. According to A* tree, the paper proposes a algorithm of point querying based on A* tree, using technique of dynamic bloom filter; the paper proposes a algorithm of range querying based on A* tree, using idea of the bounding box by overlap operation between each bounding box and the query area; the paper proposes a algorithm of nearest neighbor querying based on A* tree, using idea of a priority queue and value of the minimum distance.Finally, by experiments and analysis of the algorithms of point querying based on A* tree, range querying based on A* tree and nearest neighbor querying based on A* tree, the correctness and validity of algorithms are proved. At the same time, experiments show that A* tree is an effective cloud distributed data structure of multidimensional data.