III: Small: Task-aware Materialization for Fast Data Analytics

III：小型：用于快速数据分析的任务感知物化

• 批准号: 1910014
• 负责人: Paraschos Koutris
• 金额: $ 42.9万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-01 至 2023-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910014&HistoricalAwards=false
• 关键词: III; Small; Task; aware; Materialization

The data-to-knowledge pipeline is central to our data-driven world. It consumes data in raw format and then cleans, transforms, integrates, stores, processes, and analyzes the data to obtain knowledge in a usable format. Data analytics pipelines are complex and their workflows typically consist of several simpler tasks chained together. To speed up such pipelines, a ubiquitous optimization technique is to materialize the intermediate result of a task, so that downstream tasks can access the intermediate data as efficiently as possible. Existing materialization techniques suffer from several drawbacks, including prohibitively large cost in terms of storage and preprocessing time. To address these drawbacks, this proposal will develop smart materialization algorithms that can significantly accelerate the performance of data analytics applications. As a result, it will enable data scientists to obtain actionable insights faster and will impact research in areas such as biology, economics, sociology and the medical sciences. The goal of this project is to design, implement and evaluate materialization techniques using three novel ideas: task-aware materialization; fine-grained decisions on what and how to materialize; and multiple design points that can trade off space for time to achieve optimal performance of data analytics pipelines. The project will also explore how to design data structures for materialization that are adaptive to changes in the data and the downstream workload. From a theoretical viewpoint, the proposed research will aim to obtain theoretical guarantees on the tradeoff between space and time for materialization for different tasks. From a practical viewpoint, it will result in implementing and evaluating the developed algorithms on real-world data analytics applications, including visualization through lineage tracking, statistical inference, pattern retrieval in graphs and social network analysis.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

数据到知识的管道是我们这个数据驱动的世界的核心。它使用原始格式的数据，然后对数据进行清理、转换、集成、存储、处理和分析，以获得可用格式的知识。数据分析管道是复杂的，它们的工作流通常由几个简单的任务链接在一起组成。为了加快这种管道的速度，一种无处不在的优化技术是将任务的中间结果具体化，以便下游任务能够尽可能高效地访问中间数据。现有的物化技术有几个缺点，包括在存储和预处理时间方面的过高成本。为了解决这些缺点，本提案将开发智能物化算法，可以显着加快数据分析应用程序的性能。因此，它将使数据科学家能够更快地获得可操作的见解，并将影响生物学、经济学、社会学和医学等领域的研究。这个项目的目标是设计，实施和评估物化技术使用三个新颖的想法：任务感知物化；关于实现什么和如何实现的细粒度决策；多个设计点可以权衡空间和时间，以实现数据分析管道的最佳性能。该项目还将探索如何设计能够适应数据变化和下游工作负载的数据结构。从理论的角度来看，本文的研究旨在为不同任务的物化在空间和时间之间的权衡获得理论保证。从实际的角度来看，它将导致在现实世界的数据分析应用中实现和评估开发的算法，包括通过血统跟踪的可视化、统计推断、图形模式检索和社会网络分析。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Space-Time Tradeoffs for Conjunctive Queries with Access Patterns

具有访问模式的联合查询的时空权衡

• DOI: 10.1145/3584372.3588675
• 发表时间: 2023
• 期刊: Symposium on Principles of Database Systems (PODS
• 作者: Zhao, Hangdong;Deep, Shaleen;Koutris, Paraschos
• 通讯作者: Koutris, Paraschos

Fast Join Project Query Evaluation using Matrix Multiplication

• DOI: 10.1145/3318464.3380607
• 发表时间: 2020-02
• 期刊: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
• 作者: Shaleen Deep;Xiao Hu;Paraschos Koutris

General Space-Time Tradeoffs via Relational Queries

通过关系查询进行一般时空权衡

• 发表时间: 2023
• 期刊: Lecture Notes in Computer Science (WADS
• 作者: Deep, Shaleen;Hu, Xiao;Koutris, Paraschos
• 通讯作者: Koutris, Paraschos

Ranked Enumeration of Join Queries with Projections

• DOI: 10.14778/3510397.3510401
• 发表时间: 2022-01
• 期刊: ArXiv
• 作者: Shaleen Deep;Xiao Hu;Paraschos Koutris

Enumeration Algorithms for Conjunctive Queries with Projection

带投影的联合查询的枚举算法

• DOI: 10.4230/lipics.icdt.2021.14
• 发表时间: 2021
• 期刊: ICDT
• 作者: Deep, Shaleen;Hu, Xiao;Koutris, Paraschos
• 通讯作者: Koutris, Paraschos