.png){kind=icon}
返回
Towards Parameterized Hardness on Maintaining Conjunctive Queries
.png){kind=icon}
PRE
AI
DOI：10.1145/3801917.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了在单元组更新下动态维护固定自连接自由合取查询结果时的精细粒度复杂度。先前工作表明，自由连通查询可以在更新时间 O(D^δ) 下维护，其中 δ ∈ [0.5, 1]，D 为当前数据库大小。然而，已知最佳上界 O(D) 与下界 Ω(D^{0.5-ε})（对任意 ε > 0）之间存在差距。我们通过引入两个结构参数（高度 k 和维度 d）来量化合取查询的动态复杂度，从而缩小这一差距。我们建立了新的精细粒度下界，表明任何维护具有这些参数的查询的算法，除非公认猜想失败，否则必须产生更新时间 Ω(D^{1-1/(max(k,d)-ε)})。这为维护自由连通查询提供了首个超线性下界，并表明当考虑任意大的 k 和 d 时当前算法的紧致性。作为我们下界工作的补充，我们识别了一个数据相关参数——广义 H 指数 h(D)，其上界为 D^{1/d}，并设计了一个高效算法来维护星查询（高度为 2 的自由连通查询的常见类别）。该算法实现了实例特定的更新时间 O(h(D)d^{-1}) 和线性空间 O(D)，在有利情况下匹配我们的参数化下界并提供实例特定的性能。
Keyword:
conjunctive query
fine-grained complexity
query maintenance
dynamic algorithms
期刊
P
IF:
0
论文数:
31
被引数:
0
机构
引用论文
暂无论文信息