Max-Planck-Institut für Informatik
max planck institut
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
Date, Time and Location
Date:Tuesday, 10 March 2009
Duration:45 Minutes
Building:E1 4
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.

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