Online Archive of University of Virginia Scholarship
Superscalable Algorithms1031 views
Author
Brunelle, Nathan, Computer Science - School of Engineering and Applied Science, University of Virginia
Advisors
Robins, Gabriel, Department of Computer Science, University of Virginia
Abstract
We propose two new highly-scalable approaches to effectively process massive data sets in the post- Moore's Law era, namely (1) designing algorithms to operate directly on highly compressed data, and (2) leveraging massively parallel finite automata-based architectures for specific problem domains. The former method extends scalability by exploiting regularity in highly-compressible data, while also avoiding expensive decompression and re-compression. The latter hardware succinctly encapsulates complex behaviors via simulation of non-deterministic finite-state automata. We evaluate the efficiency, extensibility, and generality of these non-traditional approaches in big data environments. By presenting both promising experimental results and theoretical impossibility arguments, we provide more comprehensive frameworks for future research in these areas.
Degree
PHD (Doctor of Philosophy)
Keywords
Automata; Data Compression; Algorithms; Data Structures; Compression-aware algorithms; Pseudorandomness; Computational Geometry; Bloom Filter; Heterogeneous Computing; Parallel Computing; Automata Processor; Hardware Coprocessors; Big Data; Moore's Law
Brunelle, Nathan. Superscalable Algorithms. University of Virginia, Computer Science - School of Engineering and Applied Science, PHD (Doctor of Philosophy), 2017-08-05, https://doi.org/10.18130/V3MR40.
