Distributed in-memory processing of All K Nearest Neighbor queries
Zeinalipour-Yazdi, Constantinos D.
Lee, W. -C
Pitoura, Evaggelia 1967-
PublisherInstitute of Electrical and Electronics Engineers Inc.
Source2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
32nd IEEE International Conference on Data Engineering, ICDE 2016
Google Scholar check
MetadataShow full item record
A wide spectrum of Internet-scale mobile applications, ranging from social networking, gaming and entertainment to emergency response and crisis management, all require efficient and scalable All k Nearest Neighbor (AkNN) computations over millions of moving objects every few seconds to be operational. In this paper we present Spitfire, a distributed algorithm that provides a scalable and high-performance AkNN processing framework to our award-winning geo-social network named Rayzit. The proposed algorithm deploys a fast load-balanced partitioning along with an efficient replication-set selection, to provide fast main-memory computations of the exact AkNN results in a batch-oriented manner. We evaluate, both analytically and experimentally, how the pruning efficiency of the Spitfire algorithm plays a pivotal role in reducing communication and response time up to an order of magnitude, compared to three state-of-the-art distributed AkNN algorithms executed in distributed main-memory. © 2016 IEEE.