More data means more opportunity for a researcher to test more hypotheses until he discovers an interesting finding. This increases the probability of arriving at a false conclusion purely by chance and is known as the multiple comparisons problem. Data exploration systems facilitate exploring big data by automatically testing thousands of hypotheses in order to find the most interesting ones. In machine learning analysts repeatedly test a model's performance on a holdout dataset until they find the one with the best performance. Auto-ML systems try to automate this model selection process. In both cases, testing for more things means a higher probability of making a statement purely by chance.

This dissertation examines how the multiple comparisons problem appears in the field of data exploration and machine learning. In both cases we propose techniques that exploit some structure that appears in the field to improve upon existing techniques and reduce the consequences of multiple comparisons.

We present VigilaDE, the first data exploration system that utilizes the hierarchical structure of the data in order to control false discoveries. A plethora of real-world datasets already have domain-specific hierarchies that describe the relationship between variables. VigilaDE utilizes these hierarchies to guide the exploration towards interesting discoveries while controlling false discoveries and, as a result, increasing statistical power. Through extensive experiments with real-world data, simulations and theoretical analysis we show that our data exploration algorithms can find up to 2.7x more true discoveries in the data against the baseline while controlling the number of false discoveries.

In machine learning, the consequence of testing multiple different models is overfitting. We present an experimental analysis of ThresholdOut, the state of the art algorithm for avoiding overfitting a holdout dataset. The main limitation of ThresholdOut is setting its parameters. We present Auto-Set, an automated way to set its parameters for feature selection. Specifically in feature selection the order of the models that we test on a holdout dataset has a very specific structure. We utilize this structure in Auto Adjust Threshold, a novel feature selection algorithm that avoids overfitting a holdout dataset and show that it outperforms existing algorithms.

Data compression techniques (both lossless and lossy compression methods) are widely utilized in big data analytic applications in domains including health-care, transportation, and finance. The main benefit achieved from applying data compression techniques is the saving of space cost. However, performing analytic queries on compressed data has two major challenges in terms of the performance and the accuracy: (i) decompressing data may damage the performance, and (ii) if lossy data compression techniques are utilized then the returned answers are not accurate. In this dissertation, we study how to accelerate analytic queries over compressed data (and provide tight error guarantees for approximate answers if lossy data compression methods are applied).

First, this dissertation introduces an in-memory database, called GQ-Fast, which supports high-performance analytic SQL queries over compressed relational data. We study a class of graph analytic SQL queries, called relationship queries. These queries involving aggregation, join, semijoin, intersection and selection are a wide superset of fixed-length graph reachability queries and of tree pattern queries. We present real-world OLAP scenarios, where efficient relationship queries are needed. However, row stores, column stores and graph databases are unacceptably slow in such OLAP scenarios. To support efficient relationship queries, we propose a GQ-Fast database, which is an indexed database that roughly corresponds to efficient encoding of annotated adjacency lists that combines salient features of column-based organization, indexing and compression. GQ-Fast uses a bottom-up fully pipelined query execution model, which enables (i) aggressive compression (e.g., compressed bitmaps and Huffman) and (ii) avoids intermediate results that consist of row IDs (which are typical in column databases). In addition, GQ-Fast compiles query plans into executable C++ source code. Besides achieving runtime efficiency, GQ-Fast also reduces main memory requirements because, unlike column databases, GQ-Fast selectively allows dense forms of compression including heavy-weight compressions, which do not support random access. GQ-Fast outperforms the state-of-the-art databases by 1-3 orders of magnitudes and GQ-Fast uses less space.

Second, this dissertation proposes an approximate query processing system, called Plato, which supports anytime analytic queries over compressed time series with sound and tight deterministic error guarantees. Plato supports expressions that are compositions of the linear algebra operators over vectors along with arithmetic operators. Such analytics can express common statistics (such as correlation and cross-correlation) that may combine multiple time series. Plato builds a compressed segment tree structure for each time series during the offline insertion time. Each node in the tree refers to a time series segment. Each segment (i) is compressed by an estimation function that approximates the actual values and is coming from a user-chosen estimation function family, and (ii) is associated with one to three (depending on the case) precomputed error measures. Then Plato is able to provide tight deterministic error guarantees satisfying the error budgets provided by users by accessing the minimal number of nodes in the segment tree. In addition, we also identify two broad estimation function family groups. The Vector Space (VS) family and the presently defined Linear Scalable Family (LSF) lead to theoretically and practically high-quality guarantees, even for queries that combine multiple time series that have been independently compressed. Well-known function families (e.g., the polynomial function family) belong to LSF. The theoretical aspect of "high quality" is crisply captured by the Amplitude Independence (AI) property: An AI guarantee does not depend on the amplitude of the involved time series, even when we combine multiple time series.

Pre-2018 CSE ID: CS2003-0739

Since 2005, with Ajax functionality becoming a de-facto requirement of cloud-based applications, a developer needs to integrate a plethora of languages in order to deliver even simple data-centric web applications: SQL to access the database, HTML and JavaScript for browser-side interactions, and yet another programming language (e.g. Java) for server-side business logic. Even worse, most of the JavaScript and Java is tedious, imperative code to perform mundane, low-level data integration, coordination and access optimization problems, which result either from language and data heterogeneities, or from the distributed programming necessitated by multiple computation points (browser, application server, database server).

FORWARD is a data-centric, declarative web application development framework that uses SQL++, a minimally enhanced version of SQL as its core programming model. Data from SQL queries can be styled directly with a data-driven page configuration that allows HTML templates and pre-packaged Ajax units (e.g. maps, charts, calendars), thus leading to Ajax pages that are automatically rendered and refreshed. In the majority of applications, no Java or JavaScript is needed.

A central contribution is the provision of a unified, SQL-accessible application state that captures the application's database along with typical web application programming data spaces, such as session and request data. The unified state includes a logical representation of the core page data pertinent to the business logic, thus allowing the SQL-based business logic to easily access page data seamlessly with the rest of the state.

This dissertation also discusses a few key optimization and automation components of FORWARD, which are enabled by FORWARD's declarative approach. FORWARD mapping framework can express SQL++ queries found common in transforming data from one schema to another, and is used extensively in the page layer. A novel ID-based incremental view maintenance (IVM) system takes an algebraic approach and expresses data diffs with IDs, so that diff computation is accelerated as data access is minimized. Furthermore, the IVM system is extended to handle SQL++ query language and schema-less data model.

Modern solid state drives (SSDs) unnecessarily confine applications to the conventional block I/O interface, which under-utilizes SSD’s internal resources, leading to suboptimal performance and unsatisfactory lifetime.

This thesis first presents the key-addressable, multi-log SSD (KAML), an SSD with a key-value interface that uses a novel multi-log architecture and stores data as variable-sized records rather than fixed-sized sectors. Exposing a key-value interface allows applications to remove a layer of indirection between application-level keys and data stored in the SSD. KAML also provides native support for fine-grained atomicity and isolation. We have implemented a prototype of KAML on an SSD development platform, and results show that KAML outperforms conventional systems by up to 4.0X.

Existing SSDs also provide flash-based out-of-band (OOB) data that can only be updated on a conventional write. Consequently, the metadata stored in their OOB region lack flexibility due to the idiosyncrasies of flash memory, incurring unnecessary flash write operations detrimental to device lifetime. This thesis also presents PebbleSSD, an SSD with byte-addressable metadata, or BAM, as a mechanism exploiting the nonvolatile, byte-addressable random access memory (NVRAM) inside the SSD. With BAM, PebbleSSD can support a range of useful features to improve its lifetime by reducing redundant flash writes. We have implemented a prototype of PebbleSSD on an SSD development platform, and experimental results demonstrate that PebbleSSD can reduce the amount of data written by log-structured file systems during log cleaning by up to 99%, and reduce file-system-level write amplification by up to 33% for a number of workloads.

Finally, previous proposals for SSDs with new interfaces suffer from the limitation caused by one-at-a-time design approach. To overcome this limitation, the thesis presents Willow, a user-programmable SSD with programmability as a central feature. Willow allows programmers to augment and extend the semantics of an SSD with application-specific features without compromising file system protections. We demonstrate the effectiveness and flexibility of Willow by implementing support for atomicity as an example. We find that defining SSD semantics in software is easy and beneficial, and that Willow makes it feasible for database transaction processing workload to benefit from a customized SSD interface.

Developing custom, reactive dashboards that deliver continuously updated visualizations,

has been a traditionally laborious task, due to the advanced technical expertise they require in

web development. MVVM frameworks have attempted to simplify this process, by offering a

template language that enables the declarative specification of dashboards, and by automatically

maintaining the displayed visualizations when the visualized data change. These frameworks,

however, still exhibit significant drawbacks. When mutations occur in underlying data sources,

developers have to observe and manually propagate (using imperative code) said mutations to

the framework, which still requires advanced skill-set and experience in web development. Additionally,

even though these frameworks automatically mutate the dependent visualizations (thus

absolving developers from manually performing this task), once mutations have been propagated

to the framework, their incremental rendering algorithms incur significant performance penalties,

especially when visualizing big data.

To address these issues, we present FORWARD, a framework that simplifies the development

of custom live dashboards. FORWARD offers a declarative template language

that simplifies the integration of (a) database and web service systems (such as Postgres and

GraphQL), (b) visualization libraries (such as Google Maps and HighCharts), and (c) data

processing functions (performing aggregations, ML computations, and more), thus enabling a

truly declarative specification of dashboards. This significantly lowers the technical expertise

needed for dashboard development, thus allowing programmers with limited experience in web

development (such as data analysts), to produce custom, information-dense, highly-reactive

dashboards. FORWARD templates describe dashboards as semi-structured views. As a result,

when mutations occur in the base-data of such views, FORWARD employs novel incremental

view maintenance techniques, that automatically propagate changes from data sources all the

way to the visual layer more efficiently than existing frameworks.

In this Thesis, we illustrate FORWARD’s template language and incremental rendering

algorithms, and show their superior algorithmic complexity compared to the state of the art.

Experimental results validate the complexity results and show that FORWARD’s incremental

rendering can be orders of magnitude more efficient than existing approaches. Line-of-code and

development time experiments show that the performance gains are accompanied by productivity

gains for developers that use FORWARD to build information-dense dashboards. Lastly, we

present ViDeTTe, a system that integrates FORWARD with Jupyter notebooks, and enables data

analysts to build Jupyter Notebooks with reactive visualizations. Notebook readers can then

directly interact with these visualizations to further explore the underlying data, a functionality

that is currently not supported in Jupyter Notebooks.

A sorted list is a collection of $\langle$ID, value$\rangle$ pairs sorted either by ID (called an ID-sorted list) or value (called a value-sorted list). Although simple, it is surprisingly the fundamental structure in a wide range of data management systems, e.g., databases, search engines, graph systems, and high-dimensional similarity search systems. Existing query processing over sorted lists were mainly optimized for past hardware, e.g., slow CPUs, small DRAM, and slow disks. However, with the emergence of new hardware, e.g., fast multi-core CPUs, big DRAM, fast SSDs, we find that many of existing design decisions become obsolete.

Motivated by this, in this dissertation, we investigate how to best leverage the characteristics of emerging hardware to accelerate query processing over sorted lists. First, we studied the impact of big memory and modern CPUs to ID-sorted list compression. We designed a new compression called MILC, which is SIMD-aware, cache-aware, and most importantly can answer queries directly over compressed lists. Second, we studied the impact of fast SSDs to ID-sorted list intersection. We developed and evaluated SSD-aware intersection algorithms that can skip unnecessary data pages to leverage SSDs’ fast random accesses. Finally, we folded the proposed hardware-specific techniques into a real-world modern application -- mass spectrometry search -- that involves query processing on both ID-sorted lists and value-sorted lists. We also developed domain-specific and data-specific optimizations besides hardware-specific optimizations. Putting them together, our new mass spectrometry search system is significantly faster than state-of-the-art systems.

Big data analytics open challenges for efficiently processing, moving and storing data. Existing research works focus on the algorithm design or applying hardware accelerators. However, in current systems,data transfer (from secondary storage or remote nodes) becomes an increasingly important but less-optimized performance bottleneck.

This thesis first presents HippogriffDB, a data-warehouse system that delivers efficient, scalable analytical performance with GPU and SSD. HippogriffDB achieves high efficiency by reconciling the bandwidth mismatch between GPU and IO with improved data transfer mechanism and data compression strategies. Experiment results demonstrate that HippogriffDB outperforms state-of-the-art GPU-based databases by up to 10×.

The thesis then presents SoftFlash. SoftFlash offloads some essential database functionalities from modern data warehouse applications into storage devices. By using hardware accelerators, on-chip processors, as well as software approaches, SoftFlash manages to reduce the data traffic over network and to improve the query execution time.

This thesis also covers experimental studies on the energy prospective of flash memory in the context of mobile computing. While the flash hardware is well known to be energy and power efficient, the software stack consumes significantly higher amount of power and energy.

Pre-2018 CSE ID: CS2004-0807

Pre-2018 CSE ID: CS2005-0846