Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Master's Thesis |
| Scope | Discipline-based scholarship |
| Title | Supporting Updates in the RCAS Index |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Language |
|
| Institution | University of Zurich |
| Faculty | Faculty of Business, Economics and Informatics |
| Date | 2020 |
| Abstract Text | The Robust Content-And-Structure (RCAS) index is a novel index for semi-structured hierarchical data. Unlike pure content indexes or pure structure indexes, the RCAS index combines the content and structure of the data in a single index by interleaving paths and values. At the core of the RCAS index is a new interleaving scheme, called dynamic interleaving that interleaves paths and values at their discriminative bytes. Currently, the RCAS index only supports a bulk-loading algorithm to create the index from a set of keys. In this work we explore, implement, and evaluate new ways to insert keys in the RCAS index that strike a balance between the update and query performance of the index. We propose two new insert methods and in order to further improve the index’s insert and query performance we utilize an auxiliary RCAS index. Furthermore, we investigate two merge algorithms which have the aim to efficiently combine the content of the main and the newly introduced auxiliary index. Our experiments show that the combination of proposed insertion methods, indexes and merge algorithms can provide efficient inserts in the index while preserving high query performance. |
| Zusammenfassung | Der RCAS-Index (Robust Content-And-Structure Index) ist ein neuartiger Index für semistrukturierte hierarchische Daten. Im Gegensatz zu reinen Werteindizes oder reinen Strukturindizes kombiniert der RCAS-Index die Werte und die Struktur der Daten in einem einzigen Index, indem Pfade und Werte verzahnt werden. Das Kernstück des RCAS-Index ist ein neues Schema zum Verzahnen von Pfaden und Werten, das als Dynamic Interleaving bezeichnet wird und Pfade und Werte an ihrem diskriminativen Byte verzahnt. Gegenwärtig unterstützt der RCAS-Index nur die Erstellung eines Index aus einem anfänglichen Satz von Schlüsseln. In dieser Arbeit untersuchen, implementieren und evaluieren wir neue Wege zum Einfügen von Schlüsseln in den RCAS-Index, die ein Gleichgewicht zwischen der Einfüge- und Abfragegeschwindigkeit des Index herstellen. Wir schlagen zwei neue Einfügemethoden vor, und um die Einfüge- und Abfragegeschwindigkeit des Index weiter zu verbessern, verwenden wir den RCAS-Hilfsindex. Darüber hinaus untersuchen wir zwei Merge-Algorithmen, die das Ziel haben, den Inhalt des Haupt- und des neu eingeführten Hilfsindex effizient zu kombinieren. Unsere Experimente zeigen, dass die Kombination der vorgeschlagenen Einfügemethoden, Indizes und Merge-Algorithmen ein effizientes Einfügen in den Index ermöglichen, während die hohe Abfragegeschwindigkeit erhalten bleibt. |
| PDF File |
Download
|
| Export |
BibTeX
|