Andrei Broder

Andrei Zary Broder ist ein israelischer Informatiker, der an Suchmaschinen und den dafür benötigten Algorithmen arbeitet. Er ist ein Google Distinguished Scientist.

Ausbildung und Karriere

Broder erwarb am Technion seinen Bachelor-Abschluss mit summa cum laude und wurde 1985 bei Donald Knuth an der Stanford University promoviert.

Er arbeitete bei IBM Research, wo er erst Distinguished Engineer und später CTO des „Institute for Search and Text Analysis“ wurde. Anschließend wechselte er zu AltaVista, wo er Vizepräsident für Forschung war und die Einführung von Captchas vorangetrieben hat, und danach (2005) als Research Fellow und Vizepräsident für Computational Advertising zu Yahoo, bevor er 2012 zu Google wechselte. Dort ist er Distinguished Scientist und befasste sich unter anderem mit großskaliger Personalisierung von Informationen.

Forschung

Er veröffentlichte über 100 Arbeiten und hält 39 US Patente (2013).

Zur Lösung des Problems, Webseiten mit ähnlichen Inhalten zu identifizieren (und allgemein eng verwandte Dokumente), entwickelte er 1997/98 eine neue Hashing-Technik (Locality Sensitive Hashing, LSH) über Minhash-Funktionen ein.^[1]^[2] Diese wurde von Piotr Indyk und Rajeev Motwani mit weiteren Hash-Funktionen erweitert, wobei sie dafür Nearest-Neighbor-Suchalgorithmen mit sub-linearer Antwortzeit fanden. Moses S. Charikar fand eine weitere Gruppe sehr effizienter LSH-Funktionen (Simhash-Funktionen). Die effizienten und skalierbaren Methoden verbreiteten sich in vielen Anwendung der Informatik, in denen große Datenmengen verarbeitet werden (Computer-Sehen, Data Mining, Datenbanken, Maschinenlernen, Signalverarbeitung). Typische Anwendungen sind das Finden von Duplikaten von Dokumenten und Webseiten in großen Datenmengen, das Finden ähnlicher Gensequenzen in Gendatenbanken, Bildsuche (z. B. VisualRank von Google), Erstellen von Fingerabdrücken in Audio und Video.^[3]

2020 erhielt er den Preis erneut, zusammen mit mehreren anderen Preisträgern (Yossi Azar, Anna Karlin, Michael Mitzenmacher, Eli Upfal), für eine neue Strategie bei dem Balanced Allocation Problem, auch Balls-into-bins Problem genannt, in dem n Bälle mehr oder minder zufällig auf m Kästen (bins) verteilt werden. Eine Strategie (power of two) wählt zwei Kästen zufällig aus und legt den Ball in den Kasten mit der kleineren Anzahl von Bällen. Statt des maximalen Erwartungswerts (bei m=n) von ${\frac {\log {\log n}}{\log n}}$ bei rein zufälliger Verteilung reduziert sich bei Anwendung dieser Strategie das Maximum auf $\log {\log n}$ und damit exponentiell. Das Problem hat viele Anwendungen in der Informatik, zum Beispiel gleichmäßigere Auslastungen (Balancierung) bei gemeinsamen Speicherplätzen, Verteilung von Informationspaketen auf parallele Routen in Web-Servern und Netzwerken sowie in Hash-Tabellen. Broder war Ko-Autor der ursprünglichen Arbeit zur power-of-two Strategie.^[4]

Um 2000 entwickelte er mit anderen ein graphisches Web-Modell, das Flaschenhälse des Informationsflusses zeigte.^[5]

Ehrungen und Mitgliedschaften

2007 wurde er Fellow der Association for Computing Machinery (ACM). Er ist IEEE Fellow und Mitglied der National Academy of Engineering.

2012 erhielt er mit Moses S. Charikar und Piotr Indyk den Paris-Kanellakis-Preis für LSH und 2020 für seine Beiträge zum Balanced Allocation Problem.

Weblinks

Paris Kannelakis Preis
Biografie anlässlich eines Vortrags am Technion (Memento vom 29. Oktober 2013 im Internet Archive)

Einzelnachweise

↑ Broder On the resemblance and containment of documents, Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italien, 11.–13. Juni, 1997, IEEE, S. 21–29
↑ A. Z. Broder, M. Charikar, A. M. Frieze, M. Mitzenmacher Min-wise independent permutations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, S. 327–336
↑ Shikhar Gupta, Locality Sensitive Hashing, 29. Juni 2018
↑ Azar, Broder, Karlin, Upfal, Balanced Allocations, SIAM J. on Computing, Band 29, 1999, S. 180–200, vorläufige Version erschienen in Proc. STOC 94, ACM 1994
↑ Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener: Graph structure in the web, Proceedings of the 9th World Wide Web Conference, Band 33, 2000, S. 309–320.

Personendaten
NAME	Broder, Andrei
ALTERNATIVNAMEN	Broder, Andrei Zary (vollständiger Name)
KURZBESCHREIBUNG	israelischer Informatiker
GEBURTSDATUM	20. Jahrhundert

[1] Broder On the resemblance and containment of documents, Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italien, 11.–13. Juni, 1997, IEEE, S. 21–29

[2] A. Z. Broder, M. Charikar, A. M. Frieze, M. Mitzenmacher Min-wise independent permutations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, S. 327–336

[3] Shikhar Gupta, Locality Sensitive Hashing, 29. Juni 2018

[4] Azar, Broder, Karlin, Upfal, Balanced Allocations, SIAM J. on Computing, Band 29, 1999, S. 180–200, vorläufige Version erschienen in Proc. STOC 94, ACM 1994

[5] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener: Graph structure in the web, Proceedings of the 9th World Wide Web Conference, Band 33, 2000, S. 309–320.

[1]

[2]

[3]

[4]

[5]