Cache-oblivious data structures for massive data sets

In this dissertation, we present the following results: We prove tight bounds on the cost of cache-oblivious searching and propose a generalized van Emde Boas layout to optimize the searching cost in the cache-oblivious structures. we show that there is no cache-oblivious search structure can guarantee that a search performs fewer than lg elogBN memory transfers, i.e., lg elogBN is the lower bound. The upper bound is achieved by the generalized vEB layout, whose expected memory transfers between any two levels of the memory hierarchy arbitrarily close to [lg e+O(lglgB/lgB)] logBN +O(1). That is, we achieve the factor, which optimally approaches lge a 1.443 as the block size B increases. The work appears in Chapter 2 and is published in [12]. We give the first adaptive packed-memory array (APMA), theoretically and practically optimizing PMA’s performance on most common input patterns. Like the traditional PMA, any pattern of updates costs only O(log2N) amortized element moves and O(1+(2N)/B) amortized memory transfers per update. However, the adaptive PMA adjusts to the input pattern and therefore performs better on many common input distributions achieving only O(logN) amortized element moves and O(1+(N)/B) amortized memory transfers. We analyze sequential inserts, where the insertions are to the front of the APMA, hammer inserts, where the insertions “hammer” on one part of the APMA, random inserts, where the insertions are after random elements in the APMA, and bulk inserts, where for constant α∈ [0,1], Nα elements are inserted after random elements in the APMA. This work appears in Chapter 3 and is published in [25]. We develop the partially deamortized packed-memory array (PDPMA) to reduce the worst-case cost in the PMA. As the traditional PMA, the PDPMA has the same update cost of O(1+(2 N)/B) amortized memory transfers. However, for a single update, the traditional PMA has the worst-case cost of O(N) element moves and O(1+ N/B) memory transfers. It is not feasible for industrial application because one insertion might trigger the rebalance of the whole database. Therefore, our partially deamortized PMA is designed for the purpose of cost reduction in the worst case and achieves the worst-case performace of one update in O( N logN) element moves and O(1+( N logN)/B) memory transfers. This work appears in Chapter 4. We present the first atomic-key B-tree to support atomic keys of different sizes in the B-tree with the theoretical guarantee. There exist many practical B-trees in support of variable-length keys. However, none of them have theoretical guarantee and their practical performance degrades when keys are long or vary in length. Our atomic-key B-tree is efficient in this respect. Specifically, we first give an algorithm for building a static atomic-key B-tree. On a dictionary of n keys having average size kˆ, the expected cost to search for a random key is Opckd/Bc log1+cB/kcd Np memory transfers, under the assumption that all keys are searched with uniform probability. The cost to build this tree is O( N) operations and O(N + Nkˆ/B) memory transfers. We then show how to build a dynamic atomic-key B-tree with a better performance of O(N/f +Nkˆ /B) memory transfers, where f = max{2, B/kd }. In this dynamic structure, the expect cost to search for random keys stays the same. The cost to insert an arbitrary key κ is the cost to search for κ plus a tree-update cost of Opckd/Bc log1+cB/kcd Np amortized memory transfers. This work appears in Chapter 5. In summary, we contribute to the theory of the searching cost in the cache-oblivious model by presenting the generalized vEB layout. We develop two dynamic cache-oblivious structures: the adaptive PMA and the partially deamortized PMA to overcome the traditional PMA’s deficiencies and make it practical. We also propose the atomic-key B-tree in support of atomic keys with variable length, whose structure is as close as possible to the traditional B-tree while having performance guarantees. (Abstract shortened by UMI.)