Advanced data deduplication techniques and their application

Data deduplication describes a class of approaches that reduce the storage capacity needed to store data or the amount of data that has to be transferred over a network. These approaches detect coarse-grained redundancies within a data set, e.g. a file system, and remove them.rnrnOne of the most important applications of data deduplication are backup storage systems where these approaches are able to reduce the storage requirements to a small fraction of the logical backup data size.rnThis thesis introduces multiple new extensions of so-called fingerprinting-based data deduplication. It starts with the presentation of a novel system design, which allows using a cluster of servers to perform exact data deduplication with small chunks in a scalable way.rnrnAfterwards, a combination of compression approaches for an important, but often over- looked, data structure in data deduplication systems, so called block and file recipes, is introduced. Using these compression approaches that exploit unique properties of data deduplication systems, the size of these recipes can be reduced by more than 92% in all investigated data sets. As file recipes can occupy a significant fraction of the overall storage capacity of data deduplication systems, the compression enables significant savings.rnrnA technique to increase the write throughput of data deduplication systems, based on the aforementioned block and file recipes, is introduced next. The novel Block Locality Caching (BLC) uses properties of block and file recipes to overcome the chunk lookup disk bottleneck of data deduplication systems. This chunk lookup disk bottleneck either limits the scalability or the throughput of data deduplication systems. The presented BLC overcomes the disk bottleneck more efficiently than existing approaches. Furthermore, it is shown that it is less prone to aging effects.rnrnFinally, it is investigated if large HPC storage systems inhibit redundancies that can be found by fingerprinting-based data deduplication. Over 3 PB of HPC storage data from different data sets have been analyzed. In most data sets, between 20 and 30% of the data can be classified as redundant. According to these results, future work in HPC storage systems should further investigate how data deduplication can be integrated into future HPC storage systems.rnrnThis thesis presents important novel work in different area of data deduplication re- search.

Systematics, phylogeny and biogeography of Juncaginaceae

I investigated the systematics, phylogeny and biogeographical history of Juncaginaceae, a small family of the early-diverging monocot order Alismatales which comprises about 30 species of annual and perennial herbs. A wide range of methods from classical taxonomy to molecular systematic and biogeographic approaches was used. rnrnIn Chapter 1, a phylogenetic analysis of the family and members of Alismatales was conducted to clarify the circumscription of Juncaginaceae and intrafamilial relationships. For the first time, all accepted genera and those associated with the family in the past were analysed together. Phylogenetic analysis of three molecular markers (rbcL, matK, and atpA) showed that Juncaginaceae are not monophyletic. As a consequence the family is re-circumscribed to exclude Maundia which is pro-posed to belong to a separate family Maundiaceae, reducing Juncaginaceae to include Tetroncium, Cycnogeton and Triglochin. Tetroncium is weakly supported as sister to the rest of the family. The reinstated Cycnogeton (formerly included in Triglochin) is highly supported as sister to Triglochin s.str. Lilaea is nested within Triglochin s. str. and highly supported as sister to the T. bulbosa complex. The results of the molecular analysis are discussed in combination with morphological characters, a key to the genera of the family is given, and several new combinations are made.rnrnIn Chapter 2, phylogenetic relationships in Triglochin were investigated. A species-level phylogeny was constructed based on molecular data obtained from nuclear (ITS, internal transcribed spacer) and chloroplast sequence data (psbA-trnH, matK). Based on the phylogeny of the group, divergence times were estimated and ancestral distribution areas reconstructed. The monophyly of Triglochin is confirmed and relationships between the major lineages of the genus were resolved. A clade comprising the Mediterranean/African T. bulbosa complex and the American T. scilloides (= Lilaea s.) is sister to the rest of the genus which contains two main clades. In the first, the widespread T. striata is sister to a clade comprising annual Triglochin species from Australia. The second clade comprises T. palustris as sister to the T. maritima complex, of which the latter is further divided into a Eurasian and an American subclade. Diversification in Triglochin began in the Miocene or Oligocene, and most disjunctions in Triglochin were dated to the Miocene. Taxonomic diversity in some clades is strongly linked to habitat shifts and can not be observed in old but ecologically invariable lineages such as the non-monophyletic T. maritima.rnrnChapter 3 is a collaborative revision of the Triglochin bulbosa complex, a monophyletic group from the Mediterranean region and Africa. One new species, Triglochin buchenaui, and two new subspecies, T. bulbosa subsp. calcicola and subsp. quarcicola, from South Africa were described. Furthermore, two taxa were elevated to species rank and two reinstated. Altogether, seven species and four subspecies are recognised. An identification key, detailed descriptions and accounts of the ecology and distribution of the taxa are provided. An IUCN conservation status is proposed for each taxon.rnrnChapter 4 deals with the monotypic Tetroncium from southern South America. Tetroncium magellanicum is the only dioecious species in the family. The taxonomic history of the species is described, type material is traced, and a lectotype for the name is designated. Based on an extensive study of herbarium specimens and literature, a detailed description of the species and notes on its ecology and conservation status are provided. A detailed map showing the known distribution area of T. magellanicum is presented. rnrnIn Chapter 5, the flower structure of the rare Australian endemic Maundia triglochinoides (Maundiaceae, see Chapter 1) was studied in a collaborative project. As the morphology of Maundia is poorly known and some characters were described differently in the literature, inflorescences, flowers and fruits were studied using serial mictrotome sections and scanning electron microscopy. The phylogenetic placement, affinities to other taxa, and the evolution of certain characters are discussed. As Maundia exhibits a mosaic of characters of other families of tepaloid core Alismatales, its segregation as a separate family seems plausible.