Bachelorarbeit !"#$%&'$(&)%*'+,-$+,*'("./(."&0"(0"* 102(3)/.40%(0 Benjamin Kopf 5(.3&0%#$%#6 7"890"6 :0#)%%0%*$46 :00%30(*$46 ;<=>?$''&9&/$(&)%6 0("0.0"6 Informatik Prof. Dr. Stefan Funke Prof. Dr. Stefan Funke 02.06.2017 04.12.2017 H.3.3 Institut für Formale Methoden der Informatik Universität Stuttgart Universitätsstraße 38 D - 70569 Stuttgart Abteilung Algorithmik Ich versichere, diese Arbeit selbstständig verfasst zu haben. Ich habe keine anderen als die angegebenen Quellen benutzt und alle wörtlich oder sinngemäß aus anderen Werken übernommene Aussagen als solche gekennzeichnet. Weder diese Arbeit noch wesentliche Teile daraus waren bisher Gegenstand eines anderen Prüfungsverfahrens. Ich habe diese Arbeit bisher weder teilweise noch vollständig veröffentlicht. Das elektronische Exemplar stimmt mit allen eingereichten Exemplaren überein. I hereby declare that the work presented in this thesis is entirely my own. I did not use any other sources and references that the listed ones. I have marked all direct or indirect statements from other sources contained therein as quotations. Neither this work nor significant parts of it were part of another examination procedure. I have not published this work in whole or in part before. The electronic copy is consistent with all submitted copies. !"/?"".%# Stuttgart, 4.12.2017 B. Kopf Stuttgart, 4.12.2017 B. Kopf #0+?$"$(&)% Zusammenfassung Suchmaschinen wie OSCAR liefern als Ergebnis auf eine Suchanfrage oft große Mengen unstrukturierter Daten, die für den Nutzer sehr unübersichtlich sind. In dieser Arbeit werden Algorithmen erarbeitet, welche die Organisation und interaktive Exploration solcher Ergebnismengen ermöglichen. Dabei wird anhand von anschaulichen Beispielen auf die Stärken und Schwächen der jeweiligen Vorgehensweisen eingegangen. Außerdem wird auf Probleme und Grenzen der Verfahren hingewiesen. I Inhaltsverzeichnis 1 Einleitung 1 1.1 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Verwandte Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Gliederung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Semistrukturierte Daten 3 2.1 Die Suchmaschine OSCAR . . . . . . . . . . . . . . . . . . . . 4 2.2 Die OSCAR-Query . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Vorüberlegungen 6 3.1 Das Vorbild DBLP . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Die Testfälle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Naiver Ansatz 11 4.1 Auswertung der Ergebnisse . . . . . . . . . . . . . . . . . . . . 13 5 Einbeziehung der Parents 15 5.1 Erster Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Verbesserter Algorithmus . . . . . . . . . . . . . . . . . . . . . 17 5.3 Laufzeite�zienz . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.4 Auswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6 Übertragung des Parent-Algorithmus 22 6.1 Strukturierung nach Key-Value-Paaren . . . . . . . . . . . . . 23 6.2 Strukturierung nach Keys . . . . . . . . . . . . . . . . . . . . 24 6.3 Interaktive Ergebnisse . . . . . . . . . . . . . . . . . . . . . . 24 6.4 Verbesserungen . . . . . . . . . . . . . . . . . . . . . . . . . . 26 II 7 Beispielhafte Ergebnisse 26 7.1 Beispiel 1: Supermärkte in Stuttgart . . . . . . . . . . . . . . 27 7.2 Beispiel 2: Fastfoodrestaurants in Berlin . . . . . . . . . . . . 29 8 Zusammenfassung und Ausblick 30 8.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . 30 8.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 III 1 Einleitung In der Zeit der Digitalisierung, welche immer größere Datenmengen mit sich bringt, nimmt e�zientes Suchen eine stets bedeutender werdende Stellung ein. Genauso wichtig ist aber auch eine sinnvolle und übersichtliche Anord- nung der Ergebnismenge für den Benutzer. Dafür ist es nötig, dieser eine anschauliche Struktur zu geben. Wird dabei in einer bereits strukturierten Umgebung gearbeitet, ist es vergleichsweise einfach, sinnvolle Parameter zu finden, nach denen die Ergebnisse organisiert werden können. So kann bei- spielsweise eine Suchmaschine wie DBLP1 (Ley, 2002), welche eine Daten- bank aus Journalen und Protokollen durchsucht, die Ergebnisse nach festen Parametern wie beispielsweise Autor, Publikationsjahr und Veranstaltung ordnen, da beinahe jedes Element der Datenbank diese Parameter besitzt. Seit Mitte der 90er Jahre, vor allem durch die Verbreitung des Datenfor- mats XML, gewinnt der Ansatz der schwach strukturierten Daten zunehmend an Beliebtheit. Im Gegensatz zu strukturierten Daten ist diesen schwach strukturierten Daten keine äußere Struktur anzusehen. Diese ist vielmehr in den Daten an sich enthalten. In einer solchen Umgebung kann man nur schwer Parameter festlegen, welche für die Strukturierung der Menge sinnvoll sind. Stattdessen müssen diese für jede Ergebnismenge neu ermittelt werden. Ein Beispiel dafür bietet die Suchmaschine OSCAR2 (Bahrdt und Funke, 2015), welche auf OpenStreetMap (OSM3) Daten basiert. OSCAR gibt auf eine Query eine meistens große Menge an Informationen zurück, welche ohne Struktur nur schwer erfassbar sind. 1.1 Aufgabenstellung Das Ziel dieser Arbeit ist die Entwicklung eines Algorithmus, welcher Ergeb- nismengen von OSCAR strukturiert, organisiert und schließlich übersichtlich 1http://dblp.uni-trier.de/ 2http://oscardev.fmi.uni-stuttgart.de/ 3http://openstreetmap.org/ 1 präsentiert. Als Vorbild eines guten Ergebnisses dient dabei die Suchmaschine DBLP. Das Problem bei der Organisation dieser Ergebnismengen liegt darin, dass die verschiedenen Entitäten, jeweils bestehend aus Key-Value-Paaren, oft komplett unterschiedliche Keys besitzen, auch wenn sie ähnliche Objekte beschreiben. Das macht es schwierig zu entscheiden, welche Keys und Values besonders interessant und aussagekräftig für den Benutzer sind. 1.2 Verwandte Arbeiten Da die Algorithmen in dieser Arbeit für Ergebnismengen der Suchmaschine OSCAR konzipiert sind und an solchen getestet werden, ist die Arbeit von Bahrdt und Funke (2015) die Grundlage für diese Thesis. Das Vorbild für diese Arbeit bildet die Suchmaschine der Sammlung für wissenschaftliche Publikationen DBLP (Ley, 2002). Die Suchmaschine sucht nicht nur nach Textdokumenten, sondern stellt die Ergebnisse auch, nach mehreren Kriterien strukturiert, übersichtlich dar. Besonders der Complete- Search Algorithmus von Bast und Weber (2007), auf welchem die Suchma- schine von DBLP basiert, ist dabei sehr interessant. Die E↵ektivität dieses Suchalgorithmus basiert vor allem auf der Datenstruktur HYB, welche eine verbesserte Form des invertierten Index darstellt (Bast und Weber, 2006). Eine vergleichende Studie zwischen den semistrukturierten Datenforma- ten JSON und XML führten Nurseitov et al. (2009) durch. In dieser Arbeit werden Stärken und Schwächen der jeweiligen Datenformate herausgestellt. 1.3 Gliederung In Kapitel 2 wird zunächst eine Einführung in die semistrukturierten Daten gegeben, gefolgt von der Betrachtung der explizit vorhandenen Datensätze, mit denen gearbeitet wird. 2 Als nächstes beschreibt Kapitel 3 die Ziele dieser Arbeit und stellt erste Vermutungen über mögliche Ergebnisse auf. Außerdem werden die gewählten Testsätze vorgestellt. In Kapitel 4 wird eine erste Idee für einen Algorithmus vorgestellt und analysiert. Kapitel 5 befasst sich damit, wie die Parents der OSCAR-Daten sinnvoll genutzt werden können. Dazu wird ein weiterer Algorithmus entwickelt und vorgestellt. Dieser Algorithmus wird in Kapitel 6 auch auf die Keys und Values über- tragen und den anderen Umständen angepasst und erweitert. In Kapitel 7 findet eine Darstellung der Funktionsweise des Algorithmus anhand von mehreren Beispielen, sowie die Bewertung der verschiedenen Er- gebnisse statt. Zuletzt liefert Kapitel 8 eine Zusammenfassung der Arbeit und spricht Möglichkeiten an, die Arbeit fortzuführen. 2 Semistrukturierte Daten Die immer größer werdenden Mengen an Daten machten es in der Vergan- genheit immer schwerer diesen eine strukturierte Form zu geben. Ein fest- gelegtes Datenschema scheint oft zu restriktiv, weshalb der Ansatz der se- mistrukturierten Daten seit Mitte der 90er Jahre immer populärer wird (Bry et al., 2001). Anstatt die Daten einer Struktur anzupassen, ist die Struk- tur laut Bry et al. (2001) in den semistrukturierten Datensätzen enthalten, was sie selbsterklärend machen soll. Ein großes Anwendungsgebiet finden die semistrukturierten Daten beispielsweise durch XML (eXtensible Markup Language) (Goldman et al., 1999). Die XML Daten bestehen laut Goldman et al. (1999) aus verschiedenen Elementen, welche jeweils aus Attribut-Wert- Paaren bestehen, sowie gegebenenfalls aus einer Menge an Subelementen. 3 Eine andere Datenaustauschsprache ist JSON (JavaScript Object Notation). Diese legt nach Nurseitov et al. (2009) besonderen Wert darauf, sowohl für Menschen als auch Computer, leicht lesbar zu sein. Wie bei XML liegen auch bei JSON die Daten in Form von Objekten vor, welche aus Key-Value-Paaren bestehen. Abbildung 1: Vergleich der Darstellung eines einfachen Objektes in JSON (links) und XML (rechts). (Nurseitov et al., 2009) Abbildung 1 zeigt beispielhaft wie das Objekt bestehend aus dem Vorna- men John und dem Nachnamen Smith in JSON und XML dargestellt werden könnte. 2.1 Die Suchmaschine OSCAR Die für diese Arbeit zu strukturierenden Daten kommen von der Suchma- schine OSCAR von Bahrdt und Funke (2015). Diese beruht auf Daten von dem Geodatenprojekt OpenStreetMap (OSM), bei der alle Objekte aus Key- Value-Paaren bestehen. Die OSCAR-Suchmaschine gibt als Antwort auf eine Query die gefundenen OSM-Objekte, mit passenden Tags, als JSON-Datei zurück. Die einzelnen Objekte sind dabei in einem Array aufgelistet und können wie folgt aussehen: ”id”:35367421 ”osmid”:1202732923 ”type”:”node” 4 ”score”:20 ”bbox”:[48.816382,48.816382,9.4200821,9.4200821] ”shape”:”t”:-1 ”k”:[”addr:city”,”addr:housenumber”,”addr:postcode”,”addr:street”, ”ame- nity”,”name”,”opening hours”,”phone”,”phone 1”,”wheelchair”] ”v”:[”Remshalden”,”7”,”73630”,”Schorndorfer Straße”,”fast food”,”Babylon Döner”,”Mo-Sa 11:00-22:00; Su 12:00-22:00”,”+49 7151 9753794”,”+49 7151 2711421”,”yes”] ”p”:[188490,22072,5734,538,64] Dabei steht links immer der Key und rechts von dem Doppelpunkt der da- zugehrige Value. Die eigentlichen Key-Value-Paare von OSM sind dabei in zwei Arrays gespeichert, wobei beispielsweise zu dem ersten Key im ”k” Ar- ray der erste Value des ”v” Arrays gehört. In diesem Beispiel also ”ad- dr:city”:”Remshalden”. Von jedem Objekt benötigt man außer den Keys mit den dazugehörigen Values noch eine der beiden ids, mit denen die Objekte später leicht von einander unterschieden werden können, sowie das Array der Parents ”p”. Da sowohl die von OSM vergebene ”osmid” als auch die von OSCAR neu vergebene ”id” eindeutig sind, ist es irrelevant welche der beiden verwendet wird. Für diese Arbeit wurde deswegen immer die von OSCAR vergebene ”id” verwendet, da diese auch für die Parentbeziehungen genutzt werden. In dem Array der Parents sind die ids der Regionen in welchen sich das aktuelle Objekt befindet, hinterlegt. Laut Bahrdt und Funke (2015) ist diese Parentstruktur als DAG (directed acyclic graph) aufgebaut. So befindet sich der Babylon Döner aus dem obigen Beispiel in Deutschland, welches die id 64 besitzt und deswegen im Parrent Array aufgeführt ist. Damit können relativ einfach die lokalen Beziehungen zwischen den verschiedenen Objekten festgestellt werden. 5 2.2 Die OSCAR-Query Bahrdt und Funke (2015) entwarfen die Query Sprache für OSCAR mengen- basiert. Während ein einzelnes Suchwort natürlich alle Objekte mit diesem Wort als String oder Substring in dessen Keys oder Values findet, erhält der Nutzer bei zwei durch Leerzeichen voneinander getrennten Worten in der Query, die Schnittmenge der beiden einzelnen Querys als Ergebnis. Eine Vereinigung der Ergebnismengen erreicht man mit einem ’+’ zwischen den beiden Worten, mit einem ’-’ die Di↵erenz. Nach einem bestimmten Key in den Objekten kann mit ’@’ gesucht werden und mit ’@key:value’ nach einem expliziten Key-Value-Paar. Möchte man nun zum Beispiel mit der Query Stuttgart @amenity:fast food nach Fastfoodrestaurants in Stuttgart suchen fällt auf, dass auch einige Tref- fer außerhalb von Stuttgart und sogar ein Tre↵er in Leipzig gefunden wer- den. Das liegt laut Bahrdt und Funke (2015) daran, dass die Ergebnisse in einem größeren administrativen Bereich, dem Regierungsbezirk Stuttgart lie- gen, welcher natürlich den Substring Stuttgart enthält. Ebenso verhält es sich mit dem Tre↵er in Leipzig, welcher in der Stuttgarter Allee liegt. Um das zu verhindern kann der Nutzer mit Anführungszeichen einen exakten, nicht Substring Tre↵er forcieren: ”Stuttgart” @amenity:fast food 3 Vorüberlegungen Angestrebt wird ein Algorithmus, der in möglichst kurzer Zeit alle von einer OSCAR-Query gefundenen Objekte in eine sinnvolle Struktur bringt. Als Vorbild, wie eine sinnvolle Struktur aussehen kann, dient für diese Arbeit wie bereits erwähnt die Datenbank für wissenschaftliche Publikationen DBLP (Ley, 2002). 6 3.1 Das Vorbild DBLP Das Digital Bibliography and Library Project kurz DBLP startete laut Ley (2009) im Jahre 1993 und hat sich seitdem zu einem beliebten Service für wis- senschaftliche Publikationen entwickelt. Die einzelnen Objekte sind in Form einer XML-Datenbank gespeichert, wobei als Vorbild BIBTEX dient (Ley, 2009). Die Objekte sollen deswegen falls möglich Felder wie Autor, Titel, Seiten und Jahr enthalten, doch nur das Element Titel muss tatsächlich in jedem DBLP Eintrag enthalten sein (Ley, 2009). Die Suchmaschine von DBLP basiert auf dem CompleteSearch Algorith- mus von Bast und Weber (2007). Neben den ersten Ergebnissen auf die Suchanfrage stellt die Suchmaschine auch eine strukturierte Übersicht dar, mit der die Ergebnismenge verfeinert werden kann. In Abbildung 2 ist diese Struktur für die Suchanfrage Stefan Funke abgebildet. Da die Publikationen nach denen dabei gesucht wird sehr ähnlich aufge- baut sind, kann man gewisse Attribute nach denen das Ergebnis strukturiert werden soll, im Voraus festlegen. So werden die Publikationen nach jeder Query in Kategorien wie Autor, Erscheinungsdatum und so weiter aufgelis- tet. Bei den Ergebnissen von Suchanfragen an OSCAR ist das jedoch nicht ohne weiteres möglich, weil verschiedene Objekte auch komplett verschiedene Keys haben können. Deswegen muss der entstehende Algorithmus während der Laufzeit geeignete Attribute zur Strukturierung finden. Somit ist das Feststellen geeigneter strukturgebender Elemente ein wichtiger Bestandteil den der Algorithmus bewältigen muss. 3.2 Die Testfälle Als erste Testfälle, auf welchen die Funktionalität des entwickelten Algo- rithmus geprüft werden soll, dienen die OSCAR-Anfragen Döner und Waib- lingen. Diese beiden Querys eignen sich aufgrund der Unterschiede in den jeweiligen Ergebnismengen. Die Ergebnisse auf die Suchanfrage Döner sind, 7 Abbildung 2: Strukturierte Ergebnisse der DBLP Suchmaschine bei der Que- ry Stefan Funke. (09.2017) wie in Abbildung 3 gezeigt, in (und vereinzelt auch außerhalb von) Europa verteilt. Die meisten Ergebnisse befinden sich zwar in Deutschland, sind aber auch dort relativ gleichmäßig auf die verschiedenen Bundesländer aufgeteilt. Außerdem ist zu erwarten, dass die Objekte, die von dieser Query zurückge- geben werden, alle sehr ähnlich sind, da es sich zum größten Teil um Fastfoo- dresaurants handeln sollten. Auf der anderen Seite befinden sich die Ergeb- nisse der QueryWaiblingen, wie in Abbildung 4 gezeigt, nahezu ausschließlich 8 Abbildung 3: Ausschnitt der Ausgabe von OSCAR bei Suchanfrage Döner. (09.2017) in Deutschland im Rems-Murr-Kreis, in welchem sich die Stadt Waiblingen befindet. Des Weiteren ist zu erwarten, dass die Tre↵er der Anfrage aus sehr unterschiedlichen Objekten bestehen, da nicht nach einer bestimmten Art Objekt, sondern nach allen Objekten in einer bestimmten Region gesucht wird. Den Vergleich der beiden Querys zeigt Tabelle 1 im Detail. Dabei sieht man deutlich die größere räumliche Verteilung der Ergebnismenge der Que- ry Döner anhand der deutlich größeren Menge an vorkommenden Parents, sowie die höhere Vielfalt in der Ergebnismenge der Query Waiblingen, durch die größere Anzahl verschiedener Keys und Values. 9 Abbildung 4: Ausschnitt der Ausgabe von OSCAR bei Suchanfrage Waiblin- gen. (09.2017) Query Döner Waiblingen Objekte 3.161 748.451 verschiedene Parents 3.795 52 verschiedene Keys 219 827 verschiedene Values 6.221 19.495 Lage der Objekte verteilt konzentriert Art der Objekte ähnlich verschieden Tabelle 1: Vergleich der OSCAR-Querys Döner und Waiblingen. Die Ähnlichkeit der Objekte der Query Döner lässt vermuten, dass die Strukturierung dieser Ergebnisse schwierig ausfallen wird, da es, wenn über- haupt, nur wenige Merkmale geben wird, die Objekte zu unterscheiden. Die Ergebnisse der Query Waiblingen sollten dagegen deutlich vielseitigere und interessantere Lösungen bieten, da die sehr unterschiedlichen Objekte anhand von einigen Kriterien strukturierbar sein sollten. 10 4 Naiver Ansatz Als erste Idee sollten möglichst sinnvolle Keys in der Ergebnismenge gefun- den werden, nach welchen die Objekte strukturiert werden können. Nach diesen Keys soll das Ergebnis dann anschaulich, wie bei der Suchmaschine DBLP in Abbildung 2, dargestellt werden. Dabei wurde das Problem wie folgt angegangen: 1. Bestimmung aller in der Ergebnismenge vorkommenden Key-Value-Paare. 2. Evaluation der Relevanz der Keys. 3. Strukturieren nach den relevanten Keys. 1. Bestimmung aller in der Ergebnismenge vorkommenden Key- Value-Paare Dazu werden die Key-Value-Paare der von der Query gefundenen Objek- te einmal durchgegangen. Dabei wird, wie in Abbildung 5 dargestellt, eine zweidimensionale Hashmap erzeugt, wobei die äußere Map alle vorkommen- den Keys als Keys bekommt und eine innere Hashmap als Value. Die innere Map bekommt als Keys alle Values, die zu dem Key in der Ergebnismenge vorkommen, und als Value die Anzahl, wie oft dieses Key-Value-Paar in der Menge erscheint als Integer. 2. Evaluation der Relevanz der Keys Zunächst sollen nur Keys zugelassen werden, welche auch bei einer möglichst großen Menge an Objekten vorkommen. Deswegen werden nur Keys in Be- tracht gezogen, die in mindestens zehn Prozent der Objekte erscheinen. Ge- nauso ist es auch nicht sinnvoll alle Values des Keys aufzuführen, sondern lediglich solche, die oft genug erscheinen. Deswegen werden alle Values, die weniger als ein Prozent des Keys ausmachen als others zusammengefasst. In Abbildung 6 kann man sehen, wie dann zum Beispiel die Strukturierung nach 11 Abbildung 5: Aufbau der zweidimensionalen Hashmap. Abbildung 6: Ausschnitt der Ergebnisse der Query Döner nach Vorbild von DBLP. dem Key addr:city bei Query Döner aussehen würde. Dieser Key kommt ins- gesamt bei 914 der 3161 betrachteten Objekten vor, 25 mal davon mit dem Value Berlin. Es werden insgesamt nur sieben der 561 Values angegeben, da nur diese mindestens zehn mal vorkommen. Die meisten der Values erschei- nen sogar nur ein mal. Von den so gefundenen Keys sind jedoch immer noch nicht alle sinnvoll. Es werden zuletzt noch alle ausgeschlossen, bei denen alle Objekte den gleichen Value haben oder aber jeder Value so selten ist, dass alle Values zu others 12 zusammengefasst werden würden. 3. Strukturieren nach den relevanten Keys Die Keys, die dann noch übrig sind, werden nach Häufigkeit geordnet und danach wie in Abbildung 6 gezeigt dargestellt. 4.1 Auswertung der Ergebnisse Abbildung 7: Anschaulich dargestellte Ergebnisse der Query Döner. In den Abbildungen 7 und 8 sieht man eine anschauliche Anordnung der Ergebnisse des naiven Algorithmus bei Eingabe der beiden Testquerys. 13 Abbildung 8: Anschaulich dargestellte Ergebnisse der Query Waiblingen. Visuell ähnelt die Darstellung schon sehr der von DBLP, die Qualität der Ergebnisse muss aber noch geprüft werden. Es wurden für die Query Waiblingen sieben und für die Query Döner neun Keys als relevant eingestuft. Diese Zahlen sind in Ordnung, bewegen sich aber an der Obergrenze dessen was erwünscht ist. Um eine möglichst große Übersicht zu gewährleisten werden fünf bis sieben Attribute zur Struk- turierung angestrebt. Von den gefundenen Keys sieht vor allem der addr:city Key sinnvoll aus, da hier die Tre↵er nach Ortschaften getrennt werden. Der Key addr:postcode hat quasi die selbe Funktion, weshalb nicht unbedingt 14 beide nötig wären. Es erscheint jedoch nicht besonders sinnvoll den Key addr:country, wie in Abbildung 7 gezeigt, separat darzustellen. Sinnvoller wäre es die Lokalitätseigenschaften der Objekte in einem Punkt darzustel- len, was in Kapitel 5 weiter verfolgt wird. Sehr wenig Aussagekraft hat der Key addr:housenumber. Es ist aber durchaus o↵ensichtlich, warum der Key erscheint. Das liegt daran, dass er einige Values mit relativ ähnlicher Häufig- keit besitzt, was eigentlich genau das ist, wonach gesucht wurde. Bei manchen Keys wie beispielsweise building ist die Unterscheidung in die einzelnen Va- lues nicht besonders sinnvoll, insbesondere da der am Öftesten vorkommende Value yes ist. Hier würde vermutlich die Unterteilung in Objekte, die diesen Key haben und Objekte, die ihn nicht haben, genügen. Dies ist aber schwer dynamisch umzusetzen, da die Unterscheidung in die einzelnen Values zum Beispiel bei Key wheelchair sehr wichtig ist. Alles in allem ist der erste Eindruck aber doch zufriedenstellend und zeigt, an welchen Stellen noch verbessert werden muss. 5 Einbeziehung der Parents In diesem Kapitel wird, wie schon in Kapitel 4.1 angedeutet, nach einer gu- ten Möglichkeit gesucht, die lokale Organisation der Objekte mit Hilfe der Parents zu erreichen. Das bietet sich an, da die OSCAR Objekte durch die Parent Beziehungen in einem DAG (Directed Acyclic Graph) angeordnet sind (Bahrdt und Funke, 2015). Durch diese Struktur können beispielsweise leicht alle Objekte die in Deutschland liegen aus der Ergebnismenge gefil- tert werden, indem man alle Objekte wählt, welche die Id von dem Objekt Deutschland (also 64) in ihrem Parent Array haben. Auch hier stellt sich wieder die Frage, wie die Objekte organisiert wer- den sollen. Betrachtet man die Query Döner scheint es sinnvoll die Objekte nach den verschiedenen Ländern in denen sie liegen zu trennen. Eine Aus- nahme dazu bilden die Objekte in Deutschland. Da dort mit Abstand der 15 größte Teil liegt, sollten diese noch in die Bundesländer unterteilt werden. An diesem Beispiel sieht man, dass auch die Wahl der Parents, nach denen später geordnet werden soll, dynamisch stattfinden muss, um ein sinnvolles Ergebnis zu erhalten. 5.1 Erster Ansatz Zunächst einmal sollen zwei besonders geeignete Parents gefunden werden. Dazu soll jedem Paar aus zwei verschiedenen Parents Pi und Pj ein Wert wi,j zugewiesen werden, der angibt wie geeignet dieses Paar als erste Parents sind. Das Paar mit dem größten Wert wird danach gewählt. Dafür betrachten wir die Parents als Mengen, wobei jedes Objekt, welches einen bestimmten Parent besitzt, ein Element der Menge darstellt. Da die Parents möglichst groß und verschieden sein sollen ist die nahelie- gende Idee: wi,j = |Pi [ Pj|� |Pi \ Pj| Also die Di↵erenz zwischen Kardinalität der Vereinigung und Kardinalität des Schnitts der beiden Mengen. Ein o↵ensichtliches Problem bei diesem Ansatz ist, dass für die beiden Parents Pi und Pj mit dem größten Wert wi,j Pi ⇢ Pj möglich ist, wenn alle Objekte in Pj liegen und |Pi| minimal ist. Da man grundsätzlich disjunkte Mengen als Ergebnis möchte, ist es sinnvoll die Bedingung |Pi \ Pj| = 0 hinzuzufügen. Bei näherem Betrachten ist es auch nicht gut, die Vereinigungen zu bewerten, da so eine extrem große und eine kleine Menge gewählt werden können. Es sollen aber beide Mengen möglichst groß sein. Aus diesen Überlegungen folgt: wi,j = 8 < : min {|Pi|, |Pj|} falls |Pi \ Pj| = 0 0 sonst Anschließend werden die Paare nach den Werten sortiert und die beiden Parents des Paares mit dem höchsten Wert werden als Startparents gewählt. 16 Dieses Verfahren wählt für die Query Döner Nordrhein-Westfalen und Bayern sowieVereinbarte Verwaltungsgemeinschaft der Stadt Schorndorf und Gemeindeverwaltungsverband Winnenden für Waiblingen. Dabei sieht man, dass sich die Ergebnisse von Döner auf Bundesländerebene und die vonWaib- lingen auf Städteebene befinden, was den oben beschriebenen, gewünschten Resultaten entspricht. Als nächstes müssen die restlichen relevanten Parents gefunden werden. Dazu werden in absteigender Reihenfolge die verbliebenen Paare betrachtet. Ist ein Partner bereits in der Liste der gewählten Parents, wird der andere Partner der Liste hinzugefügt. Sind beide Partner nicht in der Liste, wird der Algorithmus beendet. Dieser Ansatz ist nicht besonders gut, da dadurch wieder Überschneidungen in der Ergebnismenge vorkommen können. Für die Query Döner wählt der Algorithmus beispielsweise die Türkei, da sie mit Bayern keinen Schnitt hat und Bayern bereits bei den Startparents enthalten ist. Da aber Deutschland ebenfalls keinen Schnitt mit der Türkei hat, werden schließlich sowohl Deutschland als auch Bayern für die Ergebnisliste gewählt. Da genau das vermieden werden sollte, da PBayern ⇢ PDeutschland ist, muss das Verfahren noch verbessert werden. 5.2 Verbesserter Algorithmus Die Auswahl der ersten beiden Parents hat im ersten Ansatz zwar gut funk- tioniert, ist aber sehr aufwendig. Bei n Parents werden dafür ⇣ n 2 ⌘ Schnittmen- gen gebildet. Deutlich e�zienter ist es, zuerst die Parents nach Häufigkeit zu sortieren. Somit werden nur n Entitäten sortiert, anstelle von ⇣ n 2 ⌘ im ersten Algorithmus. Danach wird der Schnitt der beiden häufigsten Parents gebil- det. Ist er disjunkt werden diese Parents als Startparents gewählt. Ansonsten werden die nächsten Parents betrachtet, und zwar so lange bis ein Paar mit disjunktem Schnitt gefunden wird, welches dann gewählt wird. In dem fol- genden Pseudocode wird dieses Verfahren nochmal übersichtlich dargestellt: 17 for i = 2 to n do for j = 1 to i� 1 do if |Pi \ Pj| = 0 then add Pi, Pj to resultlist end algorithm end if end for end for Dieser Pseudocode berechnet im worst case wiederum ⇣ n 2 ⌘ Schnittmen- gen. Dieser tritt aber nur ein, wenn die beiden kleinsten Parents die einzigen mit disjunktem Schnitt sind, oder wenn alle Parentmengen mindestens ein Element mit den anderen Mengen gemeinsam haben. Diese beiden Fälle tre- ten jedoch nur auf, wenn in OSCAR nach einer bestimmten Region gesucht wird, oder nur ganz wenige Suchergebnisse erzielt werden. In beiden Fällen ist die Ergebnisorganisation nach Lokalität nicht besonders sinnvoll. In jedem anderen Fall sind deutlich weniger Schnittmengen nötig als bei dem ersten Ansatz. Bei dem zweiten Teil des Algorithmus ist das Problem, dass durch das Auswahlverfahren Parents in die Ergebnisliste kommen können, welche Teil- mengen von anderen Parents in dieser Liste sind, was natürlich unerwünscht ist. Um das zu verhindern muss, bei der Abwägung ob ein neuer Parent zur Liste hinzugefügt wird, dieser mit allen anderen Parents verglichen werden. Da durch den ersten Teil bereits eine sortierte Liste der Parents vorliegt ist es sinnvoll, diese weiter zu nutzen. Beginnen kann man dabei mit dem Parent dessen Index i+ 1 ist, wobei das i aus dem vorigen Teil des Algorithmus ist, da die anderen Parents bereits ausgeschlossen wurden. Nun wird von diesem Parent an geprüft, ob der Parent mit jedem Parent der Liste einen disjunkten Schnitt hat. Ist dies der Fall wird der Parent gewählt und der Ergebnisliste hinzugefügt. Ansonsten wird er verworfen. 18 for k = i+ 1 to n do for l : Pl 2 resultlist do if |Pk \ Pl| 6= 0 then discard Pk end if end for if Pk is not discarded then add Pk to resultlist end if end for Da Parents, welche nur bei sehr wenigen Objekten vorkommen nicht inter- essant sind, kann der Algorithmus vorzeitig abgebrochen werden, wenn eine bestimmte Anzahl an Vorkommen nicht mehr erreicht wird. Die Parents, die bei weniger als einem Prozent der Objekte vorkommen werden deswegen nicht berücksichtigt um unnötige Rechenzeit zu sparen. 5.3 Laufzeite�zienz Eine Obergrenze für sowohl den ersten, als auch den verbesserten Ansatz des Parents-Algorithmus sind n2 Schnittmengen, die bei n Parents gebildet werden müssen. Wegen dieser großen Zahl an Schnittmengen ist es notwendig, dass diese so wenig Rechenzeit beanspruchen wie möglich. Dazu stellt Java die Methode set1.retainAll(set2) im Interface Set zur Verfügung. Diese prüft der Reihe nach für jedes Element der Menge set1, ob dieses auch in set2 enthalten ist. Falls nicht, wird es aus set1 entfernt. Für n = |set1| und m = |set2| liegt die Laufzeit dieses Verfahrens in O(n · m). Es benötigt also quadratische Laufzeit für n ⇡ m. Um eine schnellere Schnittmengenberechnung implementieren zu können ist eine andere Datenstruktur sinnvoll, wie die von Bast und Weber (2007) 19 vorgestellte Datenstruktur HYB. Dazu wird ein Array aus Tupeln verwen- det, welches alle Objekt-Parent Paare enthält. Das erste Element des Tupels beinhaltet dabei die ID des Parent und das zweite Element die ID des da- zu gehörigen Objekts. Dieses Array wird dann aufsteigend nach dem ersten Element sortiert, wobei bei identischen Parents als zweites Kriterium nach dem zweiten Element sortiert wird. Als Beispiel werden die Objekte A, B, C und D mit Parents 0 bis 9 und folgender Verteilung betrachtet: A : 0, 3, 4, 7, 8 B : 1, 2, 3, 4, 5 C : 6, 9 D : 0, 2, 7, 9 Dann sähen die sortierten Tupel folgendermaßen aus: 0 0 1 2 2 3 3 4 4 5 6 7 7 8 9 9 A D B B D A B A B B C A D A C D Um e�zient auf bestimmte Parents zugreifen zu können wird außerdem ein O↵set-Array benötigt, welches an Stelle i den Index des ursprünglichen Arrays hat, an welchem die Einträge mit Parent i beginnen. Für das obige Beispiel sähe das O↵set-Array wie folgt aus: [0, 2, 3, 5, 7, 9, 10, 11, 13, 14] Mit Hilfe dieser Arrays können nun relativ schnell Schnittmengen zweier Parents bestimmt werden, da die Einträge sortiert vorliegen. Dafür wird zunächst von beiden Parents das erste Objekt (also das mit der kleinsten ID) betrachtet. Sind die Objekte identisch, wird ein Zähler, der die Schnittgröße zählt um eins erhöht und die nächsten beiden Objekte werden verglichen. Sind die Objekte verschieden, wird von dem Parent mit dem kleineren Ob- jekt das nächst größere als nächstes betrachtet. Sobald bei einem der beiden Parents das Ende erreicht ist und das nächste Element betrachtet werden soll, wird der Algorithmus beendet. 20 Zum besseren Verständnis dieses Algorithmus wird in Tabelle 2 der Schnitt zwischen zwei Parents gezeigt. Dabei sind die aktuell betrachteten Zahlen markiert. Schritt 1 Schritt 2 Schritt 3 Schritt 4 Schritt 5 Parent 1 [1, 3, 6, 8] [1, 3, 6, 8] [1, 3, 6, 8] [1, 3, 6, 8] [1, 3, 6, 8] Parent 2 [3, 4, 5, 6] [3, 4, 5, 6] [3, 4, 5, 6] [3, 4, 5, 6] [3, 4, 5, 6] Zähler 0 1 1 1 2 Tabelle 2: Algorithmus zur Bestimmung der Schnittmengen beispielhaft dar- gestellt. Da jede der beiden Listen bei diesem Algorithmus nur einmal durchlaufen wird, hat dieser die Laufzeitschranke O(n+m). Er läuft also in linearer Zeit, was eine deutliche Verbesserung zur quadratischen Laufzeit darstellt. 5.4 Auswertung In Abbildung 9 sind die Ergebnisse des oben beschriebenen Algorithmus dar- gestellt. Wie in Kapitel 5 bereits genannt, war das Ziel einige repräsentative Parents zu finden, welche untereinander disjunkt sind und eine ähnliche Men- ge an Objekten beinhalten. Für die Query Döner war dabei erwünscht, dass in Deutschland nach Bundesländern getrennt wird. Andere Länder sollten nicht weiter aufgeteilt werden, was von dem Algorithmus auch umgesetzt wurde. Bei der Query Waiblingen ist das nicht sinnvoll, da so gut wie al- le Objekte in Baden-Württemberg liegen. Wie man sieht wurde hier nach verschiedenen Städten getrennt. Die Ergebnisse, die der Algorithmus liefert sind also wie erwartet und gewünscht. Er ist deswegen für die Einteilung der Ergebnismenge einer OSCAR- Query nach geographischer Lage sehr sinnvoll. 21 Abbildung 9: Ergebnisse des Parent-Algorithmus für die OSCAR-Querys Döner und Waiblingen. 6 Übertragung des Parent-Algorithmus Da der Parent-Algorithmus aus Kapitel 5 erstaunlich gute Ergebnisse liefert wird er in diesem Kapitel auf die Keys und Values übertragen, um abzuwägen ob ähnlich gute Ergebnisse erzielt werden können. Dabei wird in Kapitel 6.1 untersucht, wie gut sich der Algorithmus eignet, um relevante Key-Value- Paare zu finden. In dem Kapitel 6.2 werden dagegen lediglich relevante Keys gesucht. Da die Keys und Values aber im Gegensatz zu den Parents komplett semistrukturiert vorliegen, wird die Restriktion bei der Bildung der Schnitt- mengen wesentlich gelockert. Anstelle eines komplett disjunkten Schnittes wird lediglich gefordert, dass |Pi \ Pj|  (|Pi| + |Pj|)/200 gilt. Das ist sinn- voll, da Objekte einen bestimmten Key besitzen können, der gar nicht zu ihnen passt, zum Beispiel mit Value no. Außerdem soll dadurch erschwert 22 werden, dass ein einziger Key bei der Key-Value Strukturierung die anderen komplett verdrängt, da der Schnitt der verschiedenen Values des Keys fast immer disjunkt ist. Dieses Problem kann dadurch dennoch nicht komplett ausgeschlossen werden, wie man in Abbilung 10 sieht. 6.1 Strukturierung nach Key-Value-Paaren Abbildung 10: Ergebnisse des Algorithmus für die OSCAR-Querys Döner und Waiblingen bei Betrachtung der Key-Value-Paare. In Abbildung 10 sind die Ergebnisse des Algorithmus bei der Suche nach geeigneten Key-Value-Paaren dargestellt. Bei der Query Döner wurde da- bei lediglich nach den verschiedenen Values des Keys wheelchair getrennt. Da die Ergebnisse, wie in Kapitel 3.2 beschrieben, sehr ähnlich sind, da es sich immer um Döner Imbisse handelt, ist es jedoch auch schwierig bestimm- te Trennungsmerkmale zu finden. Als Resultat wird ein Key herausgesucht, der zwei möglichst häufige Values hat, was eigentlich dem Vorgehen des ur- sprünglichem Algorithmus aus Kapitel 4 ähnelt. Durch die Heterogenität der Ergebnismenge der Query Waiblingen fin- det der Algorithmus deutlich mehr geeignete Key-Value-Paare. Einen großen Teil nehmen die Keys highway und building ein, da beide sehr oft vorkom- men und quasi keine Überschneidungen haben. Trotzdem konnten noch drei 23 andere Key-Value-Paare dazu gefunden werden, was das Ergebnis sehr zu- friedenstellend macht. 6.2 Strukturierung nach Keys Abbildung 11: Ergebnisse des Algorithmus für die OSCAR-Querys Döner und Waiblingen bei Betrachtung der Keys. Abbildung 11 zeigt, wie bereits in Kapitel 6.1 angesprochen, wie schwierig es ist Keys mit kleinen Schnittmengen für die Query Döner zu finden, da die gefundenen Objekte so ähnlich sind. Deswegen wurden durch den Algorith- mus lediglich drei Keys, die selten vorkommen, gefunden. Dass es durchaus häufigere Keys gibt sieht man beispielsweise in Abbildung 7. Für eine Query, die mehrere verschiedene Objekte liefert, wie beispiels- weise Waiblingen, können dagegen mehrere große Keys gefunden werden. Abbildung 8 zeigt, dass mit building und highway direkt die beiden größten, vom ersten Algorithmus als relevant betrachteten, Keys gewählt werden. 6.3 Interaktive Ergebnisse Obwohl die Ergebnisse des Algorithmus bei der Suche nach interessanten Keys beziehungsweise Key-Value-Paaren stellenweise gut gelungen sind, sind noch Verbesserungsmöglichkeiten vorhanden. Deswegen wird in diesem Kapi- tel eine interaktive Ergebnisfindung vorgestellt. Dies ist sinnvoll, da manche Ergebnisse ausgeschlossen werden sollen, beispielsweise weil sie für den Nut- zer nicht relevant oder interessant sind. Außerdem sind Keys, die Lokalitäten 24 angeben (wie addr:city oder addr:postcode) nicht erwünscht, da diese deutlich präziser mit dem Parent-Algorithmus von Kapitel 5 gefunden werden können. Der Algorithmus soll jedoch möglichst dynamisch und vielseitig anwendbar gehalten werden und deswegen werden keine Keys explizit ausgeschlossen. Aus diesem Grund wird dem Nutzer die Möglichkeit zur Verfügung gestellt, nach Abschluss des Algorithmus eine oder mehrere der gefundenen Lösungen auszuschließen und ihn anschließend neu zu starten. Dieser Vorgang kann mehrmals wiederholt werden, bis das Ergebnis zufriedenstellend ist. Abbildung 12: Interaktive Exploration der Ergebnisse der Query Döner. Abbildung 13: Interaktive Exploration der Ergebnisse der Query Waiblingen. Die Abbildungen 12 und 13 zeigen beispielhaft den interaktiven Umgang mit den Ergebnissen. In beiden Fällen werden nach repräsentativen Key- Value-Paaren gesucht. Dabei sind immer die Paare, die nach dem jeweiligen Schritt ausgeschlossen werden rot markiert. Au↵allend ist dabei, dass es den- noch schwierig ist für die Query Döner ein Ergebnis zu finden, welches nicht 25 von einem bestimmten Key dominiert wird. Bei der Query Waiblingen er- scheinen dagegen immer neue Keys, wie zum Beispiel addr:postcode, tracktype und source in Schritt 2. 6.4 Verbesserungen Zum Ende der Arbeit wurden noch einige kleine Veränderungen an dem Quellcode des Algorithmus vorgenommen, um das Arbeiten damit angeneh- mer und intuitiver zu gestalten: Sortieren der Ergebnisse nach Häufigkeit Zur besseren Übersicht über die erzielten Ergebnisse werden diese nach Häufig- keit geordnet. Das ist intuitiver und entspricht dem Vorbild von DBLP, wie man beispielsweise an Abbildung 2 sehen kann. Abfangen von OSCAR-Querys ohne Tre↵er Das Eingeben einer OSCAR-Query, welche keine Tre↵er in der OSCAR- Suchmaschine erzielt, da sie zum Beispiel einen Schreibfehler enthält, wirft nicht länger eine Nullpointer Exception. Stattdessen wird der Benutzer dar- auf hingewiesen und erhält die Möglichkeit die Query erneut einzugeben. Anzeigen der Ergebnisse in OSCAR Ist der Benutzer mit den gefundenen Ergebnissen zufrieden, hat er nun die Möglichkeit diese mit dem Befehl show gefolgt von der gewünschten Zei- lennummer anzeigen zu lassen. Daraufhin ö↵net das Programm OSCAR in einem Browser und zeigt die gewählten Ergebnisse an. 7 Beispielhafte Ergebnisse In diesem Kapitel wird die Arbeitsweise des Algorithmus, welcher in den Kapiteln 5 und 6 erarbeitet wurde anhand von zwei anschaulichen Beispie- len gezeigt. Dabei werden die von der Query erhaltenen Daten nach Key- 26 Value-Paaren strukturiert, da diese vermutlich für die meisten Nutzer am interessantesten ist. 7.1 Beispiel 1: Supermärkte in Stuttgart Dieses Beispiel betrachtet die Suche nach Supermärkten in Stuttgart, mit der Query Stuttgart @shop:supermarket. OSCAR liefert also Ergebnisse, die den Key shop mit dem Value supermarket besitzen und den Substring Stutt- gart enthalten, was bedeutet, dass die Objekte auch außerhalb von Stuttgart, zum Beispiel im deutlich größeren Regierungsbezirk Stuttgart liegen können (Bahrdt und Funke, 2015). Nach dem ersten Durchlauf des Algorithmus wer- den folgende Ergebnisse gefunden: 0 wheelchair: yes - 849 1 wheelchair: limited - 149 2 wheelchair: no - 29 Da in diesem Beispiel nach Supermärkten gesucht wird und die Rollstuhl- tauglichkeit für den Benutzer nicht relevant ist, werden die drei Key-Value- Paare ausgeschlossen und der Algorithmus wird neu gestartet. Nach dem zweiten Durchlauf liefert er folgende Ergebnisse: 0 name: Lidl - 155 1 name: Netto - 109 2 name: Edeka - 77 3 name: REWE - 71 4 name: Penny - 65 5 name: Rewe - 56 6 name: Norma - 56 7 name: Kaufland - 54 8 name: Aldi Süd - 51 9 organic: only - 46 10 name: Aldi - 46 11 name: ALDI SÜD - 26 27 12 name: LIDL - 17 13 name: Netto Marken-Discount - 17 14 organic: yes - 16 15 name: Penny Markt - 15 16 name: EDEKA - 14 Nach dem zweiten Durchlauf liefert der Algorithmus eine Strukturierung in die verschiedenen Supermarktketten, was ein gewünschtes Ergebnis für die Query darstellt. Außerdem werden durch den Key organic Läden gezeigt, wel- che auch oder ausschließlich Bioprodukte anbieten. Nun kann der Benutzer zum Beispiel mit show 2 die Filialen der Kette Edeka anzeigen lassen. Da- durch wird ein Browserfenster geö↵net, in welchem die Ergebnisse in OSCAR angezeigt werden. Diese entsprechen der Query Stuttgart @shop:supermarket ”@name:Edeka” und zeigt sowohl die Objekte mit Value Edeka als auch EDEKA an. Die Ergebnisse werden in Abbildung 14 dargestellt, wobei von OSCAR immer nur 20 Ergebnisse auf einmal angezeigt werden. Abbildung 14: Ergebnisse bei Suche nach Filialen der Kette Edeka in Stutt- gart. (11.2017) 28 7.2 Beispiel 2: Fastfoodrestaurants in Berlin Als zweites Beispiel soll mit der Query Berlin @amenity:fast food nach Fast- foodrestaurants in Berlin gesucht werden. Wie im ersten Beispiel dominiert auch hier der Key wheelchair die Ergebnisse beim ersten Durchlauf: 0 wheelchair: yes - 857 1 wheelchair: no - 513 2 wheelchair: limited - 493 Auch hier werden diese wieder für den zweiten Durchlauf ausgeschlossen, was folgende Ergebnisse liefert: 0 cuisine: kebab - 642 1 cuisine: burger - 321 2 cuisine: asian - 255 3 cuisine: german - 175 4 cuisine: turkish - 164 5 cuisine: regional - 91 6 cuisine: italian - 82 7 name: Subway - 65 Wie schon im ersten Beispiel liefert der Algorithmus auch hier im zwei- ten Durchlauf gute Ergebnisse. Au↵allend ist, dass die Kette Subway separat gelistet ist. Das liegt daran, dass die meisten mit dem Key-Value-Paar cuisi- ne:sandwich getaggt sind, aber nicht alle. Nun können mit dem Befehl show 2 die asiatischen Restaurants angezeigt werden, was in Abbildung 15 dar- gestellt ist. Die gezeigten Ergebnisse entsprechen der OSCAR-Query Berlin @amenity:fast food ”@cuisine:asian”. Wegen der großen Menge an Ergeb- nissen werden nah beieinanderliegende Ergebnisse von OSCAR zusammen gefasst. 29 Abbildung 15: Ergebnisse bei Suche nach asiatischen Fastfoodrestaurants in Berlin. (11.2017) 8 Zusammenfassung und Ausblick Ziel dieser Arbeit war das Entwickeln eines Algorithmus für die anschauliche Organisation von semistrukturierten Daten, welche von der Suchmaschine OSCAR geliefert werden. Im folgenden letzten Kapitel sollen die Ergebnisse davon zusammengefasst werden und es wird evaluiert, in wie weit diese den Erwartungen entsprechen. Zuletzt werden noch mögliche Anknüpfungspunk- te für zukünftige Arbeiten vorgestellt. 8.1 Zusammenfassung Zu Beginn der Arbeit wurde ein erster Ansatz zu der Strukturierung der OSCAR-Daten vorgestellt, welcher nach Vorbild von DBLP geeignete Keys sucht, deren Values als Unterscheidungskriterien für die verschiedenen Ob- jekte dienen. Als nächstes ging es um die lokale Strukturierung der Ergebnis- se durch die Betrachtung der Parents. Dieser Algorithmus wurde aufgrund der überraschend guten Ergebnisse auf die Keys, sowie die Key-Value-Paare 30 übertragen. Wie erwartet tut sich der Algorithmus jedoch bei Mengen aus sehr ähnlichen Objekten schwer, kann jedoch bei heterogenen Mengen inter- essante Unterscheidungskriterien herausstellen. Zuletzt wurde die Möglich- keit der interaktiven Ergebnisfindung mit diesem Algorithmus vorgestellt. Es ist also durchaus möglich, Struktur in eine semistrukturierte Umge- bung zu bringen, auch wenn es natürlich deutlich aufwändiger als für einen vollständig strukturierten Datensatz ist. Je nachdem wie die semistrukturier- ten Daten gestaltet sind, fällt das Ergebnis dabei unterschiedlich gut aus. 8.2 Ausblick Für das Finden geeigneter Keys beziehungsweise Key-Value-Paare für die Strukturierung können aufwändigere Verfahren als das Bilden der Schnitt- menge vermutlich etwas bessere Ergebnisse erzielen. Beispielsweise könnten Beziehungen zwischen mehreren verschiedenen Keys hergestellt werden, an- statt immer nur einen bestimmten Key mit einem anderen zu vergleichen. Um die interaktive Ergebnisfindung für den Nutzer intuitiver zu gestalten ist sicherlich der Aufbau einer grafischen Benutzeroberfläche sinnvoll, auf der beispielsweise die Elemente durch Klicken ausgeschlossen werden können. Außerdem sollte man mit dieser angenehm durch die Ergebnisse navigieren können. Interessant wären auch Untersuchungen, wie gut sich die hier erarbei- teten Algorithmen auf anderen semistrukturierten Datensätzen, als die von OSCAR bereitgestellten, verhalten. 31 Literatur Daniel Bahrdt und Stefan Funke. Oscar: Openstreetmap planet at your fingertips via osm cell arrangements. In International Conference on Web Information Systems Engineering, pages 153–168. Springer, 2015. Holger Bast und Ingmar Weber. Type less, find more: fast autocompletion search with a succinct index. In Proceedings of the 29th annual internatio- nal ACM SIGIR conference on Research and development in information retrieval, pages 364–371. ACM, 2006. Holger Bast und Ingmar Weber. The completesearch engine: Interactive, e�cient, and towards ir & db integration. In Third Biennial Conference on Innovative Data Systems, pages 88–95, 2007. François Bry, Michael Kraus, Dan Olteanu, und Sebastian Scha↵ert. Se- mistrukturierte Daten. Informatik-Spektrum, 24(4):230–233, 2001. Roy Goldman, Jason McHugh, und Jennifer Widom. From semistructured data to xml: Migrating the lore data model and query language. 1999. Michael Ley. The dblp computer science bibliography: Evolution, research issues, perspectives. In String processing and information retrieval, pages 481–486. Springer, 2002. Michael Ley. Dblp: some lessons learned. Proceedings of the VLDB Endow- ment, 2(2):1493–1500, 2009. Nurzhan Nurseitov, Michael Paulson, Randall Reynolds, und Clemente Izu- rieta. Comparison of json and xml data interchange formats: a case study. Caine, 2009:157–162, 2009. 32