Superscalable Algorithms

Brunelle, Nathan, Computer Science - School of Engineering and Applied Science, University of Virginia
Robins, Gabriel, Department of Computer Science, University of Virginia

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.

PHD (Doctor of Philosophy)
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
Issued Date: