Nearest neighbour query processing in mobile P2P networks

The mature growth of mobile technologies in both hardware and software has paved the way for applying Peer-to-Peer (P2P) to location-aware applications in general and to nearest neighbour query processing in particular. Indeed, mobile devices powered by energy-efficient and high-performance microprocessors now allow people to share messages, sounds and pictures. In addition, wireless communication technologies have been developing dramatically, which enables mobile devices from anywhere to communicate at any time without requiring a wireless access point. P2P query processing not only harnesses the power of collaboration between peers, but also overcomes the drawbacks of centralised systems, such as bottleneck issues and low fault-tolerant problems. Therefore, making use of P2P query processing is a natural and essential move in spatial database management. The study in this thesis revolves around the central question: "Can the P2P approach solve Spatial Nearest Neighbour Queries in Mobile Environments?". In order to address the question, a pure mobile P2P query processing system is proposed to answer spatial queries. Although the proposed system is able to provide services to a wide range of spatial query types, the focus of the thesis presents as a case study, one of the most common types of spatial queries: Nearest Neighbours in a two-dimension Euclidean space with mobile peers and static objects of interest. In particular, this thesis introduces the P2P query processing system to tackle k Nearest Neighbours (kNNs), Reverse Nearest Neighbours (RNNs) and Group Nearest Neighbours (GkNNs). This system eliminates the role of a base station and focuses on the power of peer collaboration. Rather than queries are sent to all peers, a time-out mechanism, result validation algorithms and peer pruning algorithms are proposed to filter unnecessary peer communication. As a result, the proposed system can decrease query processing time and energy consumption while maintaining a high rate of accuracy. The experimental study, which uses both real and synthetic data sets, shows the practical feasibility of the P2P approach in solving Nearest Neighbour queries for mobile networks with the high density of moving objects