No description available.

<p dir="ltr">In recent years, massive amounts of data have been generated from various types of devices or services. For these data, update-intensive workloads where the data update their status periodically and continuously are common. The Log-Structured-Merge (LSM, for short) is a widely-used indexing technique in various systems, where index structures buffer insert operations into the memory layer and flush them into disk when the data size in memory exceeds a threshold. Despite its noble ability to handle write-intensive (i.e., insert-intensive) workloads, LSM suffers from degraded query performance due to its inefficiency on index maintenance of secondary keys to handle update-intensive workloads.</p><p dir="ltr">This dissertation focuses on the efficient support of update-intensive workloads for LSM-based indexes. First, the focus is on the optimization of LSM secondary-key indexes and their support for update-intensive workloads. A mechanism to enable the LSM R-tree to handle update-intensive workloads efficiently is introduced. The new LSM indexing structure is termed the LSM RUM-tree, an LSM R-tree with Update Memo. The key insights are to reduce the maintenance cost of the LSM R-tree by leveraging an additional in-memory memo structure to control the size of the memo to fit in memory. In the experiments, the LSM RUM-tree achieves up to 9.6x speedup on update operations and up to 2400x speedup on query operations.</p><p dir="ltr">Second, the focus is to offer several significant advancements in the context of the LSM RUM-tree. We provide an extended examination of LSM-aware Update Memo (UM) cleaning strategies, elucidating how effectively each strategy reduces UM size and contributes to performance enhancements. Moreover, in recognition of the imperative need to facilitate concurrent activities within the LSM RUM-Tree, particularly in multi-threaded/multi-core environments, we introduce a pivotal feature of concurrency control for the update memo. The novel atomic operation known as Compare and If Less than Swap (CILS) is introduced to enable seamless concurrent operations on the Update Memo. Experimental results attest to a notable 4.5x improvement in the speed of concurrent update operations when compared to existing and baseline implementations.</p><p dir="ltr">Finally, we present a novel technique designed to improve query processing performance and optimize storage management in any secondary LSM tree. Our proposed approach introduces a new framework and mechanisms aimed at addressing the specific challenges associated with secondary indexing in the structure of the LSM tree, especially in the context of secondary LSM B+-tree (LSM BUM-tree). Experimental results show that the LSM BUM-tree achieves up to 5.1x speedup on update-intensive workloads and 107x speedup on update and query mixed workloads over existing LSM B+-tree implementations.</p>

No description available.

Nous nous intéressons à trois problèmes issus du monde des arbres aléatoires discrets et continus. Dans un premier lieu, nous faisons une étude générale des arbres de fragmentation auto-similaires, étendant certains résultats de Haas et Miermont en 2006, notamment en calculant leur dimension de Hausdorff sous des hypothèses malthusiennes. Nous nous intéressons ensuite à une suite particulière d’arbres discrets k-aires, construite de manière récursive avec un algorithme similaire à celui de Rémy de 1985. La taille de l’arbre obtenu à la n-ième étape est de l’ordre de n^(1/k), et après renormalisation, on trouve que la suite converge en probabilité vers un arbre de fragmentation. Nous étudions également des manières de plonger ces arbres les uns dans les autres quand k varie. Dans une dernière partie, nous démontrons la convergence locale en loi d’arbres de Galton-Watson multi-types critiques quand on les conditionne à avoir un grand nombre de sommets d’un certain type fixé. Nous appliquons ensuite ce résultat aux cartes planaires aléatoire pour obtenir la convergence locale en loi de grandes cartes de loi de Boltzmann critique vers une carte planaire infinie. / We study three problems related to discrete and continuous random trees. First, we do a general study of self-similar fragmentation trees, extending some results established by Haas and Miermont in 2006, in particular by computing the Hausdorff dimension of these trees under some Malthusian hypotheses. We then work on a particular sequence of k-ary growing trees, defined recursively with a similar method to Rémy’s algorithm from 1985. We show that the size of the tree obtained at the n-th step if of order n^(1/k), and, after renormalization, we prove that the sequence convergences to a fragmentation tree. We also study embeddings of the limiting trees as k varies. In the last chapter, we show the local convergence in distribution of critical multi-type Galton-Watson trees conditioned to have a large number of vertices of a fixed type. We then apply this result to the world of random planar maps, obtaining that large critical Boltzmann-distributed maps converge locally in distribution to an infinite planar map.