Distributed All k Nearest Neighbor QueriesSpeaker: Demetrios Zeinalipour-Yazti – Nicosia, Cyprus
Topic(s): Computational Theory, Algorithms and Mathematics
AbstractA 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 LectureNumber of Slides: 40
Duration: 60 minutes
Languages Available: English
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.