An efficient nearest neighbor algorithm for P2P settings

TitleAn efficient nearest neighbor algorithm for P2P settings
Publication TypeConference Papers
Year of Publication2005
AuthorsTanin E, Nayar D, Samet H
Conference NameProceedings of the 2005 national conference on Digital government research
Date Published2005///
PublisherDigital Government Society of North America
Keywordsgeographic information systems, nearest neighbor query, peer-to-peer networks, quadtree, spatial data

New Peer-to-Peer (P2P) applications like P2P job-employee seeker networks and P2P virtual cities, for application domains such as collaborative urban planning and forming virtual communities, are about to emerge. An important component in these applications is spatial data, i.e., data with locational components. Many requests initiated on spatial data involve finding the spatial objects that are nearest to a query location. In this paper, we propose an efficient algorithm that finds the spatial objects that are nearest to a given query location on a P2P network in the order of their minimum distance to the query point. The proposed algorithm makes use of a distributed spatial index that does not rely on the use of a central server. The algorithm is designed to be more efficient by utilizing the parallel nature of the P2P network. A demonstration of the proposed algorithm was implemented as a prototype P2P application that finds events and places of interest in a city.