Data Management and Optimization of Data Layouts for Large-scale Interactive Walkthrough Applications

In modern walkthrough applications, storing massive datasets has become easy and inexpensive due to the availability of gigantic disk-based storage devices including hard drives, DVDs, and Blu-ray discs. However, fetching data from these devices for processing and rendering in interactive environments remains a bottleneck as data transfer speed has not kept pace with the sizes of both the secondary storage and main memory.;Out-of-core algorithms are commonly used as a solution to transfer data efficiently from the secondary storage to main memory. Existing algorithms strongly rely on suitable data layout algorithms to reduce the data fetch time. However, in spite of all commonly used techniques, finding a data layout with consistent high performance in interactive walkthrough application is still a challenging problem.;In this thesis, we first examine the performance of Solid-State Drives (SSD) for out-of-core algorithms and show that the performance bottleneck is in seeking and fetching data from secondary storage devices. SSDs have constant disk seek time. This property makes SSDs useful for applications that can afford only simple data clustering algorithms (cache-coherent data layouts) such as those that edit and modify the data set frequently. For storage devices in which we cannot ignore the seek time such as the traditional hard disk drives, we propose an orthogonal approach to minimize the seek time through redundant storage of data. As one extreme solution, given a data set and the access patterns, we show that interactive rendering performance of large data sets can be improved by limiting the number of seeks to just one per data access. As a more general solution, we explore the inter-relationship between the redundancy factor, number of seeks per data access, and data transfer volume per data access, and optimize the data clustering for a given bounds on number of seeks and data transfer volume using a linear programming approach. However, this approach provides only the data clustering, and the final data layout on the disk has to be computed as a post-processing step. In the subsequent work, we model the actual seek time instead of just the number of seeks, and simultaneously optimize both the clustering and layout using graph algorithms for optimal rendering performance for the given bounds on the seek time and redundancy.