Die Forschungsgruppe Datenbanken und Informationssysteme an der Universität Innsbruck

Die Forschungsgruppe (Lehrstuhl) Datenbanken und Informationssysteme (DBIS) an der Universität Innsbruck wurde 2006 von Günther Specht gegründet und wird seither von ihm geleitet. Sie besteht derzeit aus elf Mitarbeitern und drei assoziierten Mitarbeitern an der Sektion für Genetische Epidemologie der Medizinischen Universität Innsbruck. Allein 2017 wurden vier Dissertationen eingereicht.

Unser Schwerpunkt liegt derzeit auf fünf Forschungsrichtungen:

Zusätzlich entwickeln wir noch eine Reihe viel genutzter Systeme, wie den BIM-Merkmalserver für die Bauindustrie, den Haplogrep-Server zur Bestimmung der Haplogruppen in der Genetik, den CloudGene-Server (Cloud Service für die Genetik, basierend auf Hadoop und MapReduce), einige Systeme für die Digital Humanities, sowie verschiedene Lern-Tools für Studierende, wie z. B. RelaX¹, mit dem die relationale Algebra auf beliebigen Datensets interaktiv ausführbar ist und somit leichter verständlicher gemacht wird. Viele Systeme sind über unsere Homepage² zugreifbar.

Da das Umfeld, in dem wir arbeiten, nicht ganz so bekannt ist, möchten wir vorab kurz die Universität und das Institut für Informatik vorstellen.

Die Universität Innsbruck ist eine Volluniversität und die größte Universität Westösterreichs. Sie besteht aus 16 Fakultäten, das Spektrum reicht alphabetisch von Architektur bis Volkswirtschaft und chronologisch von der Philosophischen Fakultät (1669) bis zur School of Education (2012). Sie hat 28.300 Studierende, 126 Studienfächer, 4.600 MitarbeiterInnen, davon 3.200 wissenschaftliche MitarbeiterInnen. Unser Einzugsbereich umfasst Tirol, Vorarlberg, Südtirol (Italien), Liechtenstein und den Süden von Bayern. In den internationalen Rankings ist die Universität Innsbruck sowohl im Times Higher Education Ranking gelistet als auch im Shanghai Ranking. Dort steht sie 2016 in der Gruppe der 151–200 besten Universitäten weltweit und damit – gemeinsam mit der Universität Wien – an der Spitze der österreichischen Hochschullandschaft.

Das Institut für Informatik wurde 2001 gegründet und besteht inzwischen aus 8 Forschungsgruppen (Lehrstühlen) und 11 ProfessorInnen (einschließlich assoziierter Professoren). Der Schwerpunkt des Instituts liegt auf der Praktischen und Angewandten Informatik einerseits und Computer Vision und der Robotik andererseits. Im Bachelorstudium haben wir jährlich ca. 130–160 Anfänger, insgesamt etwas über 850 Studierende und ca. 50 DoktorandInnen. Aktuell wurde unser Informatikstudium im Times Higher Education Computer Science Ranking 2017 in den Bereich 151–175 weltweit gelistet. Im U‑Multirank Student Survey 2015, wurde das Institut mit A (dem höchsten Rang) in 13 Gebieten, einschließlich Forschung, Lehre und Internationalität bewertet. Insgesamt arbeiten am Institut 130 Mitarbeiter, die Hälfte davon auf Drittmittelstellen. Dazu wurden in den letzten fünf Jahren am Institut 34 Millionen Euro Drittmittel akquiriert. Das Institut für Informatik ist Teil der Fakultät für Mathematik, Informatik und Physik, der größten Fakultät der Universität.

Im Kerndatenbankbereich beschäftigt sich DBIS vor allem mit der Datenorganisation im Hauptspeicher. Im Speziellen wird in diesem Bereich an neuartigen Indexstrukturen für Hauptspeicherdatenbanken und der optimierten Speicherung von Graphdaten geforscht [1]. Im Bereich von Graphdatenbanken wurde der Ansatz eines hauptspeicherorientierten Datenbanksystems entwickelt, das Graphdaten nativ mittels intelligenter Zeigerstrukturen abbildet und zur Anfrageverarbeitung tiefensuchbasierte Kantentraversierungen verwendet. Ebenfalls wurde ein Algorithmus entwickelt, der Graphdaten in dreidimensionalen Speichertopologien für zukünftige hochparallele Rechner optimal verteilt [10]. Ein weiterer Schwerpunkt im Kerndatenbankbereich liegt auf der optimierten Indizierung im Umfeld von Hauptspeicherdatenbanken. In diesem Bereich wurde mit dem DCB-Tree (Delta Coded B‑Tree) eine speichereffiziente Indizierung von kurzen Schlüsseln entwickelt [2]. Aktuell wird an einer trie-basierten Indexstruktur mit Namen HOT (Height Optimizing Trie) geforscht, die sowohl speichereffizienter als auch performanter als vergleichbare Alternativen ist. Im Gegensatz zu bekannten Trie-Strukturen ist der dabei entwickelte Ansatz robust gegenüber ungleich verteilten, langen Schlüsseln.

Ein wichtiger Punkt unserer Forschung umfasst den Bereich des Music Information Retrieval und der Recommender Systeme. Dabei liegt der Schwerpunkt auf Context-aware Recommender Systems – Empfehlungssysteme, die entsprechend dem Kontext des Benutzers personalisierte und angepasste Empfehlungen berechnen, da der wahrgenommene Nutzen einer Empfehlung stark vom Kontext abhängt. Im Fall von Musikempfehlungen bedeutet Context Awareness, dass ein Benutzer im richtigen Moment (der richtigen Situation) das richtige Musikstück vorgeschlagen bekommt. Wir befassen uns daher mit zwei Bereichen: (i) Feature Extraktion und Engineering, um verbesserte Features zur Charakterisierung von Benutzern, Musikstücken und Kontext zu entwickeln und (ii) Recommender Systeme, die insbesondere das kontextspezifische Verhalten (und die entsprechenden Features) von Benutzern bestmöglich für die Personalisierung von Empfehlungen auszunutzen. Im Bereich des User Modelings arbeitet DBIS daran, verschiedene Arten von Kontext-Features zu extrahieren, um eine möglichst vollständige Charakterisierung des Benutzers und dessen Kontext zu erhalten [11]. Diese Features reichen von der aktuellen Situation des Benutzers (z. B. Fitnessstudio, Arbeit, Erholung) über die aktuelle Gemütslage des Benutzers bis hin zu kulturellen Aspekten. Als Datengrundlage dafür dienen Daten aus dem Social Web, wie sogenannte #nowplaying Tweets, Daten von Musikempfehlungsdiensten wie last.fm, aber auch Daten, die direkt von Plattformen für Music Streaming wie Spotify gecrawlt wurden. Daraus entstanden zwei Datensets: das #nowplaying-Datenset [25] und das Playlist-Datenset [11], die DBIS frei zur Verfügung stellt³. Diese neu entwickelten Features fließen dann in Empfehlungssysteme ein, die mit State-of-the-Art-Algorithmen versuchen, den Benutzer, dessen Kontext und sein kontext-spezifisches Musikverhalten zu modellieren [12, 13]. So bilden die bei DBIS entwickelten User-Modelle unter anderem ab, welche User entsprechend ihres kulturellen Kontextes und ihrer aktuellen Situation bestimmte Arten von Musik präferieren. Dabei legen wir großen Wert auf die Interpretierbarkeit der Modelle und forschen daher an Methoden basierend auf Regression, Matrix-Faktorisierung und Baum-basierter Klassifizierung.

Ein weiteres großes Standbein ist die Forschung im Bereich von semistrukturierten Informationssystemen. In kollaborativen Plattformen werden oftmals Tags (oder Key/Value-Paare) eingesetzt, um Ressourcen zu annotieren und zu kategorisieren. Diese Annotationen sind von den Benutzern frei wählbar, was dazu führt, dass sich die verwendeten Annotationen stark unterscheiden (z. B. durch die Verwendung von Synonymen oder durch die unterschiedliche Strukturierung der Informationen). Diese Heterogenität schränkt die Möglichkeit, diese Daten effizient abzufragen, stark ein. Daher verfolgt der von DBIS entwickelte Snoopy-Ansatz [4, 5] das Ziel, Empfehlungssysteme einzusetzen, um passende Elemente (Keys und Values) vorzuschlagen. So kann proaktiv der Heterogenität von Informationen in semistrukturierten Informationssystemen entgegengewirkt werden, indem Benutzer direkt bei der Eingabe von neuen Informationen unterstützt werden. Dies führt einerseits zu homogeneren Informationen und damit gesteigerter Abfrage-Performance und andererseits dazu, dass Benutzer mehr Informationen eingeben, da sich durch die Verfügbarkeit von Empfehlungen die Eingabe einfacher gestaltet [26].

Ein weiterer Fokus der DBIS-Gruppe in Innsbruck liegt auf der Analyse von Textdokumenten. Dabei widmet sich ein Teilbereich der intrinsischen Plagiatserkennung, in dem versucht wird, anhand von Stilbrüchen innerhalb eines Textdokuments mögliche Plagiate zu identifizieren. Hierfür werden die einzelnen Sätze des zu untersuchenden Dokuments in eine Grammatikbaum-Struktur übergeführt, deren Ähnlichkeit anschließend mit Hilfe von maschinellem Lernen gemessen werden kann. Werden zu große Unterschiede in der verwendeten Grammatik entdeckt, spricht das für einen möglichen Fall von Plagiarismus. Wir konnten zeigen, dass sich die von den verschiedenen Autoren verwendete Grammatik signifikant unterscheidet und sich die Analyse der Grammatik dadurch gut für diesen Zweck eignet [18, 19].

Ein weiteres Forschungsgebiet stellt die Autorenerkennung dar, in dem ein unbekanntes Dokument einem bestimmten Autor zugewiesen werden soll. Auch hier konnten durch die Analyse von verschiedenen grammatikalischen Merkmalen erhebliche Verbesserungen erzielt werden [20]. Die automatische Profilerstellung ist ein technisch verwandtes Themengebiet, bei dem versucht wird, Metainformationen wie etwa das Alter oder Geschlecht aufgrund des Schreibstils vorauszusagen [21]. Schließlich wird auch im Bereich der Multilingualität geforscht, in dem Algorithmen entwickelt wurden, um maschinell übersetzte Texte zu identifizieren und ihrer ursprünglichen Sprache mit hoher Genauigkeit zuzuordnen. Die Anwendungsgebiete der verschiedenen Arten der Textanalysen sind vielfältig: so kann etwa nach möglichen Plagiaten in Dokumenten gesucht werden, deren Quellen nicht digital verfügbar sind (z. B. ältere Bücher) und somit von Systemen nicht erkannt werden können, die auf externe Referenzdatenbanken zugreifen. Anwendungen der Autorenzuordnung von Texten reichen vom Erkennen von Ghostwriting über digitale Forensik bis hin zu Tantiemenstreitigkeiten bei Mehrautorenwerken. Seit 2015 ist DBIS im Organisationsteam des international angesehenen PAN-Workshops vertreten, der jährliche Tasks rund um das Thema Textanalyse veranstaltet [17, 22].

In Geoinformationssystemen bezeichnen die Flächen innerhalb einer Isochrone die Gebiete, die von einem Ausgangspunkt aus innerhalb einer gegebenen Zeit erreichbar sind. Diese müssen nicht notwendigerweise zusammenhängend sein (siehe z. B. Zug-Haltestellen) und können Löcher enthalten (z. B. Berge). Mit Hilfe der entwickelten Algorithmen lassen sich viele interessante Fragestellungen beantworten, darunter z. B. wo Schulen oder Rettungsstellen platziert werden müssen, um innerhalb einer gewissen Zeit von allen Punkten aus erreichbar zu sein. Wenn man die Gebiete betrachtet, von wo aus ein bestimmter Punkt innerhalb einer gegebenen Zeit erreichbar ist, spricht man von einer Incoming Isochrone, sonst von einer Outgoing Isochrone. Unser Ziel ist es, multimodale Isochrone, d. h. unter Benutzung beliebig kombinierbarer Verkehrsmittel, für große Netze effizient zu berechnen. Dabei werden sowohl kontinuierliche Verkehrsmittel (wie zu Fuß oder Auto) als auch diskrete (wie öffentliche Verkehrsmittel, die fahrplangebunden sind) berücksichtigt. Wir beziehen dabei auch die Höheninformation (z. B. wichtig beim Fahrrad) mit ein. Diese Forschung erfolgt in enger Zusammenarbeit mit den Datenbankgruppen der Freien Universität Bozen (Johann Gamper). Generell erweist sich der Dijkstra-Algorithmus zur Berechnung von Isochronen schnell als ineffizient. Unsere Ansätze mit den MineTX- und MineRX-Algorithmen [7] verwenden inkrementell adaptives sowie dynamisches Nachladen und Freigeben von Knoten. Damit werden auch große Netze wie Berlin, Washington DC oder die ganze Schweiz in IsoMAPs berechenbar. Auf unserer Webseite findet sich eine Web-Applikation⁴, mit deren Hilfe das Prinzip veranschaulicht und Isochrone mit verschiedenen Algorithmen berechnet werden können. Zur Erstellung geeigneter Datensets müssen Informationen aus unterschiedlichsten Quellen integriert sowie deren Datenqualität ermittelt und optimiert werden [15].

Unter dem Begriff BIM (Building Information Modeling) wird im Bauwesen nicht nur ein digitales Gebäudemodell verstanden, sondern alle im Zuge eines Bauvorhabens anfallenden Daten über den kompletten Lebenszyklus hinweg – von der Projektidee über die Planung, die Ausführung, den Betrieb bis hin zur Verwertung der Rohstoffe beim Abbruch. All diese Daten sollen normiert und integriert in einem Datenmodell gehalten werden, d. h. in einer Datenbank. Dabei sprechen wir bei einem Lebenszyklus von weit über 100 Jahren. Zur Zeit wird intensiv an der Normierung und Internationalisierung der dabei zur Verwendung kommenden Merkmale mit deren Bemessungen, Einheiten, Verantwortlichkeiten und Projektphasenabhängigkeiten gearbeitet. Im Rahmen zweier Kooperationsprojekte mit Tiroler Unternehmen und dem Arbeitsbereich für Baubetrieb, Bauwirtschaft und Baumanagement der Universität Innsbruck wurde von DBIS der erste öffentliche Merkmalserver (BIM Property Server) entwickelt [16], der inzwischen als ÖNORM A 6241-2 Teil des ÖNORM-Standards ist (das entspricht dem DIN-Standard). Die Daten werden durch das Normungsgremium des Austrian Standards Institute (ASI) (Pendant zur DIN) eingepflegt, online diskutiert, international abgeglichen (um Duplikate zu vermeiden), mit einem international eindeutigen „Global Unique Identifier“ (GUID) versehen, und als Norm für Österreich freigegeben. Intern kommt für den ganzen Prozess und für die Normdatenbank eine Graphdatenbank zum Einsatz, die sich durch ihre flexible Erweiterbarkeit in der heterogen zusammengesetzten Kooperation aus Architekten, Ingenieuren, und Informatikern bestens bewährt hat. Derzeit arbeiten wir an einer Internationalisierung, da auch andere Länder Interesse gezeigt haben, den BIM-Merkmalserver zu übernehmen.

Schwerpunkt der bioinformatischen Forschungsgruppe an der Genetischen Epidemologie sind die Methodenentwicklung, die Systementwicklung und die Bereitstellung von Services für genetische Anwendungen. Das hierfür entwickelte Framework Cloudgene⁵ wurde 2012 publiziert [14] und stellt die Grundlage für mehrere Systeme und Dienste dar. Cloudgene setzt dabei auf dem MapReduce-Programmiermodell in Apache Hadoop auf.

Als eines der darauf aufbauenden Systeme bietet der Michigan Imputation Server⁶ einen kostenlosen Genotype Imputation Service. Hierbei werden unvollständige DNA-Informationen mit statistischen Ansätzen, basierend auf einem großen Referenzdatensatz, vervollständigt. Dieses System wurde in Zusammenarbeit mit der University of Michigan und dem Eurac Research Center (in Zusammenarbeit mit Goncalo Abecasis und Christian Fuchsberger) entwickelt. Mit bereits über 13 Millionen analysierten Genomen und über 2.500 aktiven Nutzern ist es eines der größten Cloud-Dienste für genetische Daten. Der zugrundeliegende Ansatz und die Methoden wurden in drei Nature Genetic Papers veröffentlicht [3, 8, 9].

Ein weiterer Service basierend auf Cloudgene ist der mtDNA-Server⁷ [23], ein kostenloser Dienst für die Analyse menschlicher mitochondrialer DNA-Daten. Hier wird die zuverlässige Identifizierung von geringsten Mutationen mit hoher Genauigkeit erreicht. Zudem ermöglicht dieser Ansatz das Detektieren von Artefakten und Kontamination in Next-Generation-Sequenzierungsdaten. Dabei werden in massiven parallelen Sequenzieransätzen Daten im Hochdurchsatz generiert, wobei die Datenauswertung zum Bottleneck wird. Durch den skalierbaren MapReduce-Ansatz wird dem Rechnung getragen.

Die bereits erwähnten Mitochondrien, die in den Körperzellen für die Energieprozesse mitverantwortlich sind, besitzen eine eigene DNA (mitochondriale DNA, kurz mtDNA), die im Menschen ausschließlich mütterlicherseits vererbt wird. Dadurch ist es möglich, die Verbreitung des Menschen über tausende von Jahren zurückzuverfolgen. Dies wird durch die Klassifizierung von mtDNA-Sequenzen in sogenannte Haplogruppen ermöglicht. Diese Klassifizierung ist vor allem für evolutionäre, forensische und medizinische Genetik wichtig. Mit dem Tool HaploGrep⁸ [6] haben wir ein System entwickelt, das von vielen Gruppen weltweit eingesetzt wird. Dieses Tool wurde ebenso wie der bereits erwähnte mtDNA-Server in einem renommierten Journal⁹ veröffentlicht [24]. Die Services sind frei verfügbar und führten bereits zu zahlreichen Kooperationen weltweit.