Data Systems Seminar Series (2018-2019)

Data structures are critical in any data-driven scenario, and they define the behavior of modern data systems. However, they are notoriously hard to design due to a massive design space and the dependence of performance on workload and hardware which evolve continuously. In this talk, we ask two questions: What if we knew how many and which data structures are possible to design? What if we could compute the expected performance of a data structure design on a given workload and hardware without having to implement it and without even having access to the target machine? We will discuss our quest for 1) the first principles of data structures, 2) design continuums that make it possible to automate design, and 3) self-designing systems that can morph between what we now consider fundamentally different structures. We will draw examples from the NoSQL key-value store design space and discuss how to accelerate them and balance space-time tradeoffs.

Mohammad Sadoghi is an Assistant Professor of Computer Science at the University of California, Davis. Formerly, he was an Assistant Professor at Purdue University and Research Staff Member at IBM T.J. Watson Research Center. He received his Ph.D. from the Computer Science Department at the University of Toronto in 2013. His research spans all facets of secure and massive-scale data management. At UC Davis, he leads the ExpoLab research group with the aim to pioneer a new exploratory data platform—referred to as ExpoDB—a distributed ledger that unifies secure transactional and real-time analytical processing, all centered around a democratic and decentralized computational model. Prof. Sadoghi has over 60 publications and has filed 34 U.S. patents. His SIGMOD'11 paper was awarded the EPTS Innovative Principles Award, his EDBT'11 paper was selected as one of the best EDBT papers in 2011, and his ESWC'16 paper won the Best In-Use Paper Award. He is serving as Workshop/Tutorial Co-Chair at Middleware'18, has served as the PC Chair (Industry Track) at ACM DEBS'17, co-chaired a new workshop series, entitled Active, at both ICDE and Middleware, and co-chaired the Doctoral Symposium at Middleware'17. He served as the Area Editor for Transaction Processing in the Encyclopedia of Big Data Technologies by Springer. He is co-authoring a book on "Transaction Processing on Modern Hardware" as part of Morgan & Claypool Synthesis Lectures on Data Management. He regularly serves on the program committee of SIGMOD, VLDB, ICDE, EDBT, Middleware, ICDCS, DEBS, and ICSOC.

Hierarchical Dense Subgraph Discovery: Models, Algorithms, Applications

Online analytics, in most advanced scientific, business, and defense applications, rely heavily on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). ACQs continuously aggregate streaming data and periodically produce results such as max or average over a given window of the latest data.  It was shown that in processing ACQs it is beneficial to use incremental evaluation, which involves storing and reusing calculations performed over the unchanged parts of the window, rather than performing the re-evaluation of the entire window after each update.  In this talk, we examine how the principle of sharing is applied in the partial and final aggregation techniques and present our SlickDeque and WeaveShare techniques that optimize the execution of multi-ACQs in single and multiple computing nodes.

Adaptive Scalable Analytics in Multi-Engine Environments

Big Data analytics in science and industry are performed on a range of heterogeneous data stores, both traditional and modern, and on a diversity of query engines. Workflows are difficult to design and implement since they span a variety of systems. To reduce development time and processing costs, some automation is needed. In this talk we will present a new platform to manage analytics workflows. The platform enables workflow design, execution, analysis and optimization with respect to time efficiency, over multiple execution engines. Such configurations are emerging as a common paradigm used to combine analysis of unstructured data with analysis of structured data (e.g., NoSQL plus SQL). We focus on the usability of the platform by users with various expertise, the automation of the analysis and optimization of execution, as well as the effect of optimization on workflow execution. The platform performs also multi-workflow optimisation and workflow recalibration. The talk will finish with some plans for future research on data management optimization on hybrid infrastructures, i.e. infrastructures that comprise multiple sites heterogeneous parts and combine private clusters and public resources.

Meta-Analysis for Retrieval Experiments Involving Multiple Test Collections

Dr. Ian Soboroff is a computer scientist and leader of the Retrieval Group at the National Institute of Standards and Technology (NIST). The Retrieval Group organizes the Text REtrieval Conference (TREC), the Text Analysis Conference (TAC), and the TREC Video Retrieval Evaluation (TRECVID). These are all large, community-based research workshops that drive the state-of-the-art in information retrieval, video search, web search, information extraction, text summarization and other areas of information access. He has co-authored many publications in information retrieval evaluation, test collection building, text filtering, collaborative filtering, and intelligent software agents. His current research interests include building test collections for social media environments and nontraditional retrieval tasks.

Data Management meets Information Theory

Dan Suciu is a Professor in Computer Science at the University of Washington. He received his Ph.D. from the University of Pennsylvania in 1995, was a principal member of the technical staff at AT&T Labs and joined the University of Washington in 2000. Suciu is conducting research in data management, with an emphasis on topics related to Big Data and data sharing, such as probabilistic data, data pricing, parallel data processing, data security. He is a co-author of two books Data on the Web: from Relations to Semistructured Data and XML, 1999, and Probabilistic Databases, 2011. He is a Fellow of the ACM, holds twelve US patents, received the best paper award in SIGMOD 2000 and ICDT 2013, the ACM PODS Alberto Mendelzon Test of Time Award in 2010 and in 2012, the 10 Year Most Influential Paper Award in ICDE 2013, the VLDB Ten Year Best Paper Award in 2014, and is a recipient of the NSF Career Award and of an Alfred P. Sloan Fellowship. Suciu serves on the VLDB Board of Trustees, and is an associate editor for the Journal of the ACM, VLDB Journal, ACM TWEB, and Information Systems and is a past associate editor for ACM TODS and ACM TOIS. Suciu's PhD students Gerome Miklau, Christopher Re and Paris Koutris received the ACM SIGMOD Best Dissertation Award in 2006, 2010, and 2016 respectively, and Nilesh Dalvi was a runner up in 2008.

Indexing is a game of tradeoffs: Organize your data now and be rewarded with lower read latencies later.  The question of whether, how, or when to organize has led to a proliferation of many different, often highly-specialized index structures.  In this talk, I present an alternative that replaces the the holistic tradeoff decisions made by classical index structures with smaller, localized organizational transformations.  This approach, which we call Just-in-Time Data Structures (JITDs), is based on a grammar for data structure instances.  A sentence in this grammar corresponds to a specific physical layout, and many classical data structures can be described as syntactic restrictions on this grammar.  Mirroring a just-in-time compiler, a JITD incrementally replaces phrases in a sentence (i.e., physical sub-structures) with different, ideally more efficient ones.  This replacement happens in the background, without blocking reader threads for longer than an atomic pointer swap.  JITDs are competitive with existing, commonly-used data structures in common-case scenarios, while exhibiting better performance in dynamic settings. I will present our foundational work on JITDs, and outline some of our more recent work on automatic rewrite policy optimization.

(This work is supported by NSF Awards IIS-1617586 and CNS-1629791)

Oliver Kennedy is an assistant professor at the University at Buffalo.  He earned his PhD from Cornell University in 2011 and now leads the Online Data Interactions (ODIn) lab, which operates at the intersection of databases and programming languages.  Oliver is the recipient of an NSF CAREER award, UB's Exceptional Scholar Award, and the UB SEAS Early Career Teacher of the Year Award.  Several of his papers have been invited to "Best of" compilations from SIGMOD and VLDB.  The ODIn lab is currently exploring uncertain data management, just-in-time data structure design, and "small data" management.

The talk will also cover the architectural aspects of the systems and how it has been integrated with the rest of the components of the LeanXcale database, the distributed storage engine and the distributed SQL query engine. It will also be presented the underpinnings on how to blend operational and analytical workloads through innovations on the storage engine combined with a distributed OLAP query engine.

We are witnessing the increasing use of warehouse-scale computers to analyze massive datasets quickly. This poses two challenges for database systems. The first challenge is interoperability with established analytics libraries and tools. Massive datasets often consist of small images (arrays) in file formats like HDF5 and FITS. We will first present ArrayBridge, an open-source I/O library that allows processing with SQL, SciDB or TensorFlow without converting between file formats. ArrayBridge can transparently optimize data placement to make I/O more than 300X faster than directly reading small files. The second challenge is scalability, as warehouse-scale computers expose communication bottlenecks in foundational data processing operations. We will present a data shuffling algorithm that carefully uses RDMA to transmit data up to 4X faster than MPI. We will then present GRASP, an aggregation algorithm for high-cardinality parallel aggregation. By carefully scheduling data transfers to leverage similarity, GRASP avoids unscaleable all-to-all communication and completes the aggregation more than 3X faster than repartitioning. We conclude by highlighting additional challenges that need to be overcome to scale database systems to massive computers.

Spyros Blanas is an assistant professor in the Department of Computer Science and Engineering at The Ohio State University. His research interest is high performance database systems, and his current goal is to build a database system for high-end computing facilities. He has received the IEEE TCDE Rising Star award and a Google Research Faculty award. He completed his Ph.D. at the University of Wisconsin–Madison where part of his Ph.D. dissertation was commercialized in Microsoft SQL Server as the Hekaton in-memory transaction processing engine.