MSO queries on trees: enumerating answers under updates
MSO queries on trees: enumerating answers under updates
复制标题
MSO 对树的查询：枚举更新下的答案
DOI：
10.1145/2603088.2603137
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Wim Martens
中科院分区：
文献类型：
--
作者：
Katja Losemann;Wim Martens
我们调查有效的视图维护MSO可定义的查询树，或更准确地说，有效枚举的答案MSO可定义的查询词和树，受到本地更新。对于单词，我们展示了一个算法，该算法使用了O（n）的预处理阶段，并枚举了它们之间O（logn）延迟的答案。当单词被更新时，该算法可以避免重复昂贵的预处理，并在O（logn）时间内重新启动枚举阶段。对于树，我们的算法使用O（n）的预处理时间，枚举答案具有O（log2n）的延迟，并可以在O（log2n）的时间内重新开始枚举后，收到更新的树。这大大提高了从头开始重新计算查询答案的成本。我们的算法和复杂性的结果，在本文中提出的节点选择自动机表示的MSO查询。
We investigate efficient view maintenance for MSO-definable queries over trees or, more precisely, efficient enumeration of answers to MSO-definable queries over words and trees which are subject to local updates. For words we exhibit an algorithm that uses anO(n) preprocessing phase and enumerates answers withO(logn) delay between them. When the word is updated, the algorithm can avoid repeating expensive preprocessing and restart the enumeration phase withinO(logn) time. For trees, our algorithm usesO(n) preprocessing time, enumerates answers withO(log2n) delay, and can restart enumeration withinO(log2n) time after receiving an update to the tree. This significantly improves the cost of recomputing the answers of a query from scratch. Our algorithms and complexity results in the paper are presented in terms of node-selecting automata representing the MSO queries.