Integration, Indexierung und Interaktion hochdimensionaler Datenobjekte

Dissertation / Doktorarbeit von Konstantin Koll

Einleitung:

Die Anforderungen an Computersysteme haben sich in den letzten Jahren besonders im privaten Bereich deutlich verändert, hin zu einem Speicher- und Wiedergabesystem für digitale Medien wie Musik, Videos und Fotos. Diese Entwicklung wird durch die noch immer wachsende Beliebtheit von MP3-Dateien und ihren Derivaten, digitaler Fotografie und neuerdings auch durch digitales hochauflösendes Fernsehen angetrieben. Sie hat ihren vorläufigen Höhepunkt in sog. ‚Mediacenter’-Applikationen gefunden, die digitale Medien endgültig im heimischen Wohnzimmer ankommen lassen.

Leider sind die von Betriebssystemen eingesetzten Dateisysteme nicht weiterentwickelt worden, um den veränderten Anforderungen beim Speichern und vor allem Wiederfinden tausender Dateien gerecht zu werden. Lediglich die physikalische Größe von Dateisystemen ist durch Einführung größerer Adressräume und effizienterer Datenstrukturen gewachsen. Auf logischer Ebene bieten die heute eingesetzten Dateisysteme als Ordnungsschema noch immer eine Verzeichnishierarchie an, die jedoch deutliche Nachteile aufweist. Dourish, P. et al. identifiziert einige dieser Nachteile, die teilweise bereits in Malone, T. W. beschrieben worden sind, dort allerdings bezogen auf Papierakten. Zunächst können Dateien nur an genau einem Platz in der Verzeichnishierarchie abgelegt werden.

Auf der obersten Ebene sind alle Fotos in Aufnahmen von Geburtstagsfeiern und Urlaubsfotos eingeteilt – erstere dann nach Personen, letztere nach Ländern und schließlich weiter nach Orten. Dieses System weist jedoch prinzipielle Lücken auf: Wo sollen beispielsweise Fotos von Bertas Geburtstag abgelegt werden, wenn sie ihn auf Mallorca gefeiert hat ? Wenn entsprechende Bilder in beiden Zusammenhängen auffindbar sein sollen, müssen sie auch über beide Ordner zugänglich gemacht werden, etwa mittels Einführung symbolischer Links. Das Anlegen weiterer Kategorien, etwa des Aufnahmejahres, steigert diesen Aufwand zusehends weiter.

Darüber hinaus ist eine solche Verzeichnishierarchie auf die Mitarbeit des Benutzers angewiesen Mills, B., der geeignete Kategorien für seine Dateien finden, entsprechende Unterverzeichnisse anlegen und dann auch einsetzen muss. In der Praxis wird es zudem oft vorkommen, dass Dateien in den falschen Verzeichnissen gespeichert werden, so dass sie nicht mehr aufgefunden werden können und ‚verloren gehen’.

Für diesen Fall bieten Betriebssysteme mehr oder weniger gute Suchfunktionen an, die als Suchkriterium jedoch nur die Attribute erlauben, die das Dateisystem selbst verwaltet. Weitere Metadaten, die insbesondere in modernen Multimedia-Dateiformaten enthalten sind, stehen oft nur in einigen Programmen zur Verfügung, die solche Dateiformate öffnen können. Auf Betriebssystem-Ebene sind diese Attribute unzugänglich, obwohl gerade sie eine sinnvolle Suche ermöglichen würden.

Zielsetzung:

Das Hauptziel dieser Arbeit besteht darin, den Zugriff von Benutzern auf ihre Dateien, insbesondere auf Multimedia-Inhalte, zu verbessern. Diese Aufgabenstellung erfordert die interdisziplinäre Bearbeitung der Bereiche Integration, Indexierung und Interaktion. Auf der Basis einer Referenz-Library, welche die Integration und Indexierung von hochdimensionalen Datenobjekten realisiert, kann die Interaktion durch diverse Verbesserungen optimiert werden.

Im Zusammenspiel erfüllen diese Innovationen das oben gesetzte Ziel eines verbesserten Zugriffs auf eine große Anzahl Dateien. Abschließend werden Möglichkeiten zur Integration in bereits existierende Systeme sowie zur Weiterentwicklung vorgestellt.

Inhaltsverzeichnis:

1.	Einleitung	1
1.1	Zielsetzung und Überblick	2
1.1.1	Integration	2
1.1.2	Indexierung	3
1.1.3	Interaktion	3
1.2	Resultate	4
1.3	Veröffentlichungen	4
2.	Existierende Lösungen	5
2.1	Lotus Magellan	5
2.1.1	Arbeitsweise	6
2.1.2	Steuerung der Indexierung	8
2.2	SFS und MetaFS	9
2.2.1	Weiterentwicklungen	11
2.2.2	Performanz	11
2.3	Rufus	12
2.3.1	Klassifizierer	12
2.3.2	Objekte	13
2.4	Microsoft OLE	13
2.4.1	Beispiel	14
2.4.2	Registry	16
2.4.3	Objekt-Manager	17
2.5	Microsoft Indexerstellung	18
2.6	Microsoft Windows Explorer	19
2.7	BeFS	21
2.7.1	Übersetzer	21
2.7.2	Postfächer	22
2.7.3	Suchfunktion	23
2.8	DBFS	24
2.9	Microsoft WinFS	27
2.9.1	WinFS Type Browser	28
2.9.2	StoreSpy	29
2.10	Moderne Desktop-Suchmaschinen	31
2.10.1	Linux Beagle	31
2.10.2	Apple Spotlight	32
2.10.3	Google Desktop	34
2.10.4	Yahoo Desktop	35
2.11	Fazit	36
3.	Existierende Indexe	37
3.1	Lucene	37
3.1.1	Compound File System	37
3.1.2	Performanz	40
3.2	BeFS	40
3.2.1	Indexierung	42
3.2.2	Performanz	42
3.3	Multidimensionale Indexierung	43
3.3.1	Der ‘Fluch der Dimensionen’	44
3.3.2	Partial Match Operationen	47
3.3.3	Ineffizienz von persistent gespeicherten Bäumen	48
3.3.4	Partiell belegter Datenraum	50
3.3.5	Performanz	51
3.4	Fazit	55
4.	Integration	57
4.1	Libraries	58
4.2	Relationale Datenbanken	60
4.2.1	BLOB-relationale Datenbanken	61
4.3	Dateisysteme	62
4.3.1	Abbildungsvorschrift	62
4.3.2	Semantische Dateisysteme	63
4.4	Vorteile	64
4.4.1	Zugriff	65
4.4.2	Operationen	66
4.4.3	Typsicherheit	66
4.4.4	Terminologie	67
5.	Indexierung	69
5.1	Master/Slave-Index	69
5.1.1	Generalisierung/Spezialisierung	69
5.1.2	Retrieval	71
5.1.3	Hinzufügen	74
5.1.4	Ändern	74
5.1.5	Löschen	74
5.1.6	Massen-Operationen	76
5.2	Performanz	78
5.2.1	Optimierung	79
5.2.2	Verifizierung	80
6.	Referenz-Library	81
6.1	Architektur	81
6.1.1	Domains	82
6.1.2	Applikationen	83
6.1.3	Registry	85
6.2	Implementierung	85
6.2.1	Namensraum	85
6.2.2	Selektion	87
6.3	Performanz	89
6.3.1	Testumgebung	89
6.3.2	GREP	89
6.3.3	Ohne Index	90
6.3.4	Master/Slave-Index	90
6.3.5	Komprimierter Master/Slave-Index	91
6.4	Vorteile	92
6.4.1	Architektur	92
6.4.2	Implementierung	94
7.	Interaktion	95
7.1	Shell	96
7.1.1	Moderne Shells	96
7.1.2	Anforderungen an eine Shell	98
7.1.3	Hypertext-Menus	98
7.1.4	Vorteile	102
7.2	Join-Operationen	104
7.3	Benutzerdefinierte Filter	106
7.3.1	Shell-Integration	106
7.3.2	Vorteile	107
7.4	Automatische Ordner	107
7.4.1	Kalenderansicht	109
7.4.2	Vorteile	109
7.5	Semantisches Tagging	110
7.5.1	Geotagging	111
7.5.2	Bewertung von Dateien	113
7.5.3	Vorteile	115
7.6	Aufgabenorientierung	115
7.6.1	Vorteile	117
7.7	Webserver	117
7.7.1	‘Fancy fancy indexing’	119
7.7.2	Vorteile	121
8.	Zusammenfassung und Ausblick	123
8.1	Zusammenfassung	123
8.2	Integration in existierende Systeme	124
8.2.1	Master/Slave-Index	124
8.2.2	Erweiterung für Dateisysteme	124
8.2.3	Applikationen	125
8.3	Weiterentwicklungen	126
8.3.1	Master/Slave-Index	126
8.3.2	Semantisches Tagging	127
8.3.3	Automatisches Tagging	127
8.3.4	Verbesserte Visualisierung	128
8.4	Ausblick	129
	Anhang	131
A	Glossar	131
B	Testprogramm zur Seek-Geschwindigkeit	133
B.1	SEEKTEST.PAS	133
B.2	Messergebnisse	135
C	Testprogramm ‘Microsoft SQL-Server 2005’	137
C.1	METADATA.XML	137
C.2	METADATA.XSD	138
C.3	PROGRAM.CS	138
D	Testprogramm ‘PostgreSQL’	143
D.1	PROGRAM.CS	143
	Literaturverweise	147

Textprobe:

Kapitel 3.3.1.1 Triviale Extreme Die Nachbarschaftssuche in einem d-dimensionalen Datenraum beinhaltet das Spezifizieren eines Punktes p und die Suche nach dem Datenobjekt, das den geringsten Abstand zu p aufweist. Eine Erweiterung, die k-Nachbarschaftssuche, soll die k nächstgelegenen Objekte liefern.

Für diese Probleme existieren zwei triviale Algorithmen, die entweder die Suchzeit oder den Speicherbedarf minimieren. Zum einen kann für alle Objekte der Abstand zu p ausgerechnet werden, wobei das Objekt mit dem kleinsten Abstand gespeichert und zurückgeliefert wird. Die Ausführungszeit beträgt O(n), der zusätzliche Speicherbedarf ist konstant. Der andere Extremfall existiert nur, wenn eine endliche Anzahl von Suchanfragen möglich ist: dann kann das Ergebnis für jede denkbare Anfrage im Voraus berechnet und gespeichert werden. Suchanfragen können dann in O(d) beantwortet werden, allerdings wird dies mit einem exponentiellen Speicherbedarf erkauft.

Das eigentliche Problem der Nachbarschaftssuche besteht nun darin, gleichzeitig die Laufzeit und den Speicherbedarf zu minimieren. Für sinnvolle Umgebungen (z.B. euklidischer Datenraum) und beliebige n und d scheint kein Algorithmus zu existieren, der sowohl die Laufzeit auf poly(d) und den Speicherbedarf auf poly(nd) begrenzt. Dieses Phänomen ist als »Fluch der Dimensionen« bekannt.

Partitionierung des Daten- bzw. Objektraums:

Durch die Wichtigkeit hochdimensionaler Datenräume für praktische Anwendungen wurde in der Vergangenheit intensiv nach Datenstrukturen und Algorithmen geforscht, die die Vorteile der beiden Extremlösungen vereinen sollen. Dabei fällt auf, dass vor allem das sequenzielle Scannen aller Objekte bei geschickter Implementierung eine überraschend gute Performanz bietet und unter bestimmten Voraussetzungen sogar optimal für große d ist.

Indexstrukturen, die den Daten- bzw. Objektraum partitionieren, degenerieren mit zunehmender Dimensionszahl, so dass die Partitionen zunehmend große Volumina enthalten und sich daher stark überlappen. Dadurch müssen sehr viele Objekte betrachtet werden, so dass die Partitionen letztlich doch sequenziell gescannt werden – zusätzlich zum Aufwand, der durch die Partitionierung verursacht wird (etwa das Traversieren eines Baums). Berchtold, S. et al.schlägt daher einen modifizierten R-Baum vor, den X-Baum (»extended node tree«), bei dem derartig degenerierte Baumknoten absichtlich durch lineare Listen (»supernodes«) ersetzt und dann sequenziell durchsucht werden:

The X-tree may be seen as a hybrid of a linear array-like and a hierarchical R-tree-like directory. … It is also reasonable, that for very high dimensionality a linear organization of the directory is more efficient. The reason is that due to the high overlap, most of the directory if not the whole directory has to be searched anyway.

Weber, R. et al beweist schließlich, dass dieser Sachverhalt nicht nur für R-Bäume, sondern unter Annahme der Gleichverteilung für jeden denkbaren multidimensionalen Index gilt, der den Daten- oder Objektraum partitioniert. Dieser Beweis wird nun kurz skizziert.

Alle Attributwerte werden zunächst auf das Intervall [0,1] skaliert, so dass der Datenraum auf einen Hyperwürfel mit der Kantenlänge 1 normiert wird: W = [0,1]d. Innerhalb des Datenraums soll ein beliebiger Algorithmus Elemente zu »Bereichen« zusammenfassen, entweder durch Unterteilen des Datenraums W ohne Rücksicht auf die tatsächlich enthaltenen Daten (z.B. kd-Baum) oder durch Clustern der tatsächlich vorhandenden Objekte, also Partitionieren des Objektraums w(z.B. R-Baum). Die entstehenden Bereiche haben drei grundlegende Eigenschaften:

- Jeder Bereich besitzt eine minimal umgebende Form (»minimum bounding region«).

- Jede mbr ist konvex.

- Jeder Bereich enthält mindestens zwei Elemente. Ohne diese Bedingung würde das Unterteilungsproblem nur auf eine andere Knotenebene der Baumstruktur verschoben.