HU Berlin |  Institut für Informatik | ROK | Peter K. Ibach

Seminar: Suchmaschinen - Prinzipien und Algorithmen

jeweils Freitag, 11:00 c.t. - 13:00, RUD 25, Raum 4.111 - erster Termin am Freitag, 28. April

[Inhalt] [Ablauf] [Themen] [Terminplan] [Bewertungsmatrix] [Folien] [Literatur] [Links] [Kontakt]

Inhalt

Suchmaschinen sind die Portale des Web und damit Schlüsselfaktoren für die gegenwärtigen technologischen, gesellschaftlichen und ökonomischen Umwälzungen. 

Wir wollen uns Prinzipien und Algorithmen von Suchmaschinen fachübergreifend unter informationstechnischen, ökonomischen und rechtlichen Fragestellungen ansehen. 

Dazu werden Vorträge aus den Themengebieten Internet Charakteristiken, Information Retrieval, Rankingalgorithmen, User Interfaces, Architekturen und E-Commerce gehören, es werden Fallstudien ausgewählter Suchmaschinen näher betrachtet und in einer Bewertungsmatrix verglichen, sowie Geschichte, Rolle und Trends von Suchmaschinen für die Entwicklung von Internet/E-Commerce recherchiert und diskutiert. 

Ziel des Seminars ist es, Funktionsweise und Geschäftsmodelle von Suchmaschinen und ihre Auswirkung auf die Internet Entwicklung zu verstehen, um: 

• Informationen im Internet optimal zu suchen und zu finden
• Suchmaschinen entwickeln, verbessern, integrieren oder auf spezielle Anwendungsgebiete spezialisieren zu können
• Webseiten besser auffindbar zu machen
• Suchmaschinen für Geschäftserfolge einzusetzen

Die Ergebnisse sollen im Web zusammengefasst und präsentiert werden.

Ablauf

Die Teilnehmer sollen jeweils mehrere Kurzvorträge zu den einzelnen Themengebieten mit einer webfähigen schriftlichen Zusammenfassung ausarbeiten. In den wöchentlichen Seminarterminen werden 1 bis 3 zusammenpassende Themen und Fallstudien präsentiert. Zu den Fallstudien sollen jeweils die besonderen Features vorgestellt, klassifiziert und  in eine Bewertungsmatrix eingeordnet werden. Die Kursteilnehmer sollen dazu jeweils stichprobenartige Suchanfragen bzw. Problemstellungen vorbereiten und gemeinsam diskutieren. Darüber hinaus werden einige praktische Themen als Hausaufgaben vergeben und gemeinsam diskutiert.

Themengebiete

[Internet] [Information Retrieval] [Ranking] [User Interfaces] [Architekturen] [E-Commerce] [weitere]

Internet Charakteristiken 

• Qualitativ: Internet Struktur und Protokolle - Wie ist das Internet aufgebaut (Topologische Struktur)? Wie funktioniert die Domain Name Auflösung? Wo sollten die Roboter einer Suchmaschine idealer weise stehen? Welche Zugangstechniken (ISP) gibt es und welche Kosten entstehen? Welche für Suchmaschinen relevanten Abfragemöglichkeiten erlaubt das http-Protokoll (ftp,...) (Änderungsdatum, Inhaltsverzeichnis, File-größen, File-namen, etc.)?
  Literatur: Kyas94
  Vortrag: Burkhard Güther, 02.06.00, Folien
• Quantitative Internet Charakteristiken - Inhalte: Wie viele Pages/Files hat das Internet, bei welchen Wachstumsraten/Änderungsraten, mittlere Dateigrößen (Text, Photos, Videos, MP3 etc.) ? Zugriffe: wie viele Suchanfragen, etc. haben die Suchmaschinen? Wo erhalte ich die jeweils aktuellen Statistiken? Wie werden diese Zahlen bestimmt?
  Links: #Net Statistics
  Vortrag: Christiane Wilke, 02.06.00, Folien

Information Retrieval Modelle

• Indexierung und Retrieval - Textanalyse, Thesauri, natürlichensprachliche Anfragen, Strukturierte Texte, Vektormodell, invertierte Listen, etc.
  Literatur: BaBe99, Ibach94, Meadow92, Leon94
  Vortrag: Bert Schulzki, 19.05.00, Folien
• Quantitative Modelle des IR - Verhältnis von Types (verschiedene Stammformen) zu Token (Anzahl der Wörter), Laufzeitanalyse, Kommunikationsbedarf, Speicherbedarf, etc. 
  Literatur: BaBe99, Ibach94, Meadow92, Leon94

Rankingalgorithmen

• Textbasiertes Ranking - Suchergebnisse werden aufgrund des textuellen Inhaltes sortiert. Welche Algorithmen gibt es hierzu, wie funktionieren Ranking Algorithmen?
  Literatur: Rosenbaum97, BaBe99, Ibach94, Meadow92, Leon94, Babiak97
  Vortrag: Bert Schulzki, 19.05.00, Folien
• "Umgebungsbasiertes" Ranking - Nicht immer ist die Grundlage der Suche rein inhaltsbasiert. Das Ranking einer Site richtet sich vermehrt nach ihrer "Beliebtheit", gemessen z.B. durch die Anzahl der Referenzen (siehe google) oder der Seitenzugriffe. Die Verfügbarkeit einer Site, ihre Aktualität oder ihre Performance mag ebenso eine Rolle spielen. Ein "kapitaldominierter" Ansatz favorisiert Prämien, mit der ein Suchbegriff "gekauft" wird. Wir wollen die verschiedenen Methoden anschauen, untersuchen, wie  man zuverlässig Referenzen und Hits, Verfügbarkeit und Performance bestimmen kann und in wieweit die Qualität der Suchergebnisse damit gesteigert werden kann.
  Vortrag: Aspekte des Referenzen-basierten-Rankings enthält der Fallstudien Vortrag über Google von Kay Schützeler, 14.07.00

User Interfaces

• UI Modelle - die Suchanfrage sollte (bei gegebenem Suchalgorithmus) so formuliert werden, dass die Suchergebnisse auch der Intention des Benutzers entsprechen. Das User Interface bestimmt maßgeblich, in wieweit dies intuitiv gelingt. Welche Generellen Konzepte gibt es und was leisten sie.
  Literatur: BaBe99 
• Relevance Feedback - Suchergebnisse treffen selten sofort die Intention der Suchanfrage. Doch kann man durch geschickte Verbesserung der Anfrage anhand der ersten Ergebnisse zu beeindruckender Trefferqualität kommen (Interactive query refinement). Wir schauen uns wissenschaftliche Beiträge dazu an und vergleichen damit erfolgreiche Beispiele aus der Praxis: Simpli.com, Ask Jeeves! und auch ditto.
  Literatur: BaBe99
• Personalisierung - Onlineshops begrüßen die Kunden mit Kaufempfehlungen. Suchmaschinen kennen die Vorlieben ihrer User, stellen individuelle Surf-Tips bereit und lernen von vergangenen Suchanfragen. Wie lässt sich das umsetzen und wie nützlich ist das wirklich?
• Suchagenten - Agenten erledigen die Suche als Vertreter und schließlich beraten "virtual Consultants", "Avatare" bzw. "Chatterbots" natürlichsprachlich bei der Navigation durchs Netz. Was ist davon zu halten, was ist machbar, welche Verfahren gibt es und was ist wirklich nützlich?
  Vortrag: Julia Ahlers, 16.06.00
• Mobile Endgeräte - welche User Interfaces sind für mobile Endgeräte geeignet (siehe #Channels). 

Architekturen

• Parallele Architekturen - etwa 1 Mia. Seiten gibt es im Netz mit einem Wachstum von über 100% im Jahr. Der Trend zur Suche nach Multimedia-Inhalten vervielfältigt das Datenvolumen dabei. Nur durch parallel arbeitende Roboter/Agenten können Suchmaschinen diese Datenflut bewältigen und gleichzeitig Millionen Suchanfragen verarbeiten. Wir diskutieren Architekturen und Kommunikationsstrukturen der Roboter/Agenten, bestimmen Durchsatz, Bandbreitenanforderungen sowie Möglichkeiten zur Parallelverarbeitung und Effizienzsteigerung bei der Indexierung und beim Retrieval. 
  Stichwörter: I/O Parallelität, Disk Arrays, Datenallokation und Lastbalancierung, Datenparallelität vs. Kontrollparallelität, Auftragsparallelität vs. Zugriffsparallelität, Durchsatz vs. Antwortzeit, Zentrale vs. Dezentrale Architekturen, Parallelrechner, Cluster Computing
  Literatur: BaBe99, Ibach94
  Links: Klassifikation von Parallelrechnern: Folien von Andreas Polze, Seminar über Cluster Computing von Peter Löhr (FU), Alexander Reinefeld (HU & ZIB) und Raul Rojas (FU)
• Responsive Web - Hat man die gewünschte Site im Index der Suchmaschine gefunden, stehen u.U. verschiedene Mirrors oder Proxies zur Auswahl oder ein interner Cache um die gesuchten Inhalt abzurufen. Welche Möglichkeiten gibt es hier, den Zugriff über Suchmaschinen leistungsfähiger zu machen und welche Verfahren wenden die großen Portale und Suchmaschinen an? Wie kann man Zuverlässigkeit und "günstges" Zeitverhalten vom Server über das Kommunikationsmedium bis zum Client erreichen, welche Angriffsgefahren birgt das Internet und welche Verfahren gibt es, dem entgegenzutreten?
  Stichwörter: Zuverlässigkeit, Verfügbarkeit, Sicherheit, Fehlertolerante Systemarchitekturen, Fehlerklassen, Echtzeit, (End-to-End) Quality of Service (QoS), Echtzeit Scheduling/Lastbalancierung, Prioritäten, Deadlines, Überlastschutz, Stresstests, Zeitvorhersage, Responsivitätsmaße, Mirrors, Proxies, Cache, Computerviren, denial of service attacs, spamming & filtering, kryptographische Verfahren, Virtual Private Networks VPN, Firewalls, Intelligente Netze, policy based networks
  Links: Akamai - responsive internet content delivery

• Integration - Nicht alle Informationsquellen sind über http als html-files zugreifbar. Daneben gibt es ftp und einige weitere Protokolle. Immer häufiger aber wird Content in Datenbanken abgelegt um daraus dynamisch html-files zu generieren. Lassen sich unterschiedliche Übertragungsprotokolle und Datenstrukturen, insbesondere dynamische Inhalte intergrieren, indexieren, cachen, referenzieren und wiederfinden? 
  Links: Informations Integration Seminar WS 99-00, Datenboutique
• Meta-Suchmaschinen - Wie funktionieren Meta-Suchmaschinen (quantitative Einschränkungen,  Integration, Architekturen, etc.)?
• Multimedia / Spezialisten - Wie funktioniert die spezialisierte Suche nach Personen, Dokumenten, Multimedia - Besonderheiten bei der Suche nach Bildern (z.B. ditto, AltaVista), Videos, Musik, etc.
  Links: Image Search Engines
  Vortrag: Natalie Rosenke, 30.06.00
• Channels / Mobility - E-Commerce wandelt sich zum M-Business. Schon in zwei Jahren soll die Zahl der Mobile User im Internet die Zahl der Festnetz User überflügeln (600 Mio gegenüber 400 Mio weltweit). Ebenso kommen Settop Boxen und andere "Channels" hinzu. U.A. werden Local Services, die Suche nach ortsabhängigen Informationen, z.B. nach dem nächsten Nightclub mit House Music, die "Killerapplikationen" sein. Wie funktioniert die Technik (WAP, UMTS, Ortung) und welche User Interfaces sind hier sinnvoll?
  Vortrag: Ie Piu hat im e-lab Seminar einen damit verwandten Vortrag über WAP-Technologie gehalten, Folien

E-Commerce

• Abrechnungsverfahren - Suchmaschinen verdienen durch Werbung, aber zunehmend an Vermittlung, Provision, "Satellitengeschäften", Übernahmen und Partnerschaften. Wer verdient wie und wie viel und wie lassen sich Provisionsmodelle technisch realisieren?
  Literatur: KöBe98
  Vortrag: E-Commerce / Abrechnungsverfahren, Diemo Urbig, mailto, 23.06.00,  index, Folien
• Rechtliche Rahmenbedingungen - Suchmaschinen leben vom Inhalt anderer. Darf man einfach so Links setzen, Suchwörter kaufen, Textpassagen kopieren, cachen oder speichern, eine Datenbank automatisiert abfragen, Thumbnails oder Trailer generieren oder das Verhalten von Kunden protokollieren?
  Literatur: Strömer99, Koch99
  Vortrag: Matthias Horbank, 23.06.00, Folien

Geschichte, Rolle und Trends

• Historie von Suchmaschinen - Historische Entwicklung von Suchmaschinen. Die Evolution und Funktionsweise von archie, Veronica, Gopher, WAIS, Mosaic, etc.
  Literatur: Gilster94, Kyas94, Babiak97 Links: z.B. Yahoo Linkliste zur Internet Geschichte
  Vortrag: Kay Schützler, 19.05.00, Folien
• Suchmaschinen als Portale -  Technologie & Content, email, Kalender, Bookmark und Office Anwendungen, Einflüsse, Rolle, Trends, Analystenmeinungen, etc.
  Links: z.B. Trends zur Nutzung des Internet

Hausaufgaben/Sonstige

• Fallstudien - wie funktionieren ausgewählte Suchmaschinen? Einordnung in Bewertungsmatrix.
• Website Promotion - Wie mache ich meine Website bekannt?
  Aufteilung: 1. Desktop Tools, 2. Promotion Roboter, 3. Manuelle Eintragung, 4. Analyse Tools
  Artikel dazu: c't 23/99 S.180
  Links:
  • WebPosition Gold Search Engine and Web promotion Software
  • Homepageanmeldung mit metacrawler.de - in 3 Minuten ist die Homepage bei verschiedenen Suchmaschinen eingetragen zum Indexieren. Ähnliches bietet auch JimTools.com.
  • Check4New - Software zum automatischen erkennen von Aktualisierungen im Web.
  • 1&1 BannerCommunity - Kostenlose Bannerwerbung im gegenseitigen Austausch.

• mySeachEngine
  1. Welche Möglichkeiten bieten Suchmaschinen zur Personalisierung an (z.B. myYahoo oder
     meOme-Vision - Personalisieren der eigenen Portalseite)?
  2. Wie kriege ich eine Suchmaschine auf meine eigene Website?
  3. Desktop Tools - welche Tools können mich sinnvoll bei Recherchen unterstützen?
  4. Server Tools - Software Komponenten zum Aufbau einer Suchmaschine.
• Tips und Tricks aus der Praxis - wie bringe ich aktuelle Suchmaschinen dazu, das zu finden was ich wirklich suche?
  Literatur: Babiak97
• Future Research Trends - was fehlt den Suchmaschinen noch? Welche zukünftigen Forschungsschwerpunkte gibt es?
  • Jeder schreibt 3 Wünsche auf: "Was mich schon immer an Suchmaschinen gestört hat und ich mir als zukünftiges Feature wünschen würde" und überlegt gleichzeitig, ob und wie man diesen Wunsch erreichen kann.

Terminplan