标题：Distributed Grid-Based K Nearest Neighbour Query Processing Over Moving Objects
作者：Yang, Min; Liu, Yang; Yu, Ziqiang
作者机构：[Yang, Min; Liu, Yang; Yu, Ziqiang] Shandong Univ, Sch Comp Sci & Technol, Jinan 250100, Peoples R China.
会议名称：16th International Conference on Web-Age Information Management (WAIM)
会议日期：JUN 08-10, 2015
来源：WEB-AGE INFORMATION MANAGEMENT (WAIM 2015)
摘要：K-nearest neighbour (k-NN) queries over moving objects is a classic problem with applications to a wide spectrum of location-based services. Abundant algorithms exist for solving this problem in a centralized setting using a single server, but many of them become inapplicable when distributed processing is called for tackling the increasingly large scale of data. To address this challenge, we propose a distributed grid-based solution to k-NN query processing over moving objects. First, we design a new grid-based index called Block Grid Index (BGI), which indexes moving objects using a two-layer structure and can be easily constructed and maintained in a distributed setting. We then propose a distributed k-NN algorithm based on BGI, called DBGKNN. We implement BGI and DBGKNN in the commonly used master-worker mode, and the efficiency of our solution is verified by extensive experiments with millions of nodes.