Research And Implement Of Top-K Search On Road Network In Big Data Environment

During the past decade, the mobile Internet has experienced a rapid development and made great changes. Mean while, mobile devices has rapidly spread into our lives on which a variety of applications are constantly enriching and changing our daily lives. In all kinds of applications, LBS(Service Location-Based) is one of the very important category. The Top-K query is one of the classic queries mode in LBS, that is, according to the location of the user, finding out a set of K POIs which are nearest to the user. For example, find out the K nearest banks to the school of computer. Lots of researches has been done in the field of Top-K query, but most has two shortcomings. First, most approach sorts results with Euclidean distance rather than road network distance, second, most approach fails to support the queries in level of big data.In order to solve the problem of Top-K query in road network, this paper first analyzes the advantages and disadvantages of the existing algorithms. Second, an index structure of road network based on balanced KD-Tree named DS-Tree is proposed. DS-Tree improves the efficiency of Top-K query by deviding the road network and preprocessing some index structures. This paper proves the correctness of DS-Tree index, and analyzes the space and time efficiency of the index. At the same time, in order to adapt to the demand of the road network in big data, this paper studies the establishment and update method of DS-Tree index in M environment. Finally, the correctness and efficiency of the algorithm are verified by comparing with former approaches in the experiment.