Publications (85)
S-Store: Streaming Meets Transaction Processing
John Meehan, Nesime Tatbul, Stan Zdonik +10
Stream processing addresses the needs of real-time applications. Transaction processing addresses the coordination and safety of short atomic computations. Heretofore, these two mo…
Improving DBMS Scheduling Decisions with Fine-grained Performance Prediction on Concurrent Queries -- Extended
Ziniu Wu, Markos Markakis, Chunwei Liu +4
Query scheduling is a critical task that directly impacts query performance in database management systems (DBMS). Deeply integrated schedulers, which require changes to DBMS inter…
Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads
Jialin Ding, Vikram Nathan, Mohammad Alizadeh +1
Filtering data based on predicates is one of the most fundamental operations for any modern data warehouse. Techniques to accelerate the execution of filter expressions include clu…
IDEBench: A Benchmark for Interactive Data Exploration
Philipp Eichmann, Carsten Binnig, Tim Kraska +1
Existing benchmarks for analytical database systems such as TPC-DS and TPC-H are designed for static reporting scenarios. The main metric of these benchmarks is the performance of…
AgentSM: Semantic Memory for Agentic Text-to-SQL
Asim Biswal, Chuan Lei, Xiao Qin +3
Recent advances in LLM-based Text-to-SQL have achieved remarkable gains on public benchmarks such as BIRD and Spider. Yet, these systems struggle to scale in realistic enterprise s…
DBOS: A Proposal for a Data-Centric Operating System
Michael Cafarella, David DeWitt, Vijay Gadepally +5
Current operating systems are complex systems that were designed before today's computing environments. This makes it difficult for them to meet the scalability, heterogeneity, ava…
Partitioned Learned Bloom Filter
Kapil Vaidya, Eric Knorr, Tim Kraska +1
Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives. Recently, variations…
Fault-Tolerant Entity Resolution with the Crowd
Anja Gruenheid, Besmira Nushi, Tim Kraska +2
In recent years, crowdsourcing is increasingly applied as a means to enhance data quality. Although the crowd generates insightful information especially for complex problems such…
PIQL: Success-Tolerant Query Processing in the Cloud
Michael Armbrust, Kristal Curtis, Tim Kraska +3
Newly-released web applications often succumb to a "Success Disaster," where overloaded database machines and resulting high response times destroy a previously good user experienc…
Extract-Transform-Load for Video Streams
Ferdinand Kossmann, Ziniu Wu, Eugenie Lai +4
Social media, self-driving cars, and traffic cameras produce video streams at large scales and cheap cost. However, storing and querying video at such scales is prohibitively expen…
Getting It All from the Crowd
Beth Trushkowsky, Tim Kraska, Michael J. Franklin +1
Hybrid human/computer systems promise to greatly expand the usefulness of query processing by incorporating the crowd for data gathering and other tasks. Such systems raise many da…
Learned Garbage Collection
Lujing Cen, Ryan Marcus, Hongzi Mao +3
Several programming languages use garbage collectors (GCs) to automatically manage memory for the programmer. Such collectors must decide when to look for unreachable objects to fr…
Stage: Query Execution Time Prediction in Amazon Redshift
Ziniu Wu, Ryan Marcus, Zhengchun Liu +7
Query performance (e.g., execution time) prediction is a critical component of modern DBMSes. As a pioneering cloud data warehouse, Amazon Redshift relies on an accurate execution…
Recursive Language Models
Alex L. Zhang, Tim Kraska, Omar Khattab
We study allowing large language models (LLMs) to process arbitrarily long prompts through the lens of inference-time scaling. We propose Recursive Language Models (RLMs), a genera…
MDCC: Multi-Data Center Consistency
Tim Kraska, Gene Pang, Michael J. Franklin +1
Replicating data across multiple data centers not only allows moving the data closer to the user and, thus, reduces latency for applications, but also increases the availability in…
Controlling False Discoveries During Interactive Data Exploration
Zheguang Zhao, Lorenzo De Stefani, Emanuel Zgraggen +3
Recent tools for interactive data exploration significantly increase the chance that users make false discoveries. The crux is that these tools implicitly allow the user to test a…
Towards Practical Learned Indexing
Mihail Stoian, Andreas Kipf, Ryan Marcus +1
Latest research proposes to replace existing index structures with learned models. However, current learned indexes tend to have many hyperparameters, often do not provide any erro…
PipeRAG: Fast Retrieval-Augmented Generation via Algorithm-System Co-design
Wenqi Jiang, Shuai Zhang, Boran Han +3
Retrieval-augmented generation (RAG) can enhance the generation quality of large language models (LLMs) by incorporating external token databases. However, retrievals from large da…
ALEX: An Updatable Adaptive Learned Index
Jialin Ding, Umar Farooq Minhas, Jia Yu +9
Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the…
ODIN: A NL2SQL Recommender to Handle Schema Ambiguity
Kapil Vaidya, Abishek Sankararaman, Jialin Ding +4
NL2SQL (natural language to SQL) systems translate natural language into SQL queries, allowing users with no technical background to interact with databases and create tools like r…
SEED: Domain-Specific Data Curation With Large Language Models
Zui Chen, Lei Cao, Sam Madden +7
Data curation tasks that prepare data for analytics are critical for turning data into actionable insights. However, due to the diverse requirements of applications in different do…
Learned Indexes for a Google-scale Disk-based Database
Hussam Abu-Libdeh, Deniz Altınbüken, Alex Beutel +7
There is great excitement about learned index structures, but understandable skepticism about the practicality of a new method uprooting decades of research on B-Trees. In this pap…
SOSD: A Benchmark for Learned Indexes
Andreas Kipf, Ryan Marcus, Alexander van Renen +4
A groundswell of recent work has focused on improving data management systems with learned components. Specifically, work on learned index structures has proposed replacing traditi…
VizML: A Machine Learning Approach to Visualization Recommendation
Kevin Z. Hu, Michiel A. Bakker, Stephen Li +2
Data visualization should be accessible for all analysts with data, not just the few with technical expertise. Visualization recommender systems aim to lower the barrier to explori…
Context-Aware Parse Trees
Fangke Ye, Shengtian Zhou, Anand Venkat +8
The simplified parse tree (SPT) presented in Aroma, a state-of-the-art code recommendation system, is a tree-structured representation used to infer code semantics by capturing pro…
Unknown Examples & Machine Learning Model Generalization
Yeounoh Chung, Peter J. Haas, Eli Upfal +1
Over the past decades, researchers and ML practitioners have come up with better and better ways to build, understand and improve the quality of ML models, but mostly under the key…
Deep Research is the New Analytics System: Towards Building the Runtime for AI-Driven Analytics
Matthew Russo, Tim Kraska
With advances in large language models (LLMs), researchers are creating new systems that can perform AI-driven analytics over large unstructured datasets. Recent work has explored…
VizRec: A framework for secure data exploration via visual representation
Lorenzo De Stefani, Leonhard F. Spiegelberg, Tim Kraska +1
Visual representations of data (visualizations) are tools of great importance and widespread use in data analytics as they provide users visual insight to patterns in the observed…
PBench: Workload Synthesizer with Real Statistics for Cloud Analytics Benchmarking
Yan Zhou, Chunwei Liu, Bhuvan Urgaonkar +11
Cloud service providers commonly use standard benchmarks like TPC-H and TPC-DS to evaluate and optimize cloud data analytics systems. However, these benchmarks rely on fixed query…
Revisiting Reuse in Main Memory Database Systems
Kayhan Dursun, Carsten Binnig, Ugur Cetintemel +1
Reusing intermediates in databases to speed-up analytical query processing has been studied in the past. Existing solutions typically require intermediate results of individual ope…
VizNet: Towards A Large-Scale Visualization Learning and Benchmarking Repository
Kevin Hu, Neil Gaikwad, Michiel Bakker +7
Researchers currently rely on ad hoc datasets to train automated visualization tools and evaluate the effectiveness of visualization designs. These exemplars often lack the charact…
The Cambridge Report on Database Research
Anastasia Ailamaki, Samuel Madden, Daniel Abadi +43
On October 19 and 20, 2023, the authors of this report convened in Cambridge, MA, to discuss the state of the database research field, its recent accomplishments and ongoing challe…
Leveraging Transitive Relations for Crowdsourced Joins
Jiannan Wang, Guoliang Li, Tim Kraska +2
The development of crowdsourced query processing systems has recently attracted a significant attention in the database community. A variety of crowdsourced queries have been inves…
LSI: A Learned Secondary Index Structure
Andreas Kipf, Dominik Horn, Pascal Pfeil +2
Learned index structures have been shown to achieve favorable lookup performance and space consumption compared to their traditional counterparts such as B-trees. However, most lea…
TailorSQL: An NL2SQL System Tailored to Your Query Workload
Kapil Vaidya, Jialin Ding, Sebastian Kosak +7
NL2SQL (natural language to SQL) translates natural language questions into SQL queries, thereby making structured data accessible to non-technical users, serving as the foundation…
MLSys: The New Frontier of Machine Learning Systems
Alexander Ratner, Dan Alistarh, Gustavo Alonso +66
Machine learning (ML) techniques are enjoying rapidly increasing adoption. However, designing and implementing the systems that support ML models in real-world deployments remains…
The End of Slow Networks: It's Time for a Redesign
Carsten Binnig, Andrew Crotty, Alex Galakatos +2
Next generation high-performance RDMA-capable networks will require a fundamental rethinking of the design and architecture of modern distributed DBMSs. These systems are commonly…
MISIM: A Neural Code Semantics Similarity System Using the Context-Aware Semantics Structure
Fangke Ye, Shengtian Zhou, Anand Venkat +10
Code semantics similarity can be used for many tasks such as code recommendation, automated software defect correction, and clone detection. Yet, the accuracy of such systems has n…
Abacus: A Cost-Based Optimizer for Semantic Operator Systems
Matthew Russo, Chunwei Liu, Sivaprasad Sudhir +4
LLMs enable an exciting new class of data processing applications over large collections of unstructured documents. Several new programming frameworks have enabled developers to bu…
The Case for Learned Index Structures
Tim Kraska, Alex Beutel, Ed H. Chi +2
Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a re…
Tupleware: Redefining Modern Analytics
Andrew Crotty, Alex Galakatos, Kayhan Dursun +3
There is a fundamental discrepancy between the targeted and actual users of current analytics frameworks. Most systems are designed for the data and infrastructure of the Googles a…
Bao: Learning to Steer Query Optimizers
Ryan Marcus, Parimarjan Negi, Hongzi Mao +3
Query optimization remains one of the most challenging problems in data management systems. Recent efforts to apply machine learning techniques to query optimization challenges hav…
The Case for Learned In-Memory Joins
Ibrahim Sabek, Tim Kraska
In-memory join is an essential operator in any database engine. It has been extensively investigated in the database literature. In this paper, we study whether exploiting the CDF-…
Carnot: Interpretable, Interactive, and Optimized Execution of Deep Research Queries
Matthew Russo, Yash Agarwal, Tianyu Li +5
Enterprises increasingly seek to query data lakes using natural language via AI-driven tools like semantic operators or deep research agents. However, the latter operates as an opa…
ExSample: Efficient Searches on Video Repositories through Adaptive Sampling
Oscar Moll, Favyen Bastani, Sam Madden +3
Capturing and processing video is increasingly common as cameras become cheaper to deploy. At the same time, rich video understanding methods have progressed greatly in the last de…
Benchmarking Learned Indexes
Ryan Marcus, Andreas Kipf, Alexander van Renen +5
Recent advancements in learned index structures propose replacing existing index structures, like B-Trees, with approximate learned models. In this work, we present a unified bench…
Tailwind: A Practical Framework for Query Accelerators
Geoffrey X. Yu, Ryan Marcus, Tim Kraska
Relational database management systems (RDBMSes) can process general-purpose queries, but often have lower performance compared to custom-built solutions for specific queries. For…
Sherlock: A Deep Learning Approach to Semantic Data Type Detection
Madelon Hulsebos, Kevin Hu, Michiel Bakker +5
Correctly detecting the semantic type of data columns is crucial for data science tasks such as automated data cleaning, schema matching, and data discovery. Existing data preparat…
Parachute: Single-Pass Bi-Directional Information Passing
Mihail Stoian, Andreas Zimmerer, Skander Krid +4
Sideways information passing is a well-known technique for mitigating the impact of large build sides in a database query plan. As currently implemented in production systems, side…
Parallel External Sorting of ASCII Records Using Learned Models
Ani Kristo, Tim Kraska
External sorting is at the core of many operations in large-scale database systems, such as ordering and aggregation queries for large result sets, building indexes, sort-merge joi…
Automated Data Slicing for Model Validation:A Big data - AI Integration Approach
Yeounoh Chung, Tim Kraska, Neoklis Polyzotis +2
As machine learning systems become democratized, it becomes increasingly important to help users easily debug their models. However, current data tools are still primitive when it…
A Declarative System for Optimizing AI Workloads
Chunwei Liu, Matthew Russo, Michael Cafarella +7
A long-standing goal of data management systems has been to build systems which can compute quantitative insights over large corpora of unstructured data in a cost-effective manner…
Chiller: Contention-centric Transaction Execution and Data Partitioning for Modern Networks
Erfan Zamanian, Julian Shun, Carsten Binnig +1
Distributed transactions on high-overhead TCP/IP-based networks were conventionally considered to be prohibitively expensive and thus were avoided at all costs. To that end, the pr…
MLI: An API for Distributed Machine Learning
Evan R. Sparks, Ameet Talwalkar, Virginia Smith +6
MLI is an Application Programming Interface designed to address the challenges of building Machine Learn- ing algorithms in a distributed setting based on data-centric computing. I…
Cortex: Harnessing Correlations to Boost Query Performance
Vikram Nathan, Jialin Ding, Tim Kraska +1
Databases employ indexes to filter out irrelevant records, which reduces scan overhead and speeds up query execution. However, this optimization is only available to queries that f…
KramaBench: A Benchmark for AI Systems on Data-to-Insight Pipelines over Data Lakes
Eugenie Lai, Gerardo Vitagliano, Ziyu Zhang +16
Discovering insights from a real-world data lake potentially containing unclean, semi-structured, and unstructured data requires a variety of data processing tasks, ranging from ex…
Learning Multi-dimensional Indexes
Vikram Nathan, Jialin Ding, Mohammad Alizadeh +1
Scanning and filtering over multi-dimensional tables are key operations in modern analytical database engines. To optimize the performance of these operations, databases often crea…
The End of a Myth: Distributed Transactions Can Scale
Erfan Zamanian, Carsten Binnig, Tim Kraska +1
The common wisdom is that distributed transactions do not scale. But what if distributed transactions could be made scalable using the next generation of networks and a redesign of…
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
Sanjay Krishnan, Jiannan Wang, Michael J. Franklin +2
Materialized views (MVs), stored pre-computed results, are widely used to facilitate fast queries on large datasets. When new records arrive at a high rate, it is infeasible to con…
LEA: A Learned Encoding Advisor for Column Stores
Lujing Cen, Andreas Kipf, Ryan Marcus +1
Data warehouses organize data in a columnar format to enable faster scans and better compression. Modern systems offer a variety of column encodings that can reduce storage footpri…
Estimating the Impact of Unknown Unknowns on Aggregate Query Results
Yeounoh Chung, Michael Lind Mortensen, Carsten Binnig +1
It is common practice for data scientists to acquire and integrate disparate data sources to achieve higher quality results. But even with a perfectly cleaned and merged data set,…
FactorJoin: A New Cardinality Estimation Framework for Join Queries
Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh +2
Cardinality estimation is one of the most fundamental and challenging problems in query optimization. Neither classical nor learning-based methods yield satisfactory performance wh…
Neo: A Learned Query Optimizer
Ryan Marcus, Parimarjan Negi, Hongzi Mao +5
Query optimization is one of the most challenging problems in database systems. Despite the progress made over the past decades, query optimizers remain extremely complex component…
Flow-Loss: Learning Cardinality Estimates That Matter
Parimarjan Negi, Ryan Marcus, Andreas Kipf +4
Previous approaches to learned cardinality estimation have focused on improving average estimation error, but not all estimates matter equally. Since learned models inevitably make…
Smallify: Learning Network Size while Training
Guillaume Leclerc, Manasi Vartak, Raul Castro Fernandez +2
As neural networks become widely deployed in different applications and on different hardware, it has become increasingly important to optimize inference time and model size along…
TagMe: GPS-Assisted Automatic Object Annotation in Videos
Songtao He, Favyen Bastani, Mohammad Alizadeh +4
Training high-accuracy object detection models requires large and diverse annotated datasets. However, creating these data-sets is time-consuming and expensive since it relies on h…
Defeating duplicates: A re-design of the LearnedSort algorithm
Ani Kristo, Kapil Vaidya, Tim Kraska
LearnedSort is a novel sorting algorithm that, unlike traditional methods, uses fast ML models to boost the sorting speed. The models learn to estimate the input's distribution and…
Fast Mapping onto Census Blocks
Jeremy Kepner, Andreas Kipf, Darren Engwirda +21
Pandemic measures such as social distancing and contact tracing can be enhanced by rapidly integrating dynamic location data and demographic data. Projecting billions of longitude…
LISA: Towards Learned DNA Sequence Search
Darryl Ho, Jialin Ding, Sanchit Misra +4
Next-generation sequencing (NGS) technologies have enabled affordable sequencing of billions of short DNA fragments at high throughput, paving the way for population-scale genomics…
A Data Quality Metric (DQM): How to Estimate The Number of Undetected Errors in Data Sets
Yeounoh Chung, Sanjay Krishnan, Tim Kraska
Data cleaning, whether manual or algorithmic, is rarely perfect leaving a dataset with an unknown number of false positives and false negatives after cleaning. In many scenarios, q…
Archi: Agentic Operations at the CMS Experiment
Pietro Lugato, Luca Lavezzo, Jason Mohoney +16
We present Archi, an open-source, end-to-end framework for scientific collaborations that combines the systematic ingestion and organization of heterogeneous data sources with the…
ARDA: Automatic Relational Data Augmentation for Machine Learning
Nadiia Chepurko, Ryan Marcus, Emanuel Zgraggen +3
Automatic machine learning (\AML) is a family of techniques to automate the process of training predictive models, aiming to both improve performance and make machine learning more…
AutoSLO: Practical Latency SLOs on Cloud Data Warehouses -- Extended Version
Markos Markakis, Tim Kraska
AutoSLO is a framework that automatically manages compute clusters in cloud data warehouses to meet latency service-level objectives while reducing resource waste, using proactive…
SQLens: An End-to-End Framework for Error Detection and Correction in Text-to-SQL
Yue Gong, Chuan Lei, Xiao Qin +3
Text-to-SQL systems translate natural language (NL) questions into SQL queries, enabling non-technical users to interact with structured data. While large language models (LLMs) ha…
SuperNeurons: Dynamic GPU Memory Management for Training Deep Neural Networks
Linnan Wang, Jinmian Ye, Yiyang Zhao +5
Going deeper and wider in neural architectures improves the accuracy, while the limited GPU DRAM places an undesired restriction on the network design domain. Deep Learning (DL) pr…
CrowdER: Crowdsourcing Entity Resolution
Jiannan Wang, Tim Kraska, Michael J. Franklin +1
Entity resolution is central to data integration and data cleaning. Algorithmic approaches have been improving in quality, but remain far from perfect. Crowdsourcing platforms offe…
RadixSpline: A Single-Pass Learned Index
Andreas Kipf, Ryan Marcus, Alexander van Renen +4
Recent research has shown that learned models can outperform state-of-the-art index structures in size and lookup performance. While this is a very promising result, existing learn…
FITing-Tree: A Data-aware Index Structure
Alex Galakatos, Michael Markovitch, Carsten Binnig +2
Index structures are one of the most important tools that DBAs leverage to improve the performance of analytics and transactional workloads. However, building several indexes over…
Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD -- Extended Version
Geoffrey X. Yu, Ziniu Wu, Ferdi Kossmann +5
Modern organizations manage their data with a wide variety of specialized cloud database engines (e.g., Aurora, BigQuery, etc.). However, designing and managing such infrastructure…
How I Learned to Stop Worrying and Love Re-optimization
Matthew Perron, Zeyuan Shang, Tim Kraska +1
Cost-based query optimizers remain one of the most important components of database management systems for analytic workloads. Though modern optimizers select plans close to optima…
STAR: Statistical Tests with Auditable Results
Sacha Servan-Schreiber, Olga Ohrimenko, Tim Kraska +1
We present STAR: a novel system aimed at solving the complex issue of "p-hacking" and false discoveries in scientific studies. STAR provides a concrete way for ensuring the applica…
The Expected Optimal Labeling Order Problem for Crowdsourced Joins and Entity Resolution
Jiannan Wang, Guoliang Li, Tim Kraska +2
In the SIGMOD 2013 conference, we published a paper extending our earlier work on crowdsourced entity resolution to improve crowdsourced join processing by exploiting transitive re…
Bounding the Last Mile: Efficient Learned String Indexing
Benjamin Spector, Andreas Kipf, Kapil Vaidya +3
We introduce the RadixStringSpline (RSS) learned index structure for efficiently indexing strings. RSS is a tree of radix splines each indexing a fixed number of bytes. RSS approac…
TuPAQ: An Efficient Planner for Large-scale Predictive Analytic Queries
Evan R. Sparks, Ameet Talwalkar, Michael J. Franklin +2
The proliferation of massive datasets combined with the development of sophisticated analytical techniques have enabled a wide variety of novel applications such as improved produc…
When Are Learned Models Better Than Hash Functions?
Ibrahim Sabek, Kapil Vaidya, Dominik Horn +2
In this work, we aim to study when learned models are better hash functions, particular for hash-maps. We use lightweight piece-wise linear models to replace the hash functions as…