Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Distributed Similarity Search in High Dimensions
Speaker:Sebastian Michel
coming from:École Polytechnique Fédérale de Lausanne
Speakers Bio:
Event Type:Talk
Visibility:D1, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Language:English
Date, Time and Location
Date:Tuesday, 10 March 2009
Time:14:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
In this talk we will have a look at similarity search techniques for high-dimensional data.

We present a novel approach for distributed K-Nearest Neighbor (KNN) search and range query processing. Our approach is based on Locality Sensitive Hashing (LSH) which has proven very efficient in answering KNN queries in centralized settings. We consider mappings from the multi-dimensional LSH bucket space to the linearly ordered set of nodes in a network that jointly maintain the indexed data and derive requirements to achieve high quality search results and limit the number of network accesses.

We put forward two such mappings that come with these salient properties: being locality preserving so that buckets likely to hold similar data are stored on the same or neighboring peers and having a predictable output distribution to ensure fair load balancing.

We show how to leverage the linearly aligned data for efficient KNN search and how to efficiently process range queries which is, to the best of our knowledge, not possible in existing LSH schemes.

We will conclude the talk by reporting on a comprehensive performance evaluation using real world data that our approach brings major performance and accuracy gains compared to state-of-the-art.

Contact
Name(s):Conny Liegl
Phone:302-70150
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Conny Liegl, 03/09/2009 01:46 PM -- Created document.