Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 22, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Fabian Kuhn
In today's computing environments, data is no longer stored at one central server. Often, data is distributed across many heterogeneous locations that are connected through a network. Nevertheless, there need to be efficient methods to query large data sets. In the talk, I will consider the problem of distributed k-selection where, given a connected graph of diameter D consisting of n nodes in which every node holds an element, the goal is to determine the kth smallest of these elements. I will present a simple distributed randomized algorithm with time complexity O(D*log_D(n)) and I will prove a lower bound of Omega(D*log_D(n)) implying that the presented algorithm is asymptotically optimal.
Joint work with Thomas Locher and Roger Wattenhofer.
Automatic MiSe System Software Version 1.4803M | admin login