Incrementally Sorted Lattice Data Structures Open Access
Downloadable ContentDownload PDF
Data structures are vital entities that strongly impact the efficiency of several software applications. Compactness, predictable memory access patterns, and good temporal and spacial locality of the structure's operations are increasingly becoming essential factors in the selection of a data structure for a specific application. In general, the less data we store and move the better for efficiency and power consumption, especially in infrastructure software and applications for hand-held devices like smartphones. In this dissertation, we extensively study a data structure named lattice data structure (LDS) that is as compact and suitable for memory hierarchies as the array, yet with a rich structure that enables devising procedures with better time bounds. To achieve performance similar to the performance of the optimal O(log(N)) time complexity of the searching operations of other structures, we provide a hybrid searching algorithm that can be implemented by searching the lattice using the basic searching algorithm when the degree of the sortedness of the lattice is less than or equal to 0.9h, and the jump searching algorithm when the degree of the sortedness of the lattice is greater than 0.9h. A sorting procedure that can be used, during the system idle time, to incrementally increase the degree of sortedness of the lattice is given. We also provide randomized and parallel searching algorithms that can be used instead of the usual jump-and-walk searching algorithms. A lattice can be represented by a one-dimensional array, where each cell is represented by one array element. The worst case time complexity of the basic LDS operations and the average time complexity of some of the order-statistic operations are better than the corresponding time complexities of most of other data structures operations. This makes the LDS a good choice for memory-constrained systems, for systems where power consumption is a critical issue, and for real-time systems. A potential application of the LDS is to use it as an index structure for in-memory databases.