Skalierbares, inhaltsbasiertes Retrieval von Text- und Multimedia-Dokumenten in Peer-to-Peer Netzwerken

• Applicant: Professor Dr. Andreas Henrich
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2006 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 22485039

• Final Report Year: 2010

Final Report Abstract

Peer-to-Peer (P2P) Systeme bieten eine attraktive Möglichkeit zur Verwaltung großer Datenbestände. Auf Basis eines entsprechenden Protokolls arbeiten gleichberechtigte Peers zusammen und ermöglichen ohne zentralen Server die verteilte Verwaltung großer Datenbestände. Eine wichtige Aufgabe ist die Suche in P2P-Netzen. Diese Aufgabe ist für die schlüsselbasierte exakte Suche zufriedenstellend gelöst. Die Ähnlichkeits- oder Best- Match-Suche in P2P-Netzen ist dagegen ein aktuelles Forschungsgebiet. Die Herausforderung liegt darin, Algorithmen zu finden, die bei geringem Kommunikationsaufwand möglichst große Vorteile aus der verteilt verfügbaren Speicher- und Rechenkapazität ziehen. In diesem Projekt haben wir zusammenfassungsbasierte Ansätze zum P2P Information Retrieval weiterentwickelt und mit konkurrierenden Ansätzen verglichen. Dabei erwiesen sich unter anderem hochfeine, komprimierte Clusterhistogramme und adaptive Index- Swapping-Ansätze als wesentliche Verbesserungen bisheriger Ansätze. Hochfeine Clusterhistogramme stellen Ressourcenbeschreibungen dar, die jedem Referenzpunkt/Zentroid aus einer Menge vorgegebener Zentroide eine gewisse Anzahl an Indexdaten zuordnen, die dem jeweiligen Referenzpunkt am nächsten liegen. Durch Verwendung einer Vielzahl an Referenzpunkten entstehen dünn besetzte Histogramme, die sich durch den Einsatz von Kompressionsverfahren auf kompakte Weise repräsentieren lassen. Außerdem entsteht auf diese Weise eine feingranulare Partitionierung des Feature-Raums, sodass ein effizientes Retrieval ermöglicht wird. Bei Index-Swapping-Ansätzen spezialisieren sich die Peers nach dem Eintritt in das Netzwerk, der gemäß dem Protokoll des zusammenfassungsbasierten Netzes stattfindet, auf einen bestimmten Bereich der Indexdaten. Dies führt zu trennschärferen Ressourcenbeschreibungen und ermöglicht somit eine effiziente Anfragebearbeitung. Wir haben außerdem Arbeiten durchgeführt, die darauf abzielen interaktive Retrievalmechanismen in verteilten Szenarien zu unterstützen. Auch hierbei lassen sich hochfeine Clusterhistogramme und die Zentroide nutzen, die zur Erstellung der Clusterhistogramme benötigt werden. In diesem Zusammenhang haben wir damit begonnen die facettierte inhaltsbasierte Bildsuche auf den P2P-Kontext zu übertragen. Metadaten stellen ein wichtiges Kriterium beim Bildretrieval dar. Wir haben verschiedene Techniken analysiert, um den geographischen Fußabdruck eines Peers zu beschreiben. Auch hierbei bieten binäre, hochfeine Clusterhistogramme eine geeignete Möglichkeit zur Ressourcenauswahl und damit zu einem effizienten Retrieval. In zukünftigen Arbeiten sollen Source-Selection-Strategien auf Basis hochfeiner Clusterhistogramme weiter optimiert und deren Anwendbarkeit in verschiedenen Kontexten geprüft werden. Hierbei sollen drei grundlegende Arbeitsrichtungen abgedeckt werden: Optimierung bzgl. Skalierbarkeit und Retrieval-Leistung; Zusammenfassungen für verschiedene Feature-Typen; Einsatz in anderen Anwendungsszenarien. Durch die Erweiterung auf andere Feature-Typen sollen den Anwendern umfassende Suchmöglichkeiten bereitgestellt werden. Ziel ist es Anwender in unterschiedlichen Szenarien bei der Suche nach Bildern durch Suchmechanismen auf Basis verschiedener Feature-Typen zu unterstützen, da die alleinige Nutzung inhaltsbasierter Bild-Features hierfür nicht ausreicht. Neben dem Bildinhalt (erfasst durch lokale und globale Features) sollen auch textuelle Beschreibungen/Annotationen sowie zeitliche und geographische Metadaten bei der Suche genutzt werden können. Wir haben bereits damit begonnen Zusammenfassungen für textuelle und geographische Daten zu analysieren. Ein weiteres Ziel ist es auf Basis unserer Zusammenfassungen einen verteilten Indexierungsmechanismus für lokale Bild-Features bereitzustellen, bei denen typischerweise mehrere Feature-Vektoren (auf Basis von SIFT Features) ein Bild beschreiben. Es soll analysiert werden wie sich Clusterhistogramme und andere Verfahren für die Ressourcenbeschreibung bei der Aggregation lokaler Features sowohl pro Dokument als auch pro Teilkollektion im Vergleich zu anderen Verfahren verhalten. Neben der Erweiterung auf andere Feature-Typen wollen wir die Retrieval-Leistung unseres Ansatzes weiter steigern sowie die Skalierbarkeit sicherstellen. Die Verfolgung dieser Ziele ist notwendig, damit sich unsere Source-Selection-Strategien von Anwendern zufriedenstellend im Rahmen eines effizienten Suchsystems – ggf. auch in anderen Kontexten – nutzen lassen. Die Kompaktheit unserer Zusammenfassungen verbunden mit einer relativ hohen Selektivität machen diese auch für andere Anwendungsszenarien wie z.B. für den Einsatz in traditionellen, baumbasierten Indexstrukturen interessant. Diese Anwendbarkeit wollen wir exemplarisch anhand der Integration in eine baumbasierte Indexstruktur zeigen.

Publications

• Clustering-Based Source Selection for Efficient Image Retrieval in Peer-to-Peer Networks. Proc. of 8th IEEE International Symposium on Multimedia, S. 823-830, San Diego, CA, USA, 2006
  M. Eisenhardt, W. Müller, A. Henrich, D. Blank, S. El Allali
  
• Comparison of Image Similarity Queries in P2P Systems. Proc. of IEEE Int. Conf. on Peer-to-Peer Computing, S.98-105, Galway, Irland, 2006
  W. Müller, P. O. Boykin, N. Sarshar, V. P. Roychowdhury
  
• Comparison of Image Similarity Queries in P2P Systems. Computer Communications, 31(2):375-386, 2007
  W. Müller, P. O. Boykin, V. P. Roychowdhury, N. Sarshar
  
• Farb-, Textur- Features und Distanzmaße für zusammenfassungsbasiertes P2P CBIR. Technischer Bericht, 2007
  S. El Allali, D. Blank, M. Eisenhardt, A. Henrich, W. Müller
  
• HTC, a fast P2P image browser based on JXTA. Proc. of IEEE International Symposium on Multimedia 2007, S. 73-74, Taichung, Taiwan, 2007
  W. Müller, S. El Allali, D. Blank, A. Henrich, T. Lauterbach
  
• Hunt the cluster: a scalable, interactive time Bayesian image browser for P2P networks. Proc. of 3rd IEEE Int. Workshop on Multimedia Information Processing and Retrieval, S. 317-322, Taichung, Taiwan, 2007
  W. Müller, S. El Allali, D. Blank, A. Henrich, T. Lauterbach
  
• Sample-based Creation of Peer Summaries for Efficient Similarity Search in Scalable Peer-to-Peer Networks. Proc. of 9th ACM SIGMM Workshop on Multimedia Information Retrieval, S. 143-152, Augsburg, Deutschland, 2007
  D. Blank, S. El Allali, W. Müller, A. Henrich
  
• Untersuchung des Einflusses verschiedener Bild-Features und Distanzmaße im inhaltsbasierten P2P Information Retrieval. Datenbanksysteme in Business, Technologie und Web (BTW 2007), 12. Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme" (DBIS), S. 382-396, Aachen, Deutschland, 2007
  S. El Allali, D. Blank, M. Eisenhardt, A. Henrich, W. Müller
  
• Clustering-Based, Load Balanced Source Selection for CBIR in P2P Networks. International Journal of Semantic Computing (IJSC), Vol. 2, S. 235-252, 2008
  M. Eisenhardt, W. Müller, D. Blank, S. El Allali, A. Henrich
  
• Designing Benchmarks for the Evaluation of Peer-to-Peer Information Retrieval Systems. In: Baumeister, J.; Atzmüller, M. (Hrsg.): Gesellschaft für Informatik (Veranst.): Workshop-Woche: Lernen, Wissen & Adaptivität. LWA 2008, Workshop FGIR, S. 57-64, Würzburg, 2008
  D. Blank, W. Müller und A. Henrich
  
• Image Data Source Selection Using Gaussian Mixture Models. Proc. of 5th International Workshop on Adaptive Multimedia Retrieval, Springer LNCS 4918, S. 170-181, Paris, Frankreich, 2008
  S. El Allali, D. Blank, W. Müller, A. Henrich
  
• VisualFlamenco: Dependable, Interactive Image Browsing Based on Visual Properties. Proc. of 6th IEEE Int. Workshop on Content-Based Multimedia Indexing, S. 568-575, London, UK, 2008
  W. Müller, M. Zech, A. Henrich, D. Blank
  
• Picadomo: Faceted Image Browsing for Mobile Devices. Proc. of 7th IEEE Int. Workshop on Content-Based Multimedia Indexing, Chania, Kreta, S. 249-254, 2009
  A. Hub, D. Blank, A. Henrich, W. Müller
  
• Source Selection for Image Retrieval in Peer-to-Peer Networks. Symposium on Future Directions in Information Access. Electronic Workshops in Computing (eWiC), Padua, Italien, 2009
  D. Blank
  
• Summarizing Georeferenced Photo Collections for Image Retrieval in P2P Networks. Proc. of Workshop on Geographic Information on the Internet Workshop (ECIR 2009 Workshop), S. 55-60, 2009
  D. Blank und A. Henrich