der 23. Workshop Grundlagen von Datenbanken (GvD) 2011 findet in Obergurgl, Tirol, Österreich statt. Dieser viertägige Workshop wird vom GI-Arbeitskreis Grundlagen von Informationssystemen im Fachbereich Datenbanken und Informationssysteme (DBIS) veranstaltet und hat die theoretischen, konzeptionellen und methodischen Grundlagen von Datenbanken und Informationssystemen zum Thema. Organisiert wird der Workshop 2011 von der Forschungsgruppe Datenbanken und Informationssysteme am Institut für Informatik an der Leopold
Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im deutschsprachigen Raum fördern, die sich grundlagenorientiert mit Datenbanken und Informationssystemen beschäftigen. Er ist insbesondere als Forum für Nachwuchswissenschaftler/-innen gedacht, die ihre aktuellen Arbeiten in einem größeren Forum vorstellen wollen. Mit der Kulisse der beeindruckenden Tiroler Bergwelt bietet der Workshop auf 2000 Metern Meereshöhe einen idealen Rahmen für die offenen und inspirierenden Diskussionen zu Datenbanken und Informationssystemen. 18 Papiere wurde aus den Einsendungen ausgewählt und werden in Obergurgl vorgestellt. Sie spannen ein weites Feld auf und zeigen, wie aktiv und inspirierend die Datenbankforschung heute sein kann. Gerade das neue Feld der Hauptspeicher- und NoSQL-Datenbanken hat die Auseinandersetzung mit dem, was die eigentlichen Grundlagen der Datenbanken sind, neu beflügelt. Dabei ist der Workshop über die Jahre, inzwischen 23 (!), längst von einem ursprünglich eher theorie- und grundlagenlastigen Workshop auch zu einer Plattform für anwendungsgetriebene und praktische Datenbankforschung geworden und hat sich dabei auch dem damit verbundenen Gebiet der Informationssysteme geöffnet. Wichtig ist die offene Atmosphäre in der man, diesmal zurückgezogen in der Bergwelt, ohne Zeitzwang, intensiv diskutieren kann. Dies bedeutet insbesondere nicht nur die üblichen drei Fragen nach dem Vortrag bevor der nächste kommt, sondern sich die Zeit nehmen, vorgestellte neue Gedanken und Ansätze wirklich gemeinsam zu diskutieren. Davon profitieren alle.
Hinzu kommen drei interessante Keynote-Vorträge von Harald Frick, Thomas Neumann und Wolf-Tilo Balke. Ihnen sei an dieser Stelle für Ihre Bereitschaft und
Weiters danken wir dem Programmkomitee, das diesmal erstmals auf 18 Mitglieder gewachsen ist und allen Gutachtern für ihre Arbeit. Das Organisations-Komitee und dabei insbesondere Fr. Eva Zangerle und Hr. Wolfgang Gassler haben den Großteil der Arbeit gestemmt. Ohne ihren unermüdlichen Einsatz und ihr Engagement wäre der 23. Workshop nicht zustande gekommen. Herzlichen Dank! Besonderer Dank gilt auch Eike Schallehn und dem GI-Arbeitskreis "Grundlagen von Informationssystemen", der sich mit viel Einsatz um die erfolgreiche jährliche Austragung des Workshops bemüht. Schließlich gilt mein Dank allen denen, die im Hintergrund mitwirkten, dem ganzen DBIS-Team in Innsbruck, dem Haus in Obergurgl und nicht zuletzt allen Autoren und Vortragenden. Sie machen den Workshop erst zu dem, was er ist: Eine inspirierendes und motivierendes Forum für offene Diskussionen über alle neuen Ideen rund um Datenbanken und Informationssysteme. Sicher wird auch die gepflegte Hütten- und Bergatmosphäre und der offene Kamin am Abend das seine dazu beitragen. Ich freue mich darauf.
Inhaltsverzeichnis XQuery Framework for Interoperable Multimedia Retrieval ................................................................................................. 73 (Mario Döller, Florian Stegmaier, Alexander Stockinger and Harald Kosch) Workload Representation across Different Storage Architectures for Relational DBMS ...................................................... 79 (Andreas Lübcke, Veit Köppen und Gunter Saake) Data Locality in Graph Databases through N-Body Simulation............................................................................................. 85 (Dominic Pacher, Robert Binna und Günther Specht) SpiderStore: A Native Main Memory Approach for Graph Storage ...................................................................................... 91 (Robert Binna, Wolfgang Gassler, Eva Zangerle, Dominic Pacher und Günther Specht) Kriterien für Datenpersistenz bei Enterprise Data Warehouse Systemen auf In-Memory Datenbanken............................... 97 (Thorsten Winsemann and Veit Koeppen) Ein Verfahren zur automatischen Erstellung eines visuellen Wörterbuchs für die Bildsuche ................................................ 103 (Magdalena Rischka) A feedback guided interface for elastic computing ................................................................................................................ 109 (Sebastian Schönherr, Lukas Forer, Hansi Weißensteiner, Florian Kronenberg, Günther Specht und Anita Kloss-Brandstätter)
Massive parallel in-memory database with GPU based query coprocessor
QuiLogic In-Memory DB Technology This talk presents work on transforming SQL-IMDB, a commercial available inmemory database system, into a massive parallel, array structured data processor extending the “classic” query engine architecture with GPU based co-processing facilities. The chosen approach is not just a simple re-implementation of common database functionality like sorting, stream processing and joins on GPUs, instead we take a holistic view and extend the entire query engine to work as a genuine, inmemory, GPU supported database engine. We have partitioned the query engine so that both CPU and GPU are doing what they are best at. The new SQL-IMDBg query execution engine is a “Split-Work” engine which takes care to optimize, schedule and execute the query plan simultaneous and in the most efficient way on two (or more) different memory devices. The principal architecture of the engine, based on simultaneous managing multiple memory devices (local/shared/flashmemory ), was a natural fit to include the new GPU/video memory as just another (high speed) memory device. All internal core engine data structures are now based on simple array structures, for maximum parallel access support on multi- and many core hardware. Data tables located on GPU video memory can always queried together with CPU local- and shared-memory tables in “mixed” query statements. Columns on GPU tables are also accessible through GPU based indexes. A special index structure was developed based on sorted containers supporting both CPU and GPU based index lookups. Table data can be manually and automatically split between CPU and GPU and is held in vertically partitioned columns, which ease the stream like processing for basic scan primitives and coalesced memory access mechanism on GPU devices. Based on our experience gained, we see the GPU/video memory as another important high speed memory device for in-memory database systems, but which do not yet fit well into the architecture of current database engines and therefore require a major effort in re-engineering the entire core database architecture. Efficient Query Processing on Modern Hardware
Lehrstuhl für Informatik III: Datenbanksysteme
Fakultät für Informatik Technische Universität München Most database systems translate a given query into an expression in a (physical) algebra, and then start evaluating this algebraic expression to produce the query result. The traditional way to execute these algebraic plans is the iterator model: Every physical algebraic operator conceptually produces a tuple stream from its input, and allows for iterating over this tuple stream. This is a very nice and simple interface, and allows for easy combination of arbitrary operators,but it clearly comes from a time when query processing was dominated by I/O and CPU consumption was less important: The iterator interface causes thousands of expensive function calls, degrades the branch prediction of modern CPUs, and ofter results in poor code locality and complex book-keeping.
On modern hardware query processing can be improved considerably by processing tuples in a data centric, and not an operator centric, way. Data is processed such that it can be kept in CPU registers as long as possible. Operator boundaries are blurred to achieve this goal. In combination with an code compilation framework this results in query code that rivals the speed of hand-written code. When using these techniques in the HyPer DBMS, TPC-H Query 1 for example can single-threaded aggregated the scale factor 1GB data set in about 68ms on commodity hardware. Conceptual Views for Entity-Centric
Search
Databases and Informationsystems
University of Braunschweig The retrieval of entity data has always been a core application of database systems and querying an entity's attributes can be efficiently done using declarative languages like SQL. But today's retrieval tasks more and more focus also on conceptual aspects of entities, which often are not directly expressed by attributes.
For instance, users might want to find a 'thrilling' novel, unfortunately there is no 'suspense factor' attribute in today's online book stores. Consequently, entity-centric search suffers from a growing semantic gap between the users’ intended queries and the database’s schema. In the talk, we will propose the notion of conceptual views, an innovative extension of traditional database views, which aim to uncover those query-relevant concepts that are often only reflected by unstructured data related to some entities. We will also take a look at promising techniques for mining conceptual information and discuss open issues. Ein Ansatz zu Opinion Mining und Themenverfolgung für eine Medienresonanzanalyse
Thomas Scholz Heinrich-Heine-Universität Düsseldorf
Institut für Informatik
Universitätsstr. 1 D-40225 Düsseldorf, Deutschland scholz@cs.uni-duesseldorf.de pressrelations GmbH
Entwicklung
Klosterstr. 112
D-40211 Düsseldorf, Deutschland thomas.scholz@pressrelations.de Zusammenfassung Heutzutage gibt es eine unuberschaubare Anzahl von Medien mit enorm vielen Artikeln und Beitragen. Da in ihnen neben vielen anderen potenziell nutzlichen Informationen wertvolle Meinungen zu Themen enthalten sind, ist eine automatische Beobachtung dieser Medien sehr interessant, birgt aber zwei gro e Herausforderungen: eine automatisierte Tonalitatsbestimmung (Opinion Mining) kombiniert mit einer Themenverfolgung. Diese zwei Aufgaben sind Teilgebiete des Text Minings, auch Text Data Mining oder Knowledge Discovery in Texten genannt. Diese Arbeit beschreibt einen Ansatz fur Opinion Mining und Themenverfolgung basierend auf einer Information Extraction Architektur. In der Evaluation wird gezeigt, wie dieser Ansatz fur Opinion Mining oder eine Themenverfolgung eingesetzt werden kann.
Kategorie Data Mining and Knowledge Discovery Schlüsselwörter Opinion Mining, Topic Tracking, Text Mining
EINLEITENDE MOTIVATION
Das Internet, Printmedien, TV, Horfunk und Soziale Netzwerke sind eine Fundgrube von Meinungen zu bestimm-ten Themen in Form von Artikeln oder Beitragen. Heutzutage ist es moglich diese in digitaler Form zu erfassen. Im Online Bereich konnen beispielsweise Crawler eingesetzt werden um die Artikelseiten von Internetnachrichten zu erfassen. Durch Analyse des Seitenquelltextes und den Einsatz von Heuristiken kann der eigentliche Artikeltext gefunden werden. Artikel aus Printmedien konnen eingescannt und mit optischer Zeichenerkennung (OCR) digitalisiert werden. Artikel und Beitrage in digitaler Textform bieten auch teilweise die TV23rd GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 31.05.2011 - 03.06.2011, Obergurgl, Austria.
Copyright is held by the author/owner(s). und Horfunksender an. Im Bereich Soziale Netzwerke haben sich Dienstleister darauf spezialisiert, die Diskussionen und Kommentare aus Netzen wie Twitter, Facebook oder bestimmte Foren automatisch zu erfassen und als Daten anzubieten.
Die Auswertung von einer gro en Menge dieser Artikel und Beitrage ist hingegen schwierig. Eine manuelle Auswertung ist nur mit erheblichen Aufwand moglich und fur eine automatische Auswertung gibt es erste Ansatze, aber langst noch keine allumfassende Losung. Mit der Aufgabe diese Daten zu erfassen und auszuwerten beschaftigt man sich beim Medienmonitoring bzw. bei der Medienresonanzanalyse. In diesem Bereich arbeiten Ausschnittdienste.
Die riesigen Strome aus Artikeln und Beitragen enthalten viele potenziell wertvolle Informationen zu Themen, Personen, Firmen, Produkten, usw. Besonders die PR- und MarketingAbteilungen von Unternehmen, Parteien und Verbanden interessieren fur diese Daten und deren Auswertung. Dabei interessiert man sich besonders dafur, inwiefern sich das Image des Unternehmens oder das Image von bestimmten Produkten, Marken und Dienstleistungen entwickelt. Aber auch wie bestimmte Personen (Werbetrager, Vorstandsmitglieder, etc.) in diesen Medien wahrgenommen werden. Au erdem von Bedeutung ist die Frage, auf welche Weise bestimmte Themen mit dem Unternehmen verknupft sind. Beim Medienmoitoring geht es darum Artikel zu erfassen und sammeln, die fur PR- und Marketing Abteilungen interessant sind. Dazu werden von ihnen Themen oder Schlagworter de niert. Dies ist auch interessant fur Verbande, Vereine, Parteien, Stiftungen, die teilweise zu klein sind um uber eine eigene PR-Abteilung zu verfugen.
Bei der Medienresonanz geht es darum zu bestimmten Themen das mediale Echo zu analysieren.
Dies kann z. B. auf folgende Art und Weise geschehen: Zunachst werden Themen de niert, die es zu untersuchen gilt. Dies konnen beispielsweise Marken von Firmen sein oder andere Begri e wie Produktnamen, Personen oder ahnliches. Bei einem Medienbeobachter und einem Ausschnittdienst wurden die Kunden (meist PR-Abteilungen von Firmen oder Organisationen wie Parteien) Themen durch bestimmte Schlagworter festlegen. Die Schlagworter werden dann von Crawlern in den Medien gesucht, um die entsprechenden Artikel zu erfassen.
Dann konnen diese Artikel bewertet werden, z.B. ob sie wirklich relevant zu diesem Thema sind, wie exklusiv dieser Beitrag ist und am wichtigsten welche Tonalitat er besitzt.
Die Tonalitat beschreibt, ob ein bestimmter Artikel positive oder negative Meinungen zu einem Thema enthalt. Es ist auch beides moglich. Oft wird dies mit einem negativen Zahlenwert fur eine negative Tonalitat und einem positiven Zahlenwert fur eine positive Tonalitat festgehalten. Diese Bestimmung der Tonalitat wird heutzutage bei den Medienbeobachtern noch rein manuell durch Medienanalysten ausgefuhrt, die die Texte lesen und meinungsbeinhaltende Passagen identi zieren und bewerten.
Allerdings sto en solche Beobachtungsdienste aufgrund der Menge der Artikel und Beitrage heute an ihre Grenzen, was manuell noch zu bearbeiten ist. Die Nachrichtenanzahl, die diese Dienste bearbeiten, nimmt stetig zu, aufgrund der starkeren Digitalisierung der Medien wie auch durch Entstehen neuer Medien im Internet wie der Bereich Social Media. 1.3
Opinion Mining und Themenverfolgung als
Lösung
Als Losung fur eine automatische Medienresonanzanalyse bieten sich Opinion Mining und Themenverfolgung an, um die doch bisher meist manuell geleistete Arbeit zu unterstutzen und perspektivisch zu ersetzen.. Mit Hilfe des Opinion Minings soll es gelingen meinungstragende Passagen innerhalb eines Textes zu nden und dann automatisch mit einem Tonalitatswert zu versehen. Durch die Realisierung einer automatischen Themenverfolgung konnte die manuell vorgenommene Schlagwortverwaltung fur die Themenzuordnung abgelost werden. In der Kombination hatte man dann eine automatische Medienresonanzanalyse.
Der Rest dieser Arbeit kann wie folgt zusammengefasst werden: Zunachst werden die Ansatze aufgezeigt, die schon zum Bereich des Opinion Minings und der Themenverfolgung entwickelt wurden. Dann wird die Architektur entworfen, wodurch eine automatische Medienresonanzanalyse auf Basis von Natural Language Processing und Information Extraction realisierbar wird. Anschlie end wird in ersten Versuchen demonstriert, wie die Vorverarbeitung fur Opinion Mining und Themenverfolgung eingesetzt werden konnen. Abschlie end werden dann aufgrund dieser Ergebnisse Schlussfolgerungen fur das weitere Vorgehen gezogen.
VERWANDTE ARBEITEN
Opinion Mining
Um die Tonalitat eines Textes zu bestimmen, benutzen
viele Ansatze wie [
Eine typische Menge von Saattonalitatswortern sieht
beispielsweise so aus [
Diesen Aufbau durch einen Bootstrapping Algorithmus
benutzt auch das bekannteste Worterbuch: SentiWordNET
[
Andere Ansatze benutzen nur WordNET oder ahnliche,
allgemeine Worterbucher [
Viele Ansatze [
Bei Kundenrezensionen ist eine Identi kation von
Meinungsblocken nicht notig. Eine Rezension besteht nur aus
Meinungsblocken. Um generell Meinungen zu nden, auch
wenn dies in einem langen Zeitungsartikel nur ein kleiner
Absatz uber ein bestimmtes Unternehmen ist, sind zunachst
noch anderere Schritte zuvor notig. Ein satzbasierter Ansatz
[
Auch kann man davon ausgehen, dass bei Sentiment Analysis Ansatzen man schon mit einem kleineren Worterbuch mit Tonalitatswerten zurecht kommt, da man es bei den Zielen der Rezension nur mit Produkten und ahnlichem wie Filmen, Hotels usw. zu tun hat. Bei einer Medienresonanzanalyse werden aber gleichzeitig Entitaten wie Personen, Organisationen, Produkte, Events oder Aktionen im Fokus stehen. Somit andern sich auch die tonalitatsbildenen Worter, da nicht allein durch eine Beschreibung eines Produktes etc. eine Tonalitat ausgedruckt wird.
In einer Rezension will der Autor seine Meinung dem Leser direkt vermitteln. In Zeitungsartikeln beschreibt der Autor nicht nur direkte Meinungen, oft wird eher uber Fakten und Handlungen gesprochen, die sich auf bestimmte Personen oder Organisationen beziehen, die dann eine Tonalitat entstehen lassen. Darum sollte ein solcher Ansatz auch nicht nur Adjektive, sondern mehr Wortarten miteinbeziehen (z.
B. Verben). Die meisten Ansatze [
Themenverfolgung
Wissenschaftliche Methoden [
Weiterhin gibt es einen Ansatz [
Eine andere, sehr erfolgreiche Methode ist die Verfolgung
von wortlicher Rede [
Ein Zitat steht dann fur ein Thema. Durch einen graphbasierten Ansatz werden Zitate auch wieder erkannt, wenn sie verkurzt oder leicht abgeandert werden.
Selten werden verschiedene Merkmale kombiniert [
ANFORDERUNGEN FÜR DEN ANSATZ
Die verschiedenen Arbeiten [
Natural Language Processing
Gerade Natural Language Processing (NLP) wird in
vielen anderen Ansatzen benutzt, um unter anderem Adjektive
zu identi zieren [
Information Extraction
Durch Information Extraction (IE) [
Web
Crawler Satz Segmentierung
Tokenisierung Part-Of-Speech
Tagging
Stemming Merkmale extrahieren
Lernverfahren
Vorhersage
modell
Abbildung 1: Ablauf der Verarbeitungsschritte auch nicht exakt die selbe Zeichenkette verwendet wird. Im Falle einer Person konnte z.B. erst der komplette Name und spater im Text nur noch der Nachname benutzt werden.
Kommt eine Pronomenau osung hinzu, dann wird eine Entitat auch dann weiterverfolgt, wenn im Text fur die Entitat nur noch Pronomen stehen wie \sie" oder \ihn", die sich aber auf die entsprechende Person beziehen.
Daruber hinaus kann es noch sehr nutzlich sein, weitere Informationen wie den grammatikalischen Fall oder das Geschlecht von Wortern zu bestimmen. Auch Textpassagen mit wortlicher Rede oder die Extraktion von Nomenphrasen sind weitere nutzliche Informationsbausteine, die in einer weiteren Verarbeitung aufgegri en werden konnen. 3.3
Neue Möglichkeiten
Diese Vorverarbeitung lasst sich fur das Opinion Mining und die Themenverfolgung folgenderma en einsetzen:
Durch die Bestimmung der verschiedenen Wortarten lassen sich fur das Opinion Mining Worterbucher aus Adjektiven, Verben und Adverben extrahieren. Hier stellt sich noch die Frage, wie man diesen Tonalitatswert bestimmt. Viele Ansatze bilden dazu Ma e, die auf das Zusammenauftreten mit positiven bzw. negativen Tonalitatswortern beruhen.
Wenn man viele annotierte Meinungsblocke besitzt, kann man auch Standardansatze aus dem Information Retrieval wie TF-IDF darauf anwenden. Ebenso kann man Bootstrapping einsetzen.
Auch Nominalphrasen konnen in dem Worterbuch aufgenommen werden. Diese konnen auch fur die Darstellung eines Themas von gro em Nutzen sein.
Durch die Erkennung von Personen, Organisationen usw. kann man bei der Tonalitatsbestimmung unterscheiden, ob nun eine Person oder ein Produkt besprochen wird. Dadurch kann man die Bewertung des Vokabulars darauf anpassen.
Bei der Themenverfolgung kann man Themen durch die Anwesenheit von Entitaten beschreiben. Das Vorhandensein bzw. die Abwesenheit einer Entitat kann ebenso wie Schlagworter dazu benutzt werden ein Thema zu beschreiben und damit auch zu verfolgen. Auch konnte man genauso wie bei Schlagwortern das Auftreten mit TF-IDF gewichten, was nun konkret bedeuten wurde: Die Hau gkeit einer Entitat multipliziert mit der inversen Dokumentenfrequenz in der sie vorkommt. Bei dieser Gewichtung ist noch zu klaren, was den gesamten Dokumentenkorpus darstellt. Dies konnte ein zeitlicher Ausschnitt sein (z. B. ein Monat).
Zusatzlich konnte diese Gewichtung interessante Informationen uber die Entwicklung eines Themas liefern, weil es anzeigt welche Entitaten in welchen Themen eine starke Rolle spielen.
Dies kann man zusatzlich mit bisherigen Ansatzen fur Themendarstellung durch Schlagworter sowie die Verfolgung von wortlicher Rede kombinieren.
Diese Vorverarbeitungsschritte benotigen naturlich auch Rechenzeit. Da allerdings dazu auf einem riesigen Datenfeld (den Texten) nur gelesen werden muss, ist eine Parallelisierung der Vorverarbeitung durchfuhrbar.
EVALUATION
Um zu uberprufen, wie dieser Ansatz mit NLP und IE fur Opinion Mining und eine Themenverfolgung eingesetzt werden kann, wird evaluiert, wie mit bestimmten Wortarten automatisch eine Tonalitat bestimmt werden kann und ob mit Entitaten eine thematische Zuordnung moglich ist.
Dafur werden zuvor klassi zierte Daten benutzt.
Diese Evaluation soll erste Hinweise geben, ob es grundsatzlich mit diesen Merkmalen moglich ist, die fundamentalen Bausteine einer Medienresonanzanalyse maschinell durchzufuhren: Tonalitatsbestimmung und Themenzuordnung.
Dabei geht es auch weniger um die Bestimmmung des optimalen Lernverfahrens. Der Einfachheit halber wurden dazu im ersten Schritt drei typische Klassi kationsverfahren verwendet. Diese bieten sich an, weil die Daten schon vor der Evaluation mit entsprechenden Klassen versehen sind. 4.1
Tonalitätsbestimmung
Fur diesen Test wurden 1600 Nachrichtenmeldungen mit 800 positiven und 800 negativen Meldungen analysiert. Um eine Tonalitat zu erhalten, wurden mittels NLP Adjektive, Adverbien und Verben aus dem Text extrahiert und mittels Stemming auf ihre Stammform zuruckgefuhrt. Danach wurden invertierte Listen von diesen Dokumenten erzeugt und die einzelnen Terme mittels TF-IDF gewichtet.
Nach der Erzeugung dieser Attribute wurden die Daten in einer 10-fach-uber-Kreuz-Validierung durch drei Klassi kationsverfahren getestet: Support Vector Machine (SVM), Naive-Bayes und k-Nearest-Neigbours mit k=7.
Bei den Resultaten zeigte sich, das diese doch recht naive Methode (es wird beispielsweise nicht betrachtet, ob irgendwelche Negationen anwesend sind) tatsachlich erste brauchbare Hinweise geben kann.
Es zeigte sich, dass die Vermutung, nur Adjektive allein wurden die Tonalitat bestimmen, nicht zutri t. Die Gruppe der Verben schneidet schon besser ab. Hier scheint der Unterschied zwischen Sentiment Analysis bezogen auf Kundenrezensionen und Opinion Mining bezogen auf Nachrichten deutlich zu werden. Kundenrezensionen beziehen ihre Tonalitat wohl eher durch Adjektive (\die Bildqualitat ist super" oder \der Autofokus ist zuverlassig")1, wahrend in Nachrichten dies nicht unbedingt der Fall ist (\VerbraucherVerben Adverbien 100 90 80 70 60 in%50 roe 40 c -S 30 F 20 10 0 1Beispiele aus einer Amazon.de Kundenrezension 2Beispiele von Spiegel.de am 4.3.2011
Klassi kationsverfahren
Genauigkeit Support Vector Machine Naive-Bayes k-Nearst-Neighbour Support Vector Machine Naive-Bayes k-Nearst-Neighbour Support Vector Machine Naive-Bayes k-Nearst-Neighbour
Orte
Alle
Abbildung 3: Themenzuordnung schutzer warnen vor der 'Umfrucht'-Falle" oder \Rekordjahr: Audi belohnt Mitarbeiter mit Millionen")2.
Das beste Klassi kationsverfahren der drei hier getesteten Verfahren ist eindeutig die Support Vector Machine. Darum wird sie nun auch im zweiten Teil der Evaluation angewendet. 4.2
Themenzuordnung
Im zweiten Test wurden 204 Texte zu zwei sehr allgemeinen Themen gesammelt. Die Themen waren \Finanzmarkt" und \Parteien".
Dann wurden aus diesen Texten die Entitaten Personen, Organisationen und Orte extrahiert. Diese Entitaten wurden dann wiederum als Terme genommen, die mittels TFIDF gewichtet wurden. Abschlie end wurde eine SVM benutzt um die Daten in einer 10-fach-uber-Kreuz-Validierung zu evaluieren.
Die Ergebnisse veranschaulicht Abbildung 3. Interessant ist hier, dass bei den einzelnen Merkmalen die Organisationen das beste Resultat liefern (ca. 85,29 %). Dies kann aber mit der Themenauswahl (\Finanzmarkt" und \Parteien") zu tun haben, in der wahrscheinlich generell mehr Organisationen eine Rolle spielen bzw. die Organisationen das trennende Kriterium sind.
Auch Orte scheinen charakteristisch fur Themen zu sein (ca. 81,37 %). Kaum uberraschend spielt der Ort \Frankfurt" im ersten Thema eine wichtigere Rolle als im zweiten Thema und fur \Berlin" ist es umgekehrt.
Das Merkmal Person ist nicht so erfolgreich (nur ca. 68,14 %). Bei den hier vorliegenden Themen gab es hinsichtlich der Personen auch durchaus U berschneidungen, weil mehrere Personen in beiden Themen auftauchten. Eine interessante Frage stellt sich nun dahingehend, ob dies bei kleineren Themen vielleicht seltener der Fall ist.
Insgesamt zeigt sich das wunschenswerte Resultat: Mit allen Entitaten gemeinsam wird das beste Ergebnis erzielt (ca. 85,78 %). 5. SCHLUSSFOLGERUNG UND WEITER
FÜHRENDE FRAGESTELLUNGEN
Die Ergebnisse der Evaluation lassen darauf schlie en, dass sich aufbauend auf dem beschriebenen Anforderungspro l eine automatische Tonalitatsbestimmung und Themenverfolgung realisieren lasst.
Zu dem Aspekt des Opinion Minings fehlen noch viele Bestandteile, die in einem Text die Tonalitat verandern konnen. Es hat sich gezeigt, dass die Worte allein schon im Ansatz funktionieren, aber noch gro es Verbesserungspotenzial vorhanden ist.
Dazu ist zu erarbeiten, ob es noch bessere Methoden der Gewichtung gibt als der Standardansatz uber TF-IDF. Auerdem muss uberlegt werden, wie man die Tonalitatsworter beispielsweise in einem Worterbuch verwalten kann. Als nachste Fragestellung schlie t sich dann an, wie man mit semantischen Merkmalen wie Negation oder dem Bezug zu Entitaten umgeht.
Daruber hinaus ist ein weiteres spannendes Problem die Identi zierung der Meinungsblocke, also der Textpassagen, die eine Meinung beinhalten. Ein Tonalitatsgrenzwert fur Abschnitte und Satze ist denkbar, aber auch die Lokalisierung durch die Entitaten im Text, fur die man sich erstens verstarkt interessiert und die sich zweitens mit ausreichend vielen tonalitatsbildenen Wortern umgeben.
Bei der Themenverfolgung haben die Experimente zunachst nur den Wert von Entitatenerkennung in einem einfachen Beispiel gezeigt. Hier musste die Kombination mit klassischen Schlagwortansatzen und neueren Ansatzen, wie die Einbeziehung von wortlicher Rede, genutzt werden, um eine bessere Themendarstellung zu erhalten und zusatzlich interessante Fakten uber ein Thema zu sammeln. Diese Fakten konnen Folgendes beinhalten: Wie stark sind welche Personen mit welchen Themen verbunden? Oder gibt es zentrale Zitate/Aussagen, die immer wieder aufgegri en werden.
Allerdings muss zunachst die Frage beantwortet werden, wie man die Entitaten sinnvoll mit Ansatzen wie Schlagwortern und die Verfolgung von Zitaten verbinden kann. Dies wird Gegenstand der zukunftigen Arbeit sein, wobei auch zu klaren ist, wie man diese Kombination fur die Verwaltung einer Themenverfolgung sinnvoll einsetzen kann.
Weiterhin ist dabei die Gro e eines Themas zu beachten (fur die De ntion der Gro e eines Themas gibt es viele Moglichkeiten, die Anzahl der Artikel zu einem Thema ist eine nahe liegende Losung). Wie wirkt sich die Gro e der Themen auf die Verwaltung aus? Und wie verhalt sich die Themendarstellung mit Merkmalen dadurch? In der Evaluation kam schon die Frage auf, ob Personen bei kleineren Themen nicht eine wichtigere Rolle zur Themenbeschreibung spielen.
Insgesamt zeigt sich aber, dass die Vorverarbeitung durch Natural Language Processing und Information Extraction von gro em Vorteil ist, da sie fur beide Aufgabenstellungen, Opinion Mining und Themenverfolgung, viele neue Moglichkeiten ero net und diese im Ansatz fur eine Medienresonanzanalyse funktionieren.
LITERATUR
KDD '09, pages 497{506, 2009.
[
Comparing semantic associations in sentences and
paragraphs for opinion detection in blogs. In Proc. of
the International Conference on Management of
Emergent Digital EcoSystems, MEDES '09, pages
80:483{80:488, 2009.
[
WI-IAT '09, pages 279{282, 2009.
[
October 2003.
[
Hence knowing the basic facts about a data set allows to establish an adequate estimation about the expected memory footprint.
RELATIVE ADDRESSES
Using absolute pointer addresses for the location of nodes enables the navigation between two nodes in O(1) as it has been explained in the section before. The drawback of this concept is that storing a persistent state of a whole graph database can become quite complex. The reason for this is that the database can only be dumped either by serializing the whole graph and later deserializing the whole graph or by dumping the whole memory snapshot and swizzling the pointers to their correct representation at load time.
Another alternative to these approaches is to arrange the whole database content based on an o set address. Hence all memory locations have to be converted into relative addresses based on this o set. Resolving such relative pointers yields in an overhead, which is negligible compared to the total amount of time needed to fetch an arbitrary junk of memory. The time for fetching an arbitrary chunk of memory can vary between some cpu cycles, when accessing memory already located within L1-cache, up to some hundreds cpu cycles, when accessing a random chunk of memory which is not available in the cache hierarchy yet.
In the context of SpiderStore we decided to use relative
addressing. This has two advantages. The rst advantage
is that the general architecture of SpiderStore is still
applicable and the overhead introduced through relative
addressing is insigni cant in the SpiderStore concept as it has
been explained before. The main advantage of this
addressing scheme is that database restarts can be executed
within a few milliseconds. This is possible by facilitating
the Unix memory mapping techniques which does not
dismiss the mapped pages unless another executable allocates
large amounts of memory. Furthermore this concept allows
to facilitate the copy on write approaches used by the
HyPer project [
Due to the lack of a customized memory allocator, the SpiderStore snapshot mechanism is currently implemented as a read only approach. Each snapshot is split up into ve parts. One part is responsible for the storage of the node data structures, another for the indexes between node identi ers and node addresses. One more le stores the node identi ers. The other les are responsible for the storage and indexing of predicate nodes and for the storage of the edge information. The separation into several les prevents memory fragmentation and leads to shorter "addresses" for nodes, predicates and strings. For example all entries within the node, predicate or index les have uniform sizes and can therefore be seen as simple array structures.
As a platform for the evaluation a server equipped with two Intel Xeon L5520 Quad Core CPUs, 2.27 GHz, Linux kernel 2.6.18, CentOS, 64-bit architecture and 96 GB main memory was used. 4.1
DataSet
For the evaluation we used the YAGO2 [
The data set consist of of 194,350,853 triples (98 predicates,
28,744,214 unique subjects and objects). The queries
executed on this data set are derived from the queries on the
YAGO data set used in the benchmark presenting the
RDF3X approach [
For the evaluation of SpiderStore we used Virtuoso [
The test results are separated into two parts. The rst part compares the bulk import times of the di erent systems. The bulk import time is speci ed as the time needed to load the data, to create the indexes and to ensure that a persistent state of the database is written to disk. A summary of the load times can be seen in Table 1. As can be seen, SpiderStore is signi cantly faster than any of the other systems. The reason for this is that SpiderStore, due to its implicit statistics, does not need to explicitly create statistics or indexes.
System SpiderStore Jena RDF-3X Virtuoso 1:09:18 1:36:35 1:21:12 3:32:16
The second part of the evaluation compares the query execution for each query on the YAGO2 data set. Queries with an execution time over 15 minutes without producing any output are marked with "DNF". For the calculation of the geometric mean, a query runtime of 15 minutes is assumed for each cell which is marked with "DNF". Due to large result sets for query C-1 this limit is set to 60 minutes. The results of this evaluation are shown in Table 2.
DNF
DNF DNF
DNF 2197,672 6,876,673 DNF geom. mean
Considering the average execution time, RDF-3X performs better than all other stores tested. While SpiderStore in the average case is the second fastest system, two queries exist where SpiderStore outperforms the other stores. In the case of those queries, the coarse heuristics were able to generate a highly e cient execution plan. On the other side considering the queries C1-C3 SpiderStore has signi cant problems to arrange and optimize the execution order to obtain better results. Regarding query C1 even though intermediate results where present the total execution time did exceed the time limit of one hour. The reason for the performance shortcomings in the case of those queries is that the selectivity estimations based on the triple selectivity used for the generation of the execution plan can in some cases produce misleading execution orders. This is due to the fact that the cardinality of properties is not considered in the current algorithm. Regarding the other evaluated systems Jena TDB seem to have severe problems when executing queries on such large knowledge bases, because only two queries were able to determine the results within the given time frame.
Whereas Virtuoso can be considered as the third fastest system, which has a stable performance without any negative outliers.
RELATED WORK
Several approaches exist for storing graph based data in databases. In the particular case of this paper we focus on RDF-stores because SpiderStore, the developed system, can be considered as part of this category. Hence we give a short overview about the di erent approaches available for storing RDF data.
For storing RDF-data, two approaches are prevailing. On the one hand the approach of mapping the RDF-data onto relational schema exists while on the other hand the approach of native RDF-stores exist.
The mapping of RDF-data onto relational databases is done either by facilitating a large triple table, where the columns correspond to the RDF atoms subject, predicate and object or by clustering the triples according to their predicate into several tables. The latter approach is called property tables.
Both approaches are less than perfect because both su er
from severe performance drawbacks imposed by the
architecture of relational databases. For example in the property
tables approach the number of tables is equal to the number
of properties in the worst case. Several approaches which
extend these two main approaches when mapping RDF-data
onto relational database have been developed and are
benchmarked in [
CONCLUSION AND FUTURE WORK
In this paper we presented the SpiderStore memory
layout, which is able to store arbitrary graphs. The node
centric layout has been discussed in detail and a formula for
the estimation of the space consumption was described. An
enhancement to the basic layout introducing a relative
addressing schema was presented. Finally our experiments
showed that a node centric layout is able to perform
arbitrary SPARQL-queries on knowledge bases of up to 190
mio nodes with a performance comparable to highly
sophisticated RDF-stores. This promises further performance
improvements because the query optimisation approach, which
has been developed in [
APPENDIX
YAGO data set pre x rdfs:hhttp://www.w3.org/2000/01/rdf-schema#i pre x xsd:hhttp://www.w3.org/2001/XMLSchema#i pre x owl:hhttp://www.w3.org/2002/07/owl#i pre x rdf:hhttp://www.w3.org/1999/02/22-rdf-syntax-ns#i pre x yago:hhttp://www.mpii.de/yago/resource/i A1: SELECT ?GivenName ?FamilyName WHERE f ?p yago:hasGivenName ?GivenName. ?p yago:hasFamilyName ?FamilyName. ?p rdf:type ?scientist. ?scientist rdfs:label "scientist". ?p yago:wasBornIn ?city. ?city yago:isLocatedIn ?switzerland. ?switzerland yago:hasPreferredName "Switzerland". ?p yago:hasAcademicAdvisor ?a. ?a yago:wasBornIn ?city2. ?city2 yago:isLocatedIn ?germany. ?germany yago:hasPreferredName "Germany". g A2: SELECT ?name WHERE f ?a yago:hasPreferredName ?name. ?a rdf:type ?actor. 1 ?actor rdfs:label "actor". ?a yago:actedIn ?m1. ?m1 rdf:type ?movie. ?movie rdfs:label "movie". ?m1 yago:hasWikipediaCategory "German lms". ?a yago:directed ?m2. ?m2 rdf:type ?movie2. ?movie2 rdfs:label "movie". ?m2 yago:hasWikipediaCategory "Canadian lms". g B1: SELECT ?name1 ?name2 WHERE f ?a1 yago:hasPreferredName ?name1. ?a2 yago:hasPreferredName ?name2. ?a1 rdf:type yago:wikicategory English actors. ?a2 rdf:type yago:wikicategory English actors. ?a1 yago:actedIn ?movie. ?a2 yago:actedIn ?movie. FILTER (?a1 != ?a2) g B2: SELECT ?name1 ?name2 WHERE f ?p1 yago:hasPreferredName ?name1. ?p2 yago:hasPreferredName ?name2. ?p1 yago:isMarriedTo ?p2. ?p1 yago:wasBornIn ?city. ?p2 yago:wasBornIn ?city. g B3: SELECT distinct ?name1 ?name2 WHERE f ?p1 yago:hasFamilyName ?name1. ?p2 yago:hasFamilyName ?name2. ?p1 rdf:type ?scientist1. ?p2 rdf:type ?scientist2. ?scientist1 rdfs:label "scientist". ?scientist2 rdfs:label "scientist". ?p1 yago:hasWonPrize ?award. ?p2 yago:hasWonPrize ?award. ?p1 yago:wasBornIn ?city. ?p2 yago:wasBornIn ?city. FILTER (?p1 != ?p2) g C1: SELECT DISTINCT ?name1 ?name2 WHERE f ?p1 yago:hasFamilyName ?name1. ?p2 yago:hasFamilyName ?name2. ?p1 rdf:type ?scientist. ?p2 rdf:type ?scientist. ?scientist rdfs:label "scientist". ?p1 ?c ?city. ?p2 ?c2 ?city. ?city rdf:type ?cityType. ?cityType rdfs:label "city". g C2: SELECT DISTINCT ?name WHERE f ?p yago:hasPreferredName ?name. ?p ?any1 ?c1. ?p ?any2 ?c2. ?c1 rdf:type ?city . ?c2 rdf:type ?city2. ?city2 rdfs:label "city". ?city rdfs:label "city". ?c1 yago:isCalled "London". ?c2 yago:isCalled "Paris". g C3: SELECT ?p1 ?predicate ?p2 WHERE f ?p1 ?anypredicate1 ?city1. ?city1 yago:isCalled "Paris". ?p1 ?predicate ?p2. ?p2 ?anypredicate2 ?city2. ?city2 yago:isCalled "Hong Kong". g
Kriterien für Datenpersistenz bei Enterprise Data Warehouse Systemen auf In-Memory Datenbanken Otto-von-Guericke-Universität Magdeburg
Kanalstraße 18
D-22085 Hamburg +49(0)160/90819410 ABSTRACT Persistente Datenhaltung über mehrere Schichten innerhalb eines Enterprise Data Warehouse Systems ist notwendig, um den dort vorhandenen, sehr großen Datenbestand nutzen zu können, z.B. für Reporting und Analyse. Die Pflege und Wartung solcher meist redundanten Daten ist jedoch sehr komplex und erfordert einen hohen Aufwand an Zeit und Ressourcen. Neueste In-MemoryTechnologien ermöglichen gute Performanz beim Datenzugriff, so dass sich die Frage stellt, welche Daten aus welchem Grund bzw. für welchen Zweck überhaupt noch persistent abgelegt werden müssen – und wie sich dies effizient entscheiden lässt. In diesem Papier präsentieren wir eine Übersicht von Gründen für Datenpersistenz, welche als Entscheidungsgrundlage bei der Problematik dient, Daten in Enterprise Data Warehouses auf InMemory Datenbanken zu speichern.
Kategorien und Themenbeschreibung H.2.7 [Database Management]: Datenbank-Administration – Data Warehouse und Repository.
Allgemeine Begriffe Management, Design.
Schlüsselwörter
Enterprise Data Warehouse, Persistenz, In-Memory Datenbank.
1. EINLEITUNG
Heutige Data Warehouse Systeme (DWS) sind gekennzeichnet
durch sehr große Datenvolumina [
Copyright is held by the author/owner(s). Otto-von-Guericke-Universität Magdeburg
Universitätsplatz 2 D-39106 Magdeburg +49(0)391/67-19351 Die Verbesserung der Datenzugriffsgeschwindigkeit ist oftmals der Hauptgrund zusätzlicher Datenhaltung. Setzt man voraus, dass dies in einer IMDB weniger wichtig ist, so kommt die Frage auf: Wieviel Persistenz, d.h. nicht-flüchtige Datenspeicherung, ist in IMDB-basierten DWS überhaupt noch notwendig? Dies gilt insbesondere für Enterprise Data Warehouses (EDW). Ist es möglich, jede Art von Analyseanfrage direkt auf dem Rohdatenbestand abzusetzen, welcher „on-the-fly“ transformiert wird? Oder gibt es dennoch gewichtige Gründe der Datenspeicherung? Um diese Fragen zu beantworten, erläutern wir Persistenzgründe in EDW-Systemen und potentielle Konflikte zwischen Datenspeicherung und -verwendung. Zudem definieren wir Indikatoren zur Entscheidungsunterstüzung, ob Daten gespeichert werden sollen oder nicht.
Abschnitt 2 erläutert einführend die Besonderheiten von
Enterprise Data Warehouses und einer Schichtenarchitektur. In
Abschnitt 3 führen wir Gründe der Datenpersistenz in heutigen
EDW auf und beschreiben mögliche Konflikte, welche aufgrund
der Anforderungen der Datennutzung und der hierfür
notwendigen Aufwände entstehen. Abschnitt 4 erläutert
Datenpersistenz auf IMDB-basierten EDW sowie
entscheidungsunterstützende Faktoren. Abschnitt 5 fasst die Teile
zusammen und gibt einem Ausblick auf zukünftige Arbeiten.
2. EINE SCHICHTENARCHITEKTUR FÜR
ENTERPRISE DATA WAREHOUSES
Ein Enterprise Data Warehouse ist ein Business Data Warehouse
[
ein umfassendes sensibler Daten
Gründe von
Persistenz in einem Data Warehouse ist eng verbunden mit dessen
Architektur. Eine allgemeine Referenzarchitektur (vgl. z.B.
[
Abb. 1. Schichtenarchitektur für EDW (nach [
Innerhalb der Qualitäts- & Harmonisierungschicht werden die
Daten technisch und semantisch integriert. Das beinhaltet
Dublettenerkennung, Aspekte der Informationsintegration (vgl.
[
Die Datenverteilungsschicht enthält harmonisierte und integrierte Unternehmensdaten ohne betriebswirtschaftliche Logik und bildet somit die einheitliche Datenbasis für alle Anwendungen.
In der Betriebswirtschaftlichen Modellierungsschicht werden Daten hinsichtlich der Geschäftsanforderungen transformiert; zum Beispiel werden Finanz- mit Logistikdaten verknüpft.
In der Berichts- & Analyseschicht werden Daten hauptsächlich verwendungsbezogen transformiert, um performante Zugriffe zum Beispiel beim Reporting oder der Analyse zu gewährleisten.
Innerhalb der Operationalen Datenversorgung werden Daten für sehr spezielle Anwendungsfälle und Anforderungen zur Verfügung gestellt, zum Beispiel bei „near real-time Reporting“.
Obwohl die Grenzen fliessend sind, können die fünf Schichten den drei Bereichen der Datenverarbeitung wie folgt zugeordnet werden: Datenbeschaffung in der Datenempfangs- und der Qualitäts- & Harmonisierungsschicht, Datenbearbeitung in der Datenverteilungs- und der Betriebswirtschaflichen Modellierungsschicht, sowie Datenbereitstellung in den Data Marts der Berichts- & Analyseschicht. 3. GRÜNDE FÜR DATENPERSISTENZ Zwei Gründe von Datenpersistenz im Data Warehouse werden hauptsächlich genannt: Speicherung der bereits transformierten Daten in der Basisdatenbank und Speicherung redundanter, aggregierter Daten im Data-Mart-Bereich. Darüber hinaus gibt es allerdings noch eine Vielzahl von Persistenzgründen im EDW.
Hierzu zählen technische Einschränkungen, GovernanceBestimmungen des Unternehmens und Gesetze, Vereinfachung der Datenhandhabung oder ein subjektives Sicherheitsbedürfnis.
Sofern uns bekannt, werden Gründe für Datenpersistenz in der Literatur nur selten erwähnt; zudem vermissen wir eine vollständige Auflistung, wie im Folgenden beschrieben.
Entkopplung des Quellsystems: Zur Entlastung des Quellsystems werden Daten direkt nach ihrer erfolgreichen Extraktion im Eingangsbereich des DW gespeichert; hierbei werden die Daten nicht oder nur in geringem Maße verändert (z.B. werden Herkunftsmerkmal oder Zeitstempel angefügt).
Datenverfügbarkeit: Oftmals sind Daten nicht mehr oder nur in einem veränderten Zustand verfügbar; hierzu zählen z.B. Daten aus dem Internet, aus Dateien, welche regelmäßig überschrieben werden, oder aus Altsystemen. Zudem können Netzwerkprobleme dazu führen, dass auf Daten nicht zugegriffen werden kann. Die Speicherung im Warehouse garantiert die Datenverfügbarkeit.
Komplexe Transformationen: Aufgrund ihrer Komplexität sind einige Transformationen sehr zeit- und ressourcenaufwendig, so dass die Daten gespeichert werden, um ein wiederholtes Transformieren zu vermeiden.
Abhängige Transformationen: Unter „abhängige Transformation“ verstehen wir solche, deren Durchführung den Zugriff auf weitere Daten erfordert; z.B. erfordert die Verteilung eines Bonus‘ auf die einzelnen Mitarbeiter die Gesamtanzahl der Mitarbeiter. Diese notwendigen Daten werden im DW gespeichert, um das korrekte Durchlaufen der Transformation zu gewährleisten.
Veränderte Transformationsregeln: Regeln können geändert werden. Besitzen die Daten kein Zeitmerkmal und werden die Transformationen nicht „historisiert“, so ist eine identische Transformation nicht mehr möglich.
Aufwendige Datenwiederherstellung: Sind Daten nicht mehr im DWS verfügbar (z.B. weil sie archiviert sind), ist eine Wiederherstellung aufwendig, so dass sie gespeichert werden.
Datenzugriffsgeschwindigkeit: Die redundante Speicherung von Daten in Verdichtungsebenen oder materialisierten Sichten zum Zwecke der Performanzverbesserung beim Datenzugriff stellt einen der häufigsten Gründe für die Einführung einer weiteren Persistenzebene dar. „En-bloc Datenversorgung“: Üblicherweise fliessen neue Daten, aus verschiedenen, gegebenenfalls weltweiten Quellen, zeitlich verteilt in ein EDW. Nachdem diese syntaktisch und semantisch integiert wurden, werden sie zwischengespeichert und erst zu einem bestimmten Zeitpunkt in die Datenbasis des Warehouse gespielt. Hierdurch wird ein zeitlich definierter, konstanter und in sich plausibler Datenbestand für die darauf aufsetzenden Anwendungen gewährleistet.
Konstante Datenbasis: Einige, auf Daten des DWS aufbauende
Applikationen, wie beispielsweise Planung, erfordern eine
konstante Datenbasis, welche sich während der Benutzung nicht
ändern darf und deswegen separiert gespeichert wird.
„Single Version of Truth“: Transformierte Daten werden nach
unternehmensweit gültigen Definitionen, aber ohne spezielle
Geschäftslogik gespeichert. Hierdurch wird ein einheitlicher,
vergleichbarer Datenbestand geschaffen, auf den die jeweiligen
Geschäftsbereiche und Anwendungen zugreifen können [
Komplex-abweichende Daten: Zu integrierende Daten können in Syntax und Semantik sehr von der im EDW üblichen abweichen; eine (zumeist schrittweise) Eingliederung erfolgt erst nach vorheriger Speicherung.
Data-Lineage: Daten in Berichten oder Analysen sind häufig
Ergebnis mehrstufiger Transformationsprozesse. Um eine
Rückverfolgung zu den Urprungsdaten zu erleichtern oder zu
ermöglichen, etwa zur Validierung, können gespeicherte
Zwischenergebnisse erforderlich sein (vgl. [
Komplexe Berechtigungen: Anstatt der Definition und Erstellung komplexer Benutzerberechtigungen (z.B. auf Merkmale oder auf Feldinhalte), werden bestimmte Data-Marts mit den Daten erstellt und die Berechtigungen auf dem Data-Mart vergeben. „Informationsgewährleistung”: Viele EDW haben zu gewährleisten, dass die Daten den Benutzern in einem bestimmten Zeitraum (oftmals sogar 24 Stunden pro Tag) zur Verfügung stehen und für die Anwendungen genutzt werden können. Hierfür werden in der Regel besonders kritische Datenbestände zusätzlich gespeichert.
Corporate Governance: Daten werden gemäß den ComplianceVorgaben des jeweiligen Unternehmens (Corporate Governance) gespeichert; z.B., um eine aufgrund bestimmter Daten getroffene Managemententscheidung auch im Nachhinein beurteilen zu können.
Gesetze und Bestimmungen: Zudem gibt es auch Gesetze und
Bestimmungen, die eine Datenspeicherung begründen; für
Deutschland existieren solche beispielsweise im Finanzbereich
(Handelsgesetzbuch u.a., [
Subjektive Sicherheit: Letzlich kann das sujektive Bedürfnis an Sicherheit ein Grund für Datenspeicherung sein.
Persistenz beinhaltet häufig redundante Datenhaltung, da sowohl Quell- als auch transformierte Zieldaten gespeichert werden; ausschließliches Speichern der Zieldaten bedeutet in aller Regel Datenverlust. Hieraus entstehen hohe Anforderungen, nicht nur an die Hardware (Speicherplatz etc.), sondern auch an die Datenpflege, um etwa die Datenbestände konsistent zu halten.
Der Betrieb produktiver DWS führt zwangsläufig zu Konflikten zwischen den Anforderungen der Datennutzung, wie z.B.
Performanz bei Reporting und Analyse, und dem Aufwand an Zeit und Ressourcen, die notwendigen Voraussetzungen hierfür zu schaffen. Im Folgenden beschreiben wir diese Anforderungen und ihre Konsequenzen kurz.
Wie bereits erwähnt, stellt ein EDW häufig die Datenbasis für verschiedene Anwendungen dar; das hohe Datenvolumen resultiert aus den unterschiedlichen Anforderungen dieser Applikationen an die Daten. Der Bedarf an Detailinformationen erfordert viele Daten feinster Granularität. Der Bedarf an historischen Informationen erfordert eine lange Historisierung der Daten. Schließlich wird eine große Bandbreite an Daten gesammelt, beispielsweise für Data-Mining-Szenarios. Dieser große Datenbestand muss für seine Verwendung aufbereitet werden; z.B. ist eine gute Berichtsperformanz sicherzustellen.
Eine hohe Geschwindigkeit beim Datenzugriff wird zumeist durch
ein reduziertes Datenvolumen erreicht – durch den Aufbau
materialisierter Sichten oder Verdichtungsebenen. Ein einfaches
Beispiel hierfür ist die Verdichtung tagesgenauer Daten auf
Monat, mit einem Faktor von etwa 30. Pflege und Verwaltung
solcher Redundanzen erfordert nicht nur Speicherplatz, sondern
auch zusätzlichen Aufwand, die Daten aktuell und konsistent zu
halten (vgl. [
Ein komplexer Staging-Prozess mit mehreren Schichten
persistenter Daten ist einer schnellen Datenverfügbarkeit
gegensätzlich. Dies ist insbesondere auch bei Konzepten für
„Near-Realtime Reporting“ zu beachten [
Solche Modelle ermöglichen gute Performanz bei On-line Analytical Processing. Große Datenbestände müssen aber auch hier mittels materialisierter Sichten und Verdichtungsebenen reduziert werden – mit den bereits beschriebenen Konsequenzen.
Spaltenbasierte Datenbanken (vgl. [
Es wurden bereits Installationen angekündigt, die On-Line
Transactional und Analytical Processing in einem System mit bis
zu 50 TB Daten im Hauptspeicher ermöglichen [27]. In diesem
Bereich ist SanssouciDB als ein erstes Produkt zu nennen [
Diese technologischen Veränderungen führen zu der Frage, in welchem Maße Datenpersistenz in IMDB-basierten EDWSystemen noch notwendig ist. Es wird suggeriert, dass bei InMemory-Technologie keine Daten zusätzlich zu den gespeicherten Urspungsdaten persistent gehalten werden müssen.
Alle abgeleiteten Daten, insbesondere die für Analysezwecke
aggregierten oder verdichteten, werden „on-the-fly“ ermittelt und
zur Verfügung gestellt [
Tab. 1. Persistenzgründe, nach Notwendigkeit gruppiert Subjektive Sicherheit
Unterstützend Verpflichtend zu speichern sind Daten aufgrund von Gesetzen und Bestimmungen sowie Regeln der Corporate Governance. Zudem gilt dies für Daten, welche nicht wieder hergestellt werden können, weil sie nicht mehr oder nur verändert zur Verfügung stehen oder aufgrund geänderter Transformation nicht mehr erstellt werden können. Auch Daten, die bei der Transformation anderer Daten benötigt werden, sind zu speichern, wenn eine gleichzeitige Verfügbarkeit nicht gewährleistet werden kann.
Essentielle Datenpersistenz kann in bestimmte Gruppen unterteilt werden: Zum einen Daten, deren Wiederherstellung nur mit sehr hohem Aufwand (an Zeit und Ressourcen) möglich ist, wie z.B. archivierte oder komplex transformierte Daten. Hierbei ist „sehr hoch“ allerdings subjektiv und näher zu untersuchen. Eine zweite Abhängige Transformationen
Verpflichtend
Grund/Zweck Gesetze und Bestimmungen
Veränderte
Transformationsregeln Quellsystem-Entkopplung
Aufwendige
Datenwiederherstellung “En-bloc Datenversorgung” „Single Version of Truth“ „Corporate Data Memory“ „Informationsgewähr” Zugriffsgeschwindigkeit
Notwendigk.
Verpflichtend Verpflichtend Verpflichtend Verpflichtend
Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Essentiell Aufwand Aufwand Aufwand
Aufwand Vereinfachung Vereinfachung Vereinfachung Vereinfachung
Design
Design Sicherheit Performanz
Gruppe sind Daten, die gespeichert werden, um den Betrieb des Warehouse oder einzelner Anwendungen zu vereinfachen; hierzu zählen speziell abgelegte Plandaten oder Data-Marts mit Berechtigungen für besondere Benutzer. Drittens begründet sich Persistenz mit spezieller Konzeption (Design) des EDW: „Single Version of Truth“, „Corporate Data Memory“ zählen u.a. hierzu.
Sicherheit, etwa zur Gewährleistung der Datenverfügbarkeit, stellt eine weitere Gruppe dar. Letztlich ist Datenspeicherung für eine hohe Performanz ein Grund; oftmals der, dem das größte redundante Datenvolumen zugrunde liegt.
Daten, deren Speicherung unterstützend ist, beinhalten solche, die wegen subjektiver Sicherheitsüberlegungen abgelegt werden.
Eine komplette Auflistung der Persistenzgründe, gruppiert nach Notwendigkeiten, zeigt Tab. 1.
Abb. 2 zeigt ein vereinfachtes Entscheidungsdiagramm für Datenpersistenz, in dem z.B. unscharfe Begriffe wie „aufwendig“, „komplex“ und „häufig“ abhängig von der Domäne spezifiziert werden müssen. Die ersten drei Abfragen betreffen verpflichtende Gründe, d.h. die Daten sind – auch in IMDB-basierten EDW – zu speichern. Bei den aus anderen Gründen gespeicherten Daten sind die Entscheidungsgrundlagen sehr vielfältig. Stellen die Daten eine „Single Version of Truth“ dar oder umfasst das EDW-Design ein „Corporate Data Memory”, so sind diese Daten zu speichern.
Ist hingegen eine komplexe Reproduktion oder Transformation Grund des Speicherns, so müssen z.B. Zugriffshäufigkeit und Sicherstellung der Verfügbarkeit in Betracht gezogen werden, um entscheiden zu können.
Abb. 2. Entscheidungsdiagramm „Datenpersistenz“ 4.2 Bewertung der Persistenz in IMDBs Alle nicht-verpflichtend gespeicherten Daten sind Gegenstand der Betrachtung bei der Frage nach Persistenz in IMDB-basierten EDW. Insbesondere betrifft dies Daten, die zur Verbesserung der Zugriffsperformanz oder aufgrund komplexer Transformation redundant abgelegt werden. Das bedeutet aber nicht, dass allein die Geschwindigkeit der Datenverarbeitung in einem solchen System jede Art zusätzlicher Speicherung überflüssig machen wird. Dies gilt beispielsweise für die „En-bloc Datenversorgung“ oder beim Aufbau einer konstanten Datenbasis für Planungsläufe.
IMDB-Snapshot-Mechanismen, wie in [30] erläutert, halten den Datenbestand zumeist nicht über die benötigte Zeit von Stunden oder Tagen konstant. Hier kommt es nicht auf eine schnelle Versorgung mit neuen Daten an, sondern auf die Herstellung eines über einen definierten Zeitraum unveränderten Datenbestands.
Zeitstempelverfahren in In-Memory-Konzepten [
Die Erfahrung zeigt, dass technische Beschränkungen meist früher als erwartet eintreten, so dass die Systemressourcen für die an sie gestellten Aufgaben nicht mehr ausreichen werden. Die Möglichkeit, auf sehr viele Daten mit sehr hoher Performanz zuzugreifen, wird neue Bedürfnisse wecken. Es werden neue Anforderungen aufkommen und die Datenmengen zunehmen.
Aufgrund dessen ist auch bei IMDB-basierten Systemen zu betrachten, ob wiederholte, gleichartige Zugriffe und Bearbeitung von Daten „on-the-fly“ nicht durch Vorhalten der Daten im benötigten Format günstiger ist. Dies gilt insbesondere für Datenbestände, auf die häufig zugegriffen wird und die sich nicht oder nur wenig ändern, wie beispielsweise die geschlossenen Jahres-, Quartals- oder Monatsabschlüsse der Finanzbuchhaltung.
Eine weitere Frage in diesem Zusammenhang ist das Datenformat, in dem gespeichert wird, d.h. auf welcher Transformationsstufe die Speicherung optimal ist. Hierbei ist das Format zu ermitteln, welches eine möglichst flexible Verwendung der Daten bei einer größtmöglichen Vermeidung wiederholter, gleichartiger Transformationen darstellt. Dies kann durch kostenbasierte Laufzeitmessungen geschehen, wie folgendes Beispiel erläutert: Gegeben sei ein Rohdatenbestand (R), der über eine mehrstufige Transformation (Tn; n={1,2,3}) für Analysen (A) abgefragt wird.
Zu vergleichen ist, ob es effizienter ist, die Daten nach den einzelnen Transformationen persistent zu speichern (P), sie volatil zu halten (V), oder sie jeweils „on-the-fly” neu zu ermitteln: (1) R (2) R (3) R (4) R (5) R
T1 + P T1 + P T1 + P T1 + V T1
T2
T2 + P T2 + V T2 T2
T3 + A
T3 + A T3 + A
T3 + A
T3 + A für die Konsistenzsicherung der abgeleiteten Verdichtungsebenen, geringer ist als der Geschwindigkeitsgewinn der Anwendung? Und: Wie aufwendig sind diese Änderungen? Untersuchungen dieser Art sind auch bei RDBMS-basierten DWS valide. Hierbei lässt die Leistungsfähigkeit einer IMDB jedoch als Ergebnis erwarten, dass Transformationen eher „on-the-fly“ als mit redundanter Persistenz durchgeführt werden.
Einige IMDB ermöglichen die Festlegung unterschiedlicher Kriterien zur Dauerhaftigkeit, z.B. durch Definition temporärer Tabellen [29,30]. Hierdurch können Daten, die nicht verpflichtend zu speichern sind, nur in flüchtigem Speicher gehalten werden. Da ein Herunterfahren oder Absturz der Datenbank relativ selten geschieht, sind die Wartungskosten für solche Daten gering. Ein beispielhafter Anwendungsfall hierfür ist die Ermittlung von RFM-Attributen (Recency, Frequency, Monetary) zur Kundenkategorisierung im CRM-Umfeld [31]. Die Emittlung (s.
Abb. 3) basiert auf Kundenstamm- und Transaktionsdaten (Kassenbons, Aufträge, Fakturen) und umfasst Selektionen, Kalkulationen, Währungsumrechnungen, Look-Ups zu komplexen Steuerungsdaten etc. Die berechneten Attribute werden zeitnah aktualisiert benötigt, sowohl im DWS, als auch im CRM-System.
Zu berücksichtigen ist, dass es sich hierbei um oft sehr große Mengen an Daten handelt, mehrere Millionen Kunden mit jeweils einer zweistelligen Anzahl Transaktionen. Diese Datenbestände ändern sich häufig, so dass auch die RFM-Attribute laufend aktualisiert werden müssen. Da die Ermittlung der Attribute reproduzierbar ist, kann das Vorhalten dieser Daten ausschließlich im flüchtigen Speicher einer Persistierung vorzuziehen sein.
Abb. 3. Ermittlung von RFM-Attributen Festzuhalten bleibt, dass in einem IMDB-basierten EDW viele Daten nicht mehr gespeichert werden müssen, die in einem RDBMS-basierten aufgrund von Performanzgewinn redundant zu halten sind. Höhere Zugriffsgeschwindigkeiten werden es ermöglichen, Daten „on-the-fly“ für die Nutzung aufzubereiten, insbesondere solche mit relativ einfacher Transformationslogik, wie z.B. Aggregation, Joins etc. Eine Vielzahl materialisierter Sichten wird zu virtuellen Sichten. 5. FAZIT UND AUSBLICK Enterprise Data Warehouses sind komplexe Systeme mit speziellen Anforderungen an Datenbestand und Datenhaltung, für die eine Architektur dedizierter, zweckbestimmter Schichten geeignet ist. Die Notwendigkeit von Datenpersistenz in solchen Systemen kann nur durch den Zweck der Daten begründet werden. Diese Sichtweise wird bei IMDB-basierten EDW noch entscheidender. Wir beschreiben Gründe der Datenpersistenz und unterteilen sie in verpflichtende, essentielle und unterstützende.
Darauf aufbauend nähern wir uns der Entscheidungsfindung, ob Daten in solchen Systemen gespeichert werden.
Persistente Datenhaltung wird es auch in EDW-Systemen auf IMDB geben. Ein großer Anteil heutiger persistierter Daten wird allerdings nur flüchtig gespeichert oder „on-the-fly“ berechnet.
Zudem wird die Frage aufkommen nach dem Format, in dem die Daten abgelegt werden. Die Antwort hierauf wird nicht einfach zu ermitteln sein; es handelt sich hierbei vielmehr um eine multidimensionale Gewichtung verschiedener Faktoren, wie: Aufwand für Transformation, Speicherung und Updating, Anzahl und Zeit von Datenabfrage und -aktualisierung.
Zukünftige Arbeiten werden eine detaillierte Aufstellung von Persistenzgründen mit ausführlichen Beispielen umfassen.
Darüber hinaus werden Indikatoren definiert und beschrieben
werden, die die Entscheidungsfindung für/gegen Datenpersistenz
unterstützen. Dies umfasst sowohl messbare, wie beispielsweise
Vergleiche von Laufzeiten und Wartungsaufwänden zwischen
Datenbeständen in verschiedenen Speicherzuständen, als auch
nicht-messbare Indikatoren. So wird ermittelt, ob Entscheidungen
durch Berechnungen getroffen oder hierdurch zumindest
unterstützt werden können.
6. DANKSAGUNG
Diese Arbeit wird teilweise unterstützt vom Bundesministerium
für Bildung und Forschung (BMBF) innerhalb des
ViERforES-IIProjekts (Nr. 01IM10002B).
[
01.03.2011); §147 AO (Stand: 08.12.2010).
[
Systeme“; dpunkt-Verlag, Heidelberg; 2003. [26] ParAccel: „PARACCEL ANALYTIC DATABASETM“; www.paraccel.com/wp-content/uploads/2010/07/PA_DS.pdf {03.05.2011}; 2011. [27] H. Plattner: „A Common Database Approach for OLTP and
OLAP Using an In-Memory Column Database”; in:
SIGMOD`09, S. 1-2; 2009. [28] IBM: IBM solidDBTM; www.ibm.com/software/data/soliddb
{03.05.2011}; 2010. [29] Oracle: „Extreme Performance Using Oracle TimesTen In
Memory Database”; www.oracle.com/technetwork/database/ timesten/overview/wp-timesten-tech-132016.pdf {03.05.2011}; 2009. [30] A. Kemper, T. Neumann: „HyPer: Hybrid OLTP&OLAP
High PERformance Database System“; www3.in.tum.de/research/projects/HyPer/HyperTechReport.
pdf {03.05.2011}; 2010. [31] J. Stafford: „RFM: A Precursor of Data Mining”;
www.b-eye-network.com/view/10256 {03.05.2011}; 2009 Ein Verfahren zur automatischen Erstellung eines visuellen Wörterbuchs für die Bildsuche
Magdalena Rischka
Institut für Informatik Heinrich-Heine-Universität Düsseldorf
D-40225 Düsseldorf, Deutschland rischka@cs.uni-duesseldorf.de ZUSAMMENFASSUNG Das Internet bietet eine enorme Anzahl an Bildern. Bildsuchmaschinen stehen vor der Herausforderung Bilder e ektiv und e zient zu erschlie en. Die klassischen Arten der Bildsuche, die stichwort- und die inhaltsbasierte Bildsuche, haben Nachteile. Ein Retrieval-Modell, welches die Vorteile beider Sucharten integriert und die Nachteile ausschlie t, ist die auf einem visuellen Worterbuch basierende Bildsuche.
Ein visuelles Worterbuch ist dabei eine Menge von Stichwortzu-visueller-Beschreibung Beziehungen. Wir prasentieren ein Verfahren zur automatischen Erstellung eines visuellen Worterbuchs aus einer Trainingsmenge von annotierten Bildern.
Dabei werden verschiedene Modelle von visuellen Beschreibungen untersucht und anschlie end evaluiert. Wir zeigen, dass eine kompakte visuelle Beschreibung existiert, die verglichen mit multiple-Instanzen visuellen Beschreibungen bessere Retrieval-Ergebnisse liefert und gleichzeitig die Anfragezeit drastisch senkt.
Schlüsselwörter image search, visual dictionary, visual words, visual phrases
Das heutige World Wide Web stellt einen gro en und standig wachsenden Datenbestand von Bildern dar und bildet somit eine gute Basis fur die Suche nach gewunschten Bildern. Es gibt zwei klassische Arten der Bildsuche: die stichwortbasierte und die inhaltsbasierte Bildsuche. Die stichwortbasierte Bildsuche basiert auf Annotationen und Metadaten der Bilder. Die Anfrageformulierung erfolgt textuell, somit schnell und unkompliziert. Bei der Verarbeitung der Anfrage sucht das System nach Bildern, die, grob gesagt, die Stichworter aus der Anfrage beinhalten. Einen Nachteil hat diese Suchart jedoch: der Erfolg der Suche hangt von der Qualitat der Annotationen und Metadaten der Bilder ab.
Je nachdem, ob Bilder manuell vom Benutzer oder automatisch mit Hilfe eines Algorithmus annotiert wurden, weisen diese unterschiedliche Schwachen auf, z.B. die Subjektivitat des Beschreibenden, abstrakte Formulierungen oder falsche Stichwortzuordnungen, sowie Unvollstandigkeit der Beschreibung. Aufgrund dieses Nachteils versucht man heutzutage, fern von den Annotationen, auf das Bild selbst einzugehen und somit den Inhalt des Bildes zu erschlie en. Die inhaltsbasierte Bildsuche basiert demnach auf visuellen Eigenschaften des Bildes, z.B. bzgl. der Farbe, der Textur, Form usw. Eine Anfrage wird mittels einem Beispielbild gestellt, das Retrieval-System sucht dann nach Bildern, die dem Anfragebild ahnlich sind, bezogen auf den, dem System zugrundeliegenden Deskriptor und das A hnlichkeitsma . Der Nachteil dieser Suchart betri t die Anfrageformulierung mittels dem Anfragebild - ein Anfragebild liegt dem Benutzer in der Regel nicht vor, dieses wird schlie lich gesucht. Gewunscht ist daher ein Retrieval-System, welches die Vorteile beider Sucharten integriert, d.h. eine textuelle Anfrageformulierung mit einer inhaltsbasierten Bildsuche kombiniert.
Eine Losung ist das Modell des visuellen Worterbuchs als eine Menge von Stichwort-zu-visueller-Beschreibung Beziehungen. Bei der Bildsuche auf der Basis des visuellen Worterbuchs wird nun eine Anfrage textuell gestellt, dann die Stichworter aus der Anfrage in dem visuellen Worterbuch nachgeschlagen und deren U bersetzung, d.h. eine visuelle Beschreibung des Stichwortes, fur die anschlie ende inhaltsbasierte Bildsuche verwendet. Die Entwicklung eines Verfahrens zur automatischen Erstellung eines visuellen Worterbuchs ist Gegenstand dieses Papers. Wir geben zunachst einen U berblick uber verwandte Arbeiten, beschreiben dann das entwickelte Verfahren, evaluieren visuelle Beschreibungen und schlie en mit einer Schlussfolgerung und einem Ausblick.
VERWANDTE ARBEITEN
In der Literatur existieren zwei weitverbreitete De
nitionen des Begri s visuelles Worterbuch. Die erste De nition
beschreibt das Konzept der Zuordnungen von Stichwort zu
visueller Beschreibung, die zweite betri t die Quantisierung
des Deskriptor-Raums in Partitionen, sogenannte visuelle
Worter. Jeder Deskriptor wird dann mit seinem zugehorigen
visuellen Wort reprasentiert. Alle Partitionen bilden das
visuelle Worterbuch. Oft werden beide Konzepte kombiniert
[
DAS VERFAHREN ZUR ERSTELLUNG
EINES VISUELLEN WÖRTERBUCHS
In diesem Kapitel prasentieren wir das entwickelte Verfahren zur automatischen Erstellung eines visuellen Worterbuchs aus einer Trainingsmenge von annotierten Bildern.
Das Verfahren basiert auf der Idee, die Trainingsbilder einmal bzgl. der A hnlichkeit ihrer Annotationen und einmal bzgl. ihrer visuellen A hnlichkeit zu gruppieren, dann die Trainingsbilder, die bzgl. der beiden Aspekte zueinander ahnlich sind, d.h. bzgl. beider Aspekte zusammen gruppiert wurden, aufzusuchen und aus diesen schlie lich Korrelationen zwischen Stichwortern und visuellen Bildmerkmalen abzuleiten. 3.1
Anforderungen an das visuelle
Wörterbuch
Das visuelle Worterbuch kann man sich wie ein herkommliches Worterbuch vorstellen, welches aus einer Menge von Eintragen besteht. In dem visuellen Worterbuch sollen Objekte und visuelle Zusammenhange, wie z.B. Tiere, Gegenstande, Gebaude, Logos, Symbole, etc. verwaltet werden. Jeder Eintrag ist ein Paar aus einem Stichwort, der das Objekt benennt und einer dazugehorigen visuellen Beschreibung des Objektes. Stichworter sollen in der Grundform vorliegen wir sprechen dann von Termen -, und es soll die Polysemie der Terme unterstutzt werden. Eine visuelle Beschreibung stellt eine Einheit dar, die fur die inhaltsbasierte Bildsuche verwendet wird. Diese soll nur die fur dieses Objekt relevanten visuellen Charakteristika erfassen, die allen Perspektiven und Erscheinungsformen des Objektes gemeinsam sind. Zudem soll diese aus E zienzgrunden kompakt, sowie zu der Reprasentation der Bilder kompatibel sein. 3.2
Das konzeptuelle Modell des Verfahrens
Das konzeptuelle Modell des Verfahrens ist in Abbildung 1 dargestellt. Grundlage zum Erlernen des visuellen Worterbuchs bildet die Trainingsmenge von annotierten Bildern, die beliebig und ohne zusatzliche Vorbearbeitung gewahlt werden kann. Ausgehend von dieser werden zunachst einmal zwei Ziele verfolgt: die Gruppierung von ahnlichen Bildern auf der Basis der semantischen A hnlichkeit ihrer Annotationen und die Gruppierung von ahnlichen Bildern bezuglich ihrer visuellen A hnlichkeit. Dazu werden die Annotationen sowie die Bilder unabhangig voneinander in eine interne Reprasentation uberfuhrt und auf der Basis eines de nierten A hnlichkeitsma es gruppiert. Aus den beiden Gruppierungen wird dann das visuelle Worterbuch erstellt. Dazu wird zunachst einmal das Vokabular fur das visuelle Worterbuch bestimmt. Fur jeden Term des Vokabulars werden Trainingsbilder ermittelt, die diesen Term in der Annotation enthalten und bzgl. der A hnlichkeit von Annotationen und der visuel
Trainingsmenge Annotationen Repräsentation & Ähnlichkeitsmaß
Bilder Repräsentation & Ähnlichkeitsmaß Abbildung 1: Das konzeptuelle Modell des Verfahrens len Bildmerkmale ahnlich sind. Es ndet also ein Abgleich der Gruppierungen statt. Aus den ermittelten Trainingsbildern eines Terms wird schlie lich die visuelle Beschreibung des Terms gelernt und zusammen mit dem Term als ein Eintrag in dem visuellen Worterbuch abgespeichert. Wir erhalten das visuelle Worterbuch aus Stichwort-zu-visuellerBeschreibung Eintragen.
Repräsentation und Ähnlichkeitsmaß von/ für Annotationen und Bilder
Fur einen semantischen Vergleich mussen Annotationen und Bilder in eine interne Darstellung uberfuhrt werden.
Wir bereiten auf und bereinigen zuerst die Annotationen, erstellen dann einen Index mit dem Indexvokabular und leiten daraus fur jede Annotation einen Annotationsvektor gema der tf-idf Gewichtung. Als A hnlichkeitsma wahlen wir das Kosinusma .
Als Grundlage fur die Reprasentation von Bildern
wahlen wir Scale Invariant Feature Transform (SIFT)[
Fur die Bestimmung der A hnlichkeit zweier Bilder verwenden wir ein A hnlichkeitsma , das auf dem Histogrammschnitt hs zweier Histogramme basiert: hs(nHistiX ; nHistjX ) = k X min(nHistiX [l]; nHistjX [l]) (3) l=1 wobei nHistX die normalisierte Version des absoluten Histogramms aHistX darstellt. Die A hnlichkeit zweier Bilder bi und bj ergibt sich dann mit: ahnlichkeit(bi; bj) = (1
) hs(nHistiV W ; nHistjV W ) (4)
hs(nHistiV P ; nHistjV P )
Fur den Wert des Gewichts orientieren wir uns an dem
Paper [
Gruppierung von Annotationen und von Bildern
Fur die Gruppierung der Annotationen wenden wir den
in [
Die Gruppierung von ahnlichen Bildern bedeutet, Bilder, die dasselbe Objekt beinhalten, in eine Gruppe zu fassen.
Da wir von nicht vorbearbeiteten Trainingsbildern ausgehen, liegen diese Bilder also in der Regel etwas "verschmutzt\ vor, d.h. sie beinhalten neben dem Hauptobjekt ggf. noch andere irrelevante Objekte oder einen Hintergrund. Dadurch kann es leicht zu dem Problem kommen, dass zwei Bilder, die wir intuitiv nicht gruppiert hatten, weil diese unterschiedliche Hauptobjekte haben, trotzdem einen hoheren A hnlichkeitswert haben, als zwei Bilder, die dem menschlichen Emp nden nach ahnlich sind. Bei der Wahl eines Gruppierungsverfahrens mussen wir diese Problematik einbeziehen. Clusteringverfahren, die die Trainingsbilder in Partitionen zerlegen, sind nicht geeignet, es konnte namlich passieren, dass Bilder aufgrund fur uns falsch erscheinenden Gemeinsamkeiten, wie dem Hintergrund, zusammengefasst und dann bzgl. des relevanten Objektes nicht mehr gruppiert werden. Am besten ware, man hatte visuelle Beschreibungen von den, in der Trainingsmenge enthaltenen Objekten und wurde diese als Clusterzentren nehmen, um die Trainingsbilder anhand dieser Clusterzentren uberlappend zu gruppieren. Die visuellen Beschreibungen sind aber genau das was wir suchen. Hatten wir solche Beschreibungen, dann ware die Gruppierung hier uber ussig. Man kann trotzdem versuchen solche visuellen Beschreibungen zu simulieren, indem man das was den Trainingsbildern gemeinsam ist, extrahiert. Sind zwei Bilder bzgl. einem Objekt ahnlich und teilen damit die Charakteristika des Objektes, dann mussen die gemeinsamen Charakteristika auch in der kompakten Bilddarstellung der visuellen Worter und der visuellen Phrasen verankert sein, namlich als Durchschnitt der visuellen Worter und visuellen Phrasen Histogramme der beteiligten Bilder. Der Durchschnitt ds zweier Bilder bi, bj ist wie folgt de niert: ds(bi; bj) = dsV W (bi; bj); dsV P (bi; bj)
dsX (bi; bj) = (m(1); :::; m(k)) m(l) = min(aHistiX [l]; aHistjX [l]) mit und wobei bei X = V W ist k = 1000 und X = V P ist k = 500:500. Fur die Gruppierung der Trainingsbilder berechnen wir die Durchschnitte der ahnlichsten Bilder, betrachten diese als Pseudo-Objekte und damit als Centroide, und clustern die Trainingsbilder gema einem Schwellwert uberlappend an diese Durchschnitte. Wir erhalten eine Menge von Gruppen visuell ahnlicher Bilder Glvisuell j 1 l ng . 3.5
Wahl des visuellen Wörterbuch
Vokabulars
Als nachstes mussen wir klaren, welche Stichworter in das visuelle Worterbuch aufgenommen werden. Als Stichworter kommen naturlich nur Terme aus dem Indexvokabular in Frage. Die U bernahme aller Terme als Stichworter ist jedoch nicht sinnvoll, denn nicht alle Terme bzw. die den Termen zugrundeliegenden Worter beschreiben Objekte oder beinhalten einen visuellen Aspekt. Wir betrachten daher die Gruppen, die wir durch das Clustering von Annotationen erhalten haben. Wir nehmen an, dass innerhalb einer Annotationsgruppe die Terme, die in den meisten Annotationen vorkommen, etwas mit dem visuellen Inhalt der zugehorigen Bilder zu tun haben mussen. Fur jede Annotationsgruppe werden daher diese hochfrequenten Terme bestimmt. Dazu wird zunachst der Term mit der hochsten Annotationshau
gkeit ermittelt und dann noch weitere, deren Annotationshau gkeit gro er ist als 0:7 mal die maximale Hau gkeit.
Die Vereinigung der so erhaltenen Terme bildet dann das Vokabular des visuellen Worterbuchs, also im Grunde die Eintrage. Um die Forderung nach der Unterstutzung der Polysemie von Termen zu realisieren, werden die betro enen Terme mehrmals, nur mit unterschiedlichem Kontext, in dem visuellen Worterbuch aufgefuhrt. Der jeweilige Kontext eines Terms ergibt sich aus der Gruppe, genauer aus den anderen Termen der Gruppe, zu der der Term gehort.
Als Kontext wird der Centroid der Gruppe verwendet. Wir erhalten somit eine Seite des visuellen Worterbuchs, namlich eine Menge von Eintragen, die jeweils ein Objekt reprasentieren und aus einem Term und seinem Kontextvektor bestehen.
Abgleich der Gruppierungen
Fur jeden Eintrag des visuellen Worterbuchs muss nun eine Menge von Trainingsbildern bestimmt werden, aus der die visuelle Beschreibung des Terms gelernt werden soll. Das bedeutet, es mussen die Bilder bestimmt werden, die sowohl bzgl. des Terms als auch visuell bzgl. des beinhaltenden Objekts ahnlich sind. Dazu werden Bilder, die diesen Term in der Annotation enthalten, aus der Annotationsgruppe des Terms genommen und es wird daraus eine Gruppe Geintrag gebildet. Diese Gruppe wird dann mit jeder Gruppe Glvisuell visuell ahnlicher Bilder abgeglichen. Beim Abgleich wird der Mengendurchschnitt jeweils zweier Gruppen gebildet, indem die Bilder ubernommen werden, die in der Gruppe Geintrag und in der Gruppe Glvisuell vorkommen. Der resultierende Mengendurchschnitt zweier Gruppen muss mindestens zwei Bilder beinhalten, sonst konnen keine gemeinsamen Charakteristika gelernt werden. Als Resultat des Abgleichs erhalten wir wiederum, ggf. uberlappende, Gruppen von Bildern. Die Bilder innerhalb einer solchen Gruppe sind nun visuell als auch bzgl. des Terms und seinem Kontext ahnlich. Jeder Eintrag des visuellen Worterbuchs besteht nun aus einem Term, seinem Kontextvektor und der Menge der Bildgruppen aus welcher eine visuelle Beschreibung im nachsten Schritt hergeleitet wird. 3.7
Als nachstes muss die rechte Seite des visuellen Worterbuchs, die Seite der visuellen Beschreibungen, bestimmt werden. Wir betrachten einen Eintrag, also einen Term, des visuellen Worterbuchs und die ihm zugehorige, im letzten Abschnitt bestimmte Menge von Bildgruppen. Es gibt mehrere Moglichkeiten aus der Menge der Bildgruppen eine visuelle Beschreibung abzuleiten. Im Folgenden stellen wir einige Arten von visuellen Beschreibungen in der Reihenfolge der eigenen Entwicklung und Untersuchung vor. 3.7.1
Die erste und einfachste Methode eine visuelle Beschreibung anzugeben ist, die Bildgruppen zu vereinigen und die so erhaltene Menge an Trainingsbildern als Reprasentation des Terms zu verwenden. Bei der Bildsuche zu diesem Term
nden dann mehrere inhaltsbasierte Bildsuchen statt, indem jedes dieser Trainingsbilder als Anfragebild verwendet wird.
Bei dieser multiple-Instanzen visuellen Beschreibung erhalten wir jedoch zunachst fur jedes Anfragebild ein Ranking von Bildern als Ergebnis. Es stellt sich also die Frage, wie das Endergebnis aus den Ergebnissen der einzelnen Anfragen berechnet werden soll. Fur die Angabe des Endergebnisses werden drei Strategien untersucht.
Bei der ersten Strategie wird das beste Resultat als Endergebnis ausgegeben. Dazu wird die Gute der einzelnen Ergebnisse mittels einem Qualitatsma berechnet. Eine solche Berechnung erfordert allerdings zu wissen, welche Bilder des Ergebnisrankings fur den Anfrageterm relevant und welche irrelevant sind. Dafur mussten die Bilder in der Bilddatenbank kategorisiert oder mit Termen versehen sein. Von diesem Fall kann man in der Realitat jedoch nicht ausgehen. Diese Strategie ist auf einer Bilddatenbank also praktisch nicht anwendbar, lediglich auf einer vorbereiteten Testmenge. Aus Grunden des Performance Vergleichs wird diese trotzdem aufgefuhrt und untersucht. (AlleBilder-BesterScore)
Jedes Bild aus der Bilddatenbank hat fur jedes Anfragebild der visuellen Beschreibung, also in jedem der einzelnen Ergebnisse, eine Rankingposition und einen A hnlichkeitswert zum Anfragebild. Bei der zweiten Strategie wird fur jedes Bild aus der Bilddatenbank der maximale A hnlichkeitswert aus seinen A hnlichkeitswerten zu allen Anfragebildern ausgewahlt, die Bilder dann entsprechend ihrem maximalen A hnlichkeitswert sortiert und als Endergebnis ausgegeben (AlleBilder-MaxAhnlichkeit ).
Eine dritte Losung zur Bestimmung des Endergebnisses ist, fur jedes Bild aus der Bilddatenbank das arithmetische Mittel ihrer Rankingpositionen aus den einzelnen RankingErgebnissen zu berechnen, dann die Bilder bezuglich diesem arithmetischen Mittel aufsteigend zu sortieren und dieses Ranking als Endergebnis auszugeben. (AlleBilder-DurchschnittsRank ) 3.7.2
Durchschnitte
Bei der letzten visuellen Beschreibung werden nicht wirklich Charakteristika des Objektes gelernt, diese stellt also keine visuelle Beschreibung in unserem gewunschten Sinne dar. Wir gehen davon aus, dass die A hnlichkeit zweier ahnlicher Bilder auf einer gemeinsamen Teilmenge der visuellen Worter und visuellen Phrasen basiert. Wir extrahieren daher die Gemeinsamkeiten zweier ahnlicher Bilder, indem wir den Durchschnitt ihrer Histogramme gema der Formel 5 bilden. Fur jede Bildgruppe aus der Menge der Bildgruppen werden paarweise Durchschnitte der Trainingsbilder aus der Bildgruppe berechnet. Die visuelle Beschreibung besteht dann aus allen gebildeten Durchschnitten, d.h. jeder Durchschnitt dient bei der inhaltsbasierten Bildsuche als ein Anfragebild und es nden mehrere Anfragen statt.
Wie bei der ersten visuellen Beschreibung, erhalten wir auch hier eine Menge von einzelnen Ergebnissen und mussen diese zu einem Endergebnis berechnen. Wir wenden dazu die drei beschriebenen Strategien an (Durchschnitte-BesterScore, Durchschnitte-MaxAhnlichkeit, Durchschnitte-DurchschnittsRank ).
Die bisher vorgestellten visuellen Beschreibungen sind problematisch: sie bestehen aus mehreren Anfrageinstanzen und weisen daher eine zeitaufwandige Anfrageverarbeitung auf.
Eine kompakte Darstellung der visuellen Beschreibung, d.h. eine Darstellung, die aus nur einer Anfrageinstanz besteht, ware von Vorteil. Eine einfache Losung wiederum ist, das beste Trainingsbild aus den Trainingsbildern eines Eintrags als visuelle Beschreibung zu wahlen. Um das beste Trainingsbild zu bestimmen, vereinigen wir die Bildgruppen und stellen mit jedem Bild aus der Vereinigung eine Anfrage an die ganze Trainingsmenge. Mit einem Qualitatsma wird jedes Anfrageergebnis bewertet und das Anfragebild mit der besten Gute, d.h. mit dem hochsten Score des Ergebnisses fur die visuelle Beschreibung ubernommen (BestesBild ). Das gewahlte Trainingsbild kann jedoch ein lokales Optimum darstellen und in der Suche auf der Bilddatenbank versagen. Weiterhin zeigt sich auch hier das Problem, dass keine Charakteristika von Objekten aus den ahnlichen Trainingsbildern gelernt werden. 3.7.4
Durchschnitte kompakt - Anzahl
Um eine kompakte Darstellung der visuellen Beschreibung zu erhalten, die die gemeinsamen Charakteristika des Objektes ausdruckt, kommen wir auf das Konzept der Durchschnitte zuruck. Wie in der zweiten visuellen Beschreibung beschrieben, bilden wir zunachst Durchschnitte der paarweisen Trainingsbilder pro jede Bildgruppe. Wir nehmen an, dass visuelle Worter und visuelle Phrasen, die in den meisten Durchschnitten auftreten, fur das Objekt relevanter sind, als die, die seltener vorkommen. Wir erstellen daher eine visuelle Beschreibung aus zwei Histogrammen, der visuellen Worter und der visuellen Phrasen, und zahlen fur jedes visuelle Wort und jede visuelle Phrase, in wievielen Durchschnitten es vorkommt. Diese absolute Durchschnitts-Frequenz bildet dann den Wert des jeweiligen visuellen Wortes oder der visuellen Phrase in den Histogrammen (DurchschnitteKompaktAnzahl ). 3.7.5
Durchschnitte kompakt - Summe
Um die Wichtigkeit jedes visuellen Wortes und jeder visuellen Phrase innerhalb eines Durchschnitts zu betonen, wird anstatt der Anzahl der Durchschnitte eine Summe der Durchschnitte gebildet. Genaugenommen werden wieder zwei Histogramme der visuellen Worter und visuellen Phrasen erstellt und jedes Bin des Histogramms ist die Summe der entsprechenden Bins der Histogramme aller Durchschnitte. (DurchschnitteKompakt-Summe) 3.7.6
Durchschnitte kompakt - Gewichtete Summe
Der nachsten visuellen Beschreibung liegt die folgende Frage zugrunde: gibt es visuelle Phrasen, die fur ein Objekt spezi sch sind, d.h. ist der Anteil der Bilder zu einem Term und einer visuellen Phrase an allen Bildern, die diese visuelle Phrase beinhalten, besonders hoch? Wir berechnen fur jede visuelle Phrase vp und dem zugrundeliegenden Term t des Eintrags das Gewicht: gV P (t; vp) := #B(t; vp) #B(vp) mit B(t; vp) stellt die Menge aller Trainingsbilder zu dem Term t, d.h. die Vereinigung der Bilder aus den Bildgruppen zu t, die die visuelle Phrase vp beinhalten, dar. Wir ubernehmen die zuvor de nierte visuelle Beschreibung DurchschnitteKompakt-Summe und gewichten den Hau gkeitswert jeder visuellen Phrase vp mit gV P (t; vp). (DurchschnitteKompaktGewichteteSumme) 3.7.7
Durchschnitte kompakt - TFIDF
Fur die folgende visuelle Beschreibung ubernehmen wir die Idee der tf-idf Gewichtung fur Dokumentvektoren. Mit Hilfe der inversen Dokumenthau gkeit eines Terms, hier inverse Bildhau gkeit eines visuellen Wortes oder einer visuellen Phrase, wollen wir die Hau gkeiten der visuellen Worter und visuellen Phrasen, die in sehr vielen Trainingsbildern vorkommen, schwacher, und die die seltener vorkommen, starker gewichten. Analog zum Text-Retrieval bilden wir also eine Summe aller Durchschnitte, wie in der visuellen Beschreibung DurchschnitteKompakt-Summe beschrieben, berechnen dann fur jedes visuelle Wort vw und jede visuelle Phrase vp das idf Gewicht: gIDF (vw) := log wichten multipliziert: jedes Bin zu einem visuellem Wort vw mit gIDF (vw) und jedes Bin zu einer visuelle Phrase vp mit gIDF (vp). (DurchschnitteKompakt-TFIDF )
Durchschnitte kompakt - Gewichtetes TFIDF
Die Gewichte aus den beiden letzten visuellen Beschreibungen werden im Folgenden kombiniert. Wir erstellen wieder die Summe aller Durchschnitte und gewichten dann jeden Hau gkeitswert des jeweiligen visuellen Wortes vw mit gIDF (vw), und jeden Hau gkeitswert einer visuellen Phrase vp mit dem kombinierten Gewicht: gV P IDF (t; vp) := #B(t; vp) #B(vp) log
#B #B(vp) (DurchschnitteKompakt-GewichtetesTFIDF ) 4.1
EVALUATION
Trainings- und Testmenge
Fur die Test- und Trainingsmenge werden Bilder und Annotationen zu 50 Objekten aus dem World Wide Web gesammelt. Fur jedes der 50 Terme werden jeweils 10 Trainingsbilder und ca. 30 Testbilder heruntergeladen. Als Objekte werden Tiere, Fruchte, Gegenstande, Gebaude und Symbole gewahlt. Fast alle Bilder liegen in einer Au osung von ca. 400 400 Pixel vor.
Testdurchführung
Die vorgestellten visuellen Beschreibungen werden hinsichtlich der Qualitat des Retrievals und der Anfragee zienz analysiert, um so aus den daraus gewonnenen Ergebnissen und Erkenntnissen die beste fur das visuelle Worterbuch auswahlen zu konnen. Dazu wird fur jede visuelle Beschreibung zuerst ein visuelles Worterbuch aus der Trainingsmenge gelernt und dieses dann in der Anwendung der Bildsuche eingelesen. Fur jeden Eintrag des visuellen Worterbuchs, also jeden Term (im jeweiligen Kontext), wird eine Anfrage auf der Testmenge durchgefuhrt, dabei die Anfragezeit gemessen und schlie lich aus dem erhaltenen Ranking-Ergebnis die Gute des Ergebnisses mit dem Ma Score, der im Folgenden erlautert wird, berechnet. Um die visuellen Beschreibungen letztlich miteinander vergleichen zu konnen, wird fur jede visuelle Beschreibung, also jedes Worterbuch, das arithmetische Mittel der Anfragezeiten und der Scores uber allen Eintragen gebildet.
Bewertungsmaß
In [
Testergebnisse
Als Testergebnis erhalten wir die zwei Diagramme in Abbildung 2. Das obere Diagramm stellt den durchschnittlichen Score und das untere die durchschnittliche Anfragezeit fur jede visuelle Beschreibung dar. Die besten durchschnittlichen Scores erreichen die visuellen Beschreibungen AlleBilder-BesterScore, Durchschnitte-BesterScore, die aus multiplen Instanzen und der Endergebnis-Strategie BesterScore bestehen. Dabei sieht man, dass die auf Durchschnitten basierende visuelle Beschreibung ein besseres RetrievalErgebnis liefert, die durchschnittliche Anfragezeit sich gleichzeitig aber verdoppelt. Wie bereits erwahnt ist diese Endergebnis-Strategie nur ein theoretisches Modell. Die zwei praktisch realisierbaren Endergebnis-Strategien verhalten sich je nach visueller Beschreibung unterschiedlich: MaxAhnlichkeit schneidet bei AlleBilder besser und bei Durchschnitte schlechter ab als DurchschnittsRank. Diese multipleInstanzen visuellen Beschreibungen mit den Strategien MaxAhnlichkeit und DurchschnittsRank werden jedoch von den eine-Instanz, auf Durchschnitten basierenden visuellen Beschreibungen bzgl. dem durchschnittlichen Score deutlich ubertro en. Von den besten multiple-Instanzen visuellen Beschreibung AlleBilder-MaxAhnlichkeit, Durchschnitte-DurchschnittsRank zu den besten eine-Instanz, DurchschnitteKompakt-GewichteteSumme und DurchschnitteKompakt-TFIDF haben wir einen Zuwachs des durchschnittlichen Scores von 0.07 und die Anfragezeit sinkt dabei drastisch um das 9bzw. 17-fache. Die eine-Instanz, auf Durchschnitten basierenden visuellen Beschreibungen weisen einen deutlich besseren, um ca. 0.12 hoheren, durchschnittlichen Score gegenuber BestesBild auf, sind untereinander mit Unterschieden von bis 0.02 aber relativ ahnlich. Die besten unter ihnen, DurchschnitteKompakt-GewichteteSumme und DurchschnitteKompakt-TFIDF liefern zudem den besten durchschnittlichen Score unter allen praktisch realisierbaren visuellen Beschreibungen. DurchschnitteKompakt-TFIDF maximiert den durchschnittlichen Score und minimiert gleichzeitig die Anfragezeit, ist daher am besten fur das visuelle Worterbuch geeignet. 5. SCHLUSSFOLGERUNG UND
AUSBLICK
Von den gestellten Anforderungen an das visuelle Worterbuch werden die Grundform der Terme mit dem StemmingSchritt in der Aufbereitungsphase und die Polysemie mit dem CBC Clustering, dem Kontextvektor und den damit verbundenen Mehreintragen eines Terms, realisiert. Mit der erwahnten besten visuellen Beschreibung ist das Erfassen der Charakteristika des Objektes mit dem Konzept der Durchschnitte, die Kompaktheit und E zienz mit der eineInstanz Darstellung und die Kompatibilitat zu der Bilddatenbank mit den Histogrammen der visuellen Worter und Phrasen erfullt. Zukunftig, um die Anfragezeiten der eineInstanz visuellen Beschreibungen von ca. 12 Sekunden weiter zu reduzieren, kann man geeignete e ziente Indexstrukturen und Algorithmen fur die Bildsuche untersuchen und einsetzen. Um die Qualitat des Retrievals weiter zu verbessern, konnte man versuchen auch Farbeigenschaften und ihre Relevanz fur Objekte miteinzubeziehen, d.h. diese fur die visuelle Beschreibung zu lernen und in der Bildsuche einzusetzen. e 0,60 0,57 r coS 0,50 r ilittechnh 00,,3400 c s ch 0,20 r du 0,10 0,00 250,0 0,0 )ek 200,0 S it( e eZ 150,0 h c iilttn 100,0 101,0 101,0 101,0 h c s h rcu 50,0 d 0,48
0,59 0,36 0,38 0,47 0,42
0,53 0,53 0,55 0,55 0,54 visuelle Beschreibung 191,4 191,4 191,4
9,0 8,3 8,3 11,8 8,2 11,7 visuelle Beschreibung AlleBilder-BesterScore AlleBilder-MaxÄhnlichkeit AlleBilder-DurchschnittsRank Durchschnitte-BesterScore Durchschnitte-MaxÄhnlichkeit Durchschnitte-DurchschnittsRank BestesBild DurchschnitteKompakt-Anzahl DurchschnitteKompakt-Summe DurchschnitteKompakt-GewichteteSumme DurchschnitteKompakt-TFIDF
DurchschnitteKompakt-GewichtetesTFIDF
Abbildung 2: Durchschnittlicher Score und
durchschnittliche Anfragezeit der visuellen
Beschreibungen
6. LITERATUR
[
M. Detyniecki. Adaptive multimedial retrieval: Retrieval, user, and semantics. chapter Automatic Image Annotation Using a Visual Dictionary Based on Reliable Image Segmentation, pages 45{56.
Springer-Verlag, Berlin, Heidelberg, 2008.
[
University of Alberta, 2003.
[
NY, USA, 2009. ACM.
[
Descriptive visual words and visual phrases for image
applications. In Proceedings of the seventeen ACM
international conference on Multimedia, MM '09, pages
75{84, New York, NY, USA, 2009. ACM.
[
ACM Trans. Multimedia Comput. Commun. Appl., 5:7:1{7:19, October 2008.
A feedback guided interface for
elastic computing Sebastian Schönherr1,2,∗, Lukas Forer1,2,∗, Hansi Weißensteiner1,2, Florian Kronenberg2, Günther Specht1, Anita Kloss-Brandstätter2
∗ contributed equally
Institute of Computer Science
University of Innsbruck, Austria sebastian.schoenherr@uibk.ac.at
Department of Medical Genetics, Molecular and Clinical Pharmacology Innsbruck Medical University, Austria
lukas.forer@i-med.ac.at Computer Science plays an important role in today’s Genetics. New sequencing methods produce an enormous amount of data, pushing genetic laboratories to storage and computational limits. New approaches are needed to eliminate these shortcomings and provide possibilities to reproduce current solutions and algorithms in the area of Bioinformatics. In this paper a system is proposed which simplifies the access to computational resources and associated computational models of cluster architectures, assists end users in executing and monitoring developed algorithms via a web interface and provides an interface to add future developments or any kind of programs. We demonstrate on existing algorithms how an integretation can be done with little effort, making it especially useful for the evaluation and simplified usage of current algorithms.
Categories and Subject Descriptors H.4 [Information Systems Applications]: Miscellaneous General Terms Distributed System, Experimentation, Application Bioinformatics, Hadoop, MapReduce, Cloud computing
INTRODUCTION
In recent years Computer Science became an essential part in the field of Genetics. Especially through the advent of Next Generation Sequencing (NGS), whereby a human genome (3 billion base pairs/chromosome set) can be sequenced in acceptable time, the amount of data is growing significantly, exceeding all known dimensions in Genetics.
Figure 1 shows a comparison between the reducing DNA
sequencing costs and Moore’s law. Moore’s law is used as a
reference to show that computer hardware can currently not
keeping pace with the progress in DNA sequencing.
Furthermore, the amount of complete sequenced individuals is
growing exponentially from year to year [
In the area of Copy Number Variations, a possible cause
for many complex genetic disorders, high throughput
algorithms are needed to process and analyze several hundred
gigabytes of raw input data [
Cluster architectures in connection with associated
models have the potential to solve this issue, but especially for
small departments often gainless and unaffordable. Using
clusters on demand, also referred to Infrastructure as a
Service (IaaS), builds therefore a good opportunity to circle
these issues. To capitalize the full potential of IaaS, a
combination with distribution models like MapReduce [
But since no general system is given to execute those solutions, an evaluation and reproducibility is often not feasible.
Scientists need to setup a cluster on their own or using a provided remote cluster architecture to evaluate a published algorithm, being both time wasting and insecure for sensitive data. Sept01 Sept02 Oct03 Apr04 Oct04 Apr05 Oct05 Apr06 Okt06 Apr07 Oct07 Apr08 Oct08 Apr09 Oct09 Apr10 Oct10 Mar02 Mar03 Jan04 Jul04 Jan05 Jul05 Jan06 Jul06 Jan07 Jul07 Jan08 Jul08 Jan09 Jul09 Jan10 Jul10 Date In this paper we present the idea to build an integrated system for scientists in the area of Bioinformatics to (1) get access to distributed cluster architectures and execute existing algorithms, (2) build maintainable and reproducible workflows and (3) provide an interface to add future developments or any kind of programs to the system without detailed IT knowledge. The reminder of this paper is structured as follows: Section 2 gives an overview of the related work. In section 3 the architecture of our suggested system is explained in more detail with potential case studies in section 4. Section 5 shows necessary future work and the paper ends with a conclusion in section 6.
RELATED WORK
Cluster solutions guided by a web-interface to execute
distributed algorithms like Myrna [
Galaxy [
However, the user needs to start the master node manually by using the AWS console and Galaxy does not provide a native support of Hadoop programs, executes modules step by step and distributes only whole jobs among the cluster.
ARCHITECTURE
A modular architecture is suggested in Figure 2, separating the process of instantiate and set up a cluster (Cloudgene) from the process of monitor and run a program (EMI ).
Based on open source frameworks like Apache Hadoop [
EMI can be seen as an abstraction of the underlying system architecture from the end user, lies on top of the integrated programs and allows the user to communicate and interact with the cluster as well as receive feedback of currently executed workflows (see Figure 3). EMI can be disabled in case a program already includes an interface by its own, yielding to the most general approach to execute any kind of developed solution. Both parts can be operated separately via configuration files with clear defined input and output variables. 3.1
Cloudgene
Amazon provides with its EC2 the currently most
developed service for public clouds in the area of IaaS. Cloudgene
supports besides EC2 also Rackspace [
EMI ...
Whirr XML Config Restlet
ExtJS a combination with MapReduce is useful: In this paradigm, the master node chops up data into chunks and distributes it over all active worker nodes (map step). Subsequently, the master node reassigns coherent map results to worker nodes (sort and shuffle) to calculate the final result (reduce step). For this project Apache Hadoop’s implementation of MapReduce and its distributed file system (HDFS) are used.
Using Whirr as a connector, Cloudgene is able to instance a full working EC2 or Rackspace cluster for end users with various defined properties and copies the necessary program data and configuration files to the cluster. Examples for defined variables could be the desired image, amount and kind of instances, HDFS options, MapReduce properties and the user’s SSH public key. Amazon already provides several predefined images for all sorts of use cases, which can be be used with Cloudgene (e.g. http://www.cloudbiolinux.com).
Cloudgene takes over the customization of predefined images
and installs services like MapReduce, in our case included in
Cloudera’s distribution of Apache Hadoop [
Cloudgene routinely checks if new configurations are added and offers the possibility to execute newly defined programs.
Since EC2 is using a pay-per-use model, end users must provide their Amazon Access ID and Secret Key, which is transferred via Cloudgene to Amazon in a secure way. Alternatively, Cloudgene can also be launched on every machine having Java installed, eliminating the transfer via our server.
Cloudgene solves one important issue and gives genetic departments access to computational power and storage. A still unresolved problem is the lack of a graphical user interface to control jobs deriving from command line based applications. Especially the need of putting enormous amount of local data into HDFS has to be considered. To overcome these shortcomings, a user interface (EMI) was designed. 3.2
Efficient MapReduce Interface (EMI)
Running Hadoop MapReduce programs on a cluster
requires the execution of several non-trivial steps: First, the
user must upload all input data to the master node, copy the
data into the proprietary HDFS, run the Hadoop
MapReduce job, export the results from the filesystem and finally
download them to the local workstation. For researchers
without expertise in Computer Science these tasks turns out
to be very challenging. For this purpose we developed EMI
which facilitates the execution, monitoring and evaluation
of MapReduce jobs. A web interface, which runs on the
master node of the cluster, enables the execution of jobs
through well-structured wizards and setting all required
parameters step by step. As several studies have shown,
reproducibility of data analysis is one of the greatest problems in
biomedical publications [
The modular architecture enables a fast integration of any Hadoop job which could be normally executed through the command line. A simple and clear XML configuration file describes the input and output parameters of the program and contains other relevant information that are necessary to start the job (see Section 4). In addition to this file, a zip archive file exists which contains all software relevant data (e.g. jar file, meta data, configuration files). With those files, EMI automatically generates a web interface in which the possibility to set each defined parameter through wizards and to run the defined job by a single click is provided.
As mentioned earlier, all input data must be put into the robust and fault-tolerant HDFS. As this process is very timeintensive an error prone, EMI supports the user by providing a wizard which enables the import of data from different sources (FTP, HTTP, Amazon S3 buckets or local file uploads). In addition, files defined as output parameters can be exported and downloaded as a zip archive or can be uploaded to Amazon S3 or FTP servers. EMI supports a multiuser mode whereby all data by a certain user are password protected and executed jobs are scheduled through a queue system. Overall, EMI is fully independent from Cloudgene and can be installed on a local Hadoop cluster too.
In this section we explain how new programs can be integrated into Cloudgene and EMI. Based on two different biomedical software solutions we demonstrate the diversity and simplicity of our approach. 4.1
CloudBurst is a parallel read-mapping algorithm to map
NGS data to the human genome and other reference genomes
[
In order to execute CloudBurst we create a configuration file for Cloudgene which starts a Hadoop cluster on Amazon EC2 with a standard Ubuntu Linux with open Hadoop ports 50030 and 50070. The corresponding XML has the following structure:
As CloudBurst has no graphical user interface, we install EMI on the Amazon EC2 cluster and use it for user interactions. For this purpose the command above with its arguments must be translated into the following configuration file: <emi> <program> <name>CloudBurst</name> <command> hadoop jar emi/cloudburst/CloudBurst.jar \ $input1 $input2 $output1 36 36 3 0 1 240 \ 48 24 24 128 16 </command> <input> <param id="1" type="hdfs"> <name>Reference Genome</name> <default>data/cloudburst/s_suis.br</default> </param> </input> <input> <param id="2" type="hdfs"> <name>Reads</name> <default>data/cloudburst/100k.br</default> </param> </input> <output> <param id="1" type="hdfs" merge="true"> <name>Results</name> <default>data/cloudburst/results</default> </param> </output> </program> </emi>
After the XML file is uploaded to the Cloudgene server, the user starts a web browser to (1) login to Cloudgene, (2) start up a cluster preconfigured with CloudBurst and (3) run and monitor jobs with EMI (Figure 4).
Compared to a standard manual approach, this eliminates error-prone and time-consuming tasks such as (1) setting up a cluster and connecting via the command line onto the master node, (2) uploading and importing data into HDFS, (3) exporting final results from HDFS and downloading them and (4) executing and reproducing MapReduce jobs with different configurations via a web interface. This shows, that an easy integration can be done using a simple XML configuration, supporting and guiding researchers as far as possible.
HaploGrep is a reliable algorithm implemented in a web
application to determine the haplogroup affiliation of
thousands of mitochondrial DNA (mtDNA) profiles genotyped
for the entire mtDNA or any part of it [
Since it does not use the Hadoop service either, we note this option in the configuration as well. HaploGrep listens on the ports 80 (http) and 443 (https), therefore this ports are marked as open. The configuration file for Cloudgene with all requirements looks as follows:
After the cluster setup is finalized, Cloudgene returns a web address which points to the installed instance of HaploGrep.
One of the biggest advantages of IaaS is the changable amount of needed datanodes on demand. Thus, the next version of Cloudgene is conceived to provide functions for adding and removing instances during runtime. Currently, clusters started with Cloudgene are not data persistent which yields to a data loss after a shutdown is fulfilled. For this purpose we plan to store all results on persistent Amazon EBS volumes. Furthermore, a simple user interface for Hadoop is not only useful for the end user but also for developers. It supports them during the whole prototyping and testing process of novel MapReduce algorithms by highlighting performance bottlenecks. Thus, we plan to implement time measurements of the map, reduce and shuffle phase and to visualize them in an intuitive chart. Additionally, Hadoop plans in its next generation approach to support alternate programming paradigms to MapReduce, what is particularly important for applications (e.g. K-Means) where custom frameworks out-perform MapReduce by an order of magnitude.
We presented a software system for running and maintaining elastic computer clusters. Our approach combines the individual steps of setting up a cluster into a user-friendly system. Its modular architecture enables a fast integration of any Hadoop job which could be only executed through the command line. By hiding the low-level informatics, it is the ideal system for researchers without deeper knowledge in Computer Science. Moreover, our system is not constricted to the life sciences and can be used in nearly every application range. Overall, it is a first approach in order to narrow the gap between cloud-computing and usability.
ACKNOWLEDGMENTS
Sebastian Scho¨nherr was supported by a scholarship from the University of Innsbruck (Doktoratsstipendium aus der Nachwuchsfo¨rderung, MIP10/2009/3). Hansi Weißensteiner was supported by a scholarship from the Autonomous Province of Bozen/Bolzano (South Tyrol). The project was supported by the Amazon Research Grant. We thank the Whirr Mailinglist especially Tom White and Andrei Savu for their assistance.
REFERENCES
[
A. Nekrutenko, and J. Taylor. Galaxy CloudMan: delivering cloud compute clusters. BMC
Bioinformatics, 11 Suppl 12:S4, 2010.
[
Opearting Systems Design & Implementation, pages 10–10, Berkeley, CA, USA, 2004. USENIX
Association.
[
T. Kluckner, C. Gieger, H. E. Wichmann, G. Specht, F. Kronenberg, and A. Kloss-Brandsta¨tter. CONAN: copy number variation analysis software for genome-wide association studies. BMC
Bioinformatics, 11:318, 2010.
[
G. Ananda, D. Baker, D. Blankenberg, R. Chakrabarty, N. Coraor, J. Goecks, G. Von Kuster, R. Lazarus, K. Li, A. Nekrutenko, J. Taylor, and K. Vincent. Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences. Genome
Biol., 11:R86, 2010.
[
H. Weißensteiner, R. Binna, G. Specht, and F. Kronenberg. HaploGrep: a fast and reliable algorithm for automatic classification of mitochondrial
DNA haplogroups. Hum. Mutat., 32:25–32, Jan 2011.
[
Cloud-scale RNA-sequencing differential expression
analysis with Myrna. Genome Biol., 11:R83, 2010.
[
Salzberg. Searching for SNPs with cloud computing.
Genome Biol., 10:R134, 2009.
[
genomics. Genome Biol., 11:128, 2010.
[
S. F. A. Grant, H. Hakonarson, and M. Bucan.
PennCNV: An integrated hidden Markov model designed for high-resolution copy number variation detection in whole-genome SNP genotyping data.
Genome Research, 17(11):1665–1674, Nov. 2007.
[
KORA-gen–resource for population genetics, controls and a broad spectrum of disease phenotypes.
Gesundheitswesen, 67 Suppl 1:26–30, Aug 2005.