Data structures for efficient analysis of large-scale unstructured datasets

The analysis of large unstructured or meshfree data is challenging due to their sheer size and unorganized manner. Gaining insight into the considered phenomena necessitates efficient algorithms and encodings that support the interactive manipulation of the information contained in these datasets. In the absence of suitable data representations, current visualization practice typically resorts to approximate and error-prone reformulations of the original data. Alternatively, it sacrifices interactivity to accuracy and carries out the visualization processing in an offline and therefore inflexible fashion. This thesis contributes several solutions to this fundamental problem through novel dynamic and scalable data structures that are specifically tailored to emerging many-core architectures. In particular, the proposed methods reconcile interactive data manipulation and faithful data representation. This general approach is applied to a variety of scenarios with a focus on engineering problems involving large-scale computational simulations. The novel tree encodings presented in this work provide for space savings and also enable tremendous speedups over previous state-of-the-art methods. While the work has been directly applied to ray casting / tracing and streamline computation scenarios, the data structures themselves have a much broader range of applicability