Space-Time Tradeoffs for Conjunctive Queries with Access Patterns
Space-Time Tradeoffs for Conjunctive Queries with Access Patterns
复制标题
具有访问模式的联合查询的时空权衡
DOI：
10.1145/3584372.3588675
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Koutris, Paraschos
中科院分区：
文献类型：
--
作者：
Zhao, Hangdong;Deep, Shaleen;Koutris, Paraschos
在本文中，我们调查的空间-时间权衡回答连接查询的访问模式（CQAP）。其目标是在初始预处理阶段创建一个节省空间的数据结构，并在在线阶段使用它来回答（多个）查询。以前的工作已经开发了数据结构，权衡空间使用的回答时间查询的实际利益，如路径和三角形查询。然而，这些办法缺乏一个全面的框架，而且不能普遍适用。我们的主要贡献是一个通用的算法框架，获得任何CQAP的时空权衡。我们的框架建立在PANDA算法和树分解技术的基础上。我们证明，我们的框架捕获所有国家的最先进的权衡，独立产生的各种查询。此外，我们表现出令人惊讶的改进，在现有的文献中已知的最先进的权衡可达性查询。
In this paper, we investigate space-time tradeoffs for answering conjunctive queries with access patterns (CQAPs). The goal is to create a space-efficient data structure in an initial preprocessing phase and use it for answering (multiple) queries in an online phase. Previous work has developed data structures that trades off space usage for answering time for queries of practical interest, such as the path and triangle query. However, these approaches lack a comprehensive framework and are not generalizable. Our main contribution is a general algorithmic framework for obtaining space-time tradeoffs for any CQAP. Our framework builds upon the PANDA algorithm and tree decomposition techniques. We demonstrate that our framework captures all state-of-the-art tradeoffs that were independently produced for various queries. Further, we show surprising improvements over the state-of-the-art tradeoffs known in the existing literature for reachability queries.
登录
查看更多内容
空间/时间权衡的条件下界
DOI：
--
发表时间：
2017
期刊：
Workshop on Algorithms and Data Structures
影响因子：
--
作者：
Isaac Goldstein;T. Kopelowitz;Moshe Lewenstein;E. Porat
通讯作者：
E. Porat
枚举 CSP 解决方案的结构易处理性
影响因子：
1.6
作者：
G. Greco;Francesco Scarcello
通讯作者：
Francesco Scarcello
稀疏图中更快的近似距离查询和紧凑路由
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
R. Agarwal;Brighten Godfrey;Sariel Har
通讯作者：
Sariel Har
几个字符串索引问题的硬度
影响因子：
1.1
作者：
Kasper Green Larsen;J. Munro;Sharma V. Thankachan;Jesper Sindahl;Nielsen Problems;Jesper Sindahl Nielsen
通讯作者：
Jesper Sindahl Nielsen
影响因子：
1.8
作者：
Khamis, Mahmoud Abo;Kolaitis, Phokion G.;Ngo, Hung Q.;Suciu, Dan
通讯作者：
Suciu, Dan