Distributed Real-Time Analysis of High-Velocity Many-Dimensional Data Sets

Fast aggregation of data with many hierarchical dimensions is a key component of many data analysis applications. Recent years have seen increased interest in the ability to do so in real-time, allowing live analysis of rapidly changing data sets. At the same time, data sets of interest have increased in size well beyond the capabilities of a single machine to process efficiently. With the widespread availability of virtualized cloud computing environments, organizations increasingly demand systems that can be deployed on commodity platforms.Though each of these requirements in isolation can be addressed with well-known solutions, their combination introduces several system design challenges. As a result, users are forced to sacrifice certain functionality, or use several systems to handle different uses of the same data set.This dissertation proposes a scalable distributed system, VelocityOLAP (VOLAP), which meets all of these requirements at once. Specifically, the system can ingest data at a very high rate while answering queries which aggregate large fractions of the database. Users are not required to "slice" along particular dimensions or generate separate indices in order to query the database. Data is distributed across many machines, and the system can grow or shrink dynamically to accommodate changing load. The distribution of data is dynamically adjusted to maintain performance and provide fault-tolerance without interrupting real-time processing. The system can provide strong guarantees that query results are fresh, even as new items are inserted at a high rate.These results are achieved by building the system around a spatial index data structure which is specially designed to store hierarchical multi-dimensional data with rapid ingestion. Despite the lack of any user tuning for specific query workloads, extensive benchmarks on diverse data sets confirm that VOLAP scales well and can maintain high performance for a wide range of queries on a large and rapidly growing database.