ACM Distinguished Speakers Program:  talks by and with technology leaders and innovators

Distributed All k Nearest Neighbor Queries

Speakers: Demetrios Zeinalipour-Yazti
Topic(s): Computers and Society,Data Communication,Distributed Systems and Algorithms


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. Most traditional techniques for computing AkNN queries are centralized, lacking both scalability and efficiency. Only recently, distributed techniques for shared-nothing cloud infrastructures have been proposed to achieve scalability for large datasets. These batch-oriented algorithms are sub-optimal due to inefficient data space partitioning and data replication among processing units. In this talk I will present Spitfire, a distributed algorithm that provides a scalable and high performance AkNN processing framework. The proposed algorithm deploys a fast load-balanced partitioning scheme along with an efficient replication-set selection algorithm, to provide fast main-memory computations of the exact AkNN results in a batch-oriented manner. I will also overview Rayzit, an experimental and open-source AkNN service we established and operated to evaluate our proposed ideas. The talk will conclude with findings on how AkNN graphs affect the social interactions of users.


About this Lecture

Number of Slides: 40
Duration: 60 minutes
Languages Available: English
Last Updated: 03-09-2017
Request this Lecture

To request this particular lecture, please complete this online form.
Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.
Featured Speaker

Keith Cheverst
Lancaster University

Get Involved!
Help improve the DSP by nominating a speaker or providing feedback to ACM.