Space-efficient Query Evaluation over Probabilistic Event Streams
Space-efficient Query Evaluation over Probabilistic Event Streams
复制标题
DOI：
10.1145/3373718.3394747
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
R. Alur;Yu Chen;Kishor Jothimurugan;S. Khanna
中科院分区：
文献类型：
--
作者：
R. Alur;Yu Chen;Kishor Jothimurugan;S. Khanna
物联网应用中的实时决策依赖于对流数据的查询进行节省空间的评估。为了对数据分类中的不确定性进行建模，我们考虑了概率串的模型-有限事件集上的离散概率分布序列，并启动了对这种概率串上不同类别查询的流计算的空间复杂性的研究。我们首先考虑计算从到目前为止读取的概率字符串定义的分布中采样的单词被给定的确定性有限自动机接受的概率的问题。我们证明，如果允许乘性逼近误差，则可以使用字符串长度仅为多对数(以及DFA大小的多项式)的空间来解决这个正则模式匹配问题。然后，我们展示如何将这一结果推广到由加性成本寄存器自动机指定的定量查询-这些自动机使用有限控制将字符串映射到数值，并使用线性变换更新寄存器。最后，我们考虑这样的自动机中的更新涉及测试的情况，特别是当存在可以递增或递减但递减仅当计数器值非零时才适用的计数器变量的情况。在这种情况下，期望的答案取决于可能的计数器值集合上的概率分布，对于长度为n的字符串，可能的计数器值的范围从0到n。在一个温和的假设下，即单个事件的概率从0到1有界，我们证明了有一个算法可以计算该概率分布向量的所有n个条目，并且使用仅为？(N)的空间来计算该概率分布向量的所有n个条目的加性1/多(N)误差。在建立这些结果的过程中，我们引入了几个新的技术想法，这些想法可能对设计其他概率字符串上的查询模型的空间高效算法有用。
Real-time decision making in IoT applications relies upon space-efficient evaluation of queries over streaming data. To model the uncertainty in the classification of data being processed, we consider the model of probabilistic strings --- sequences of discrete probability distributions over a finite set of events, and initiate the study of space complexity of streaming computation for different classes of queries over such probabilistic strings. We first consider the problem of computing the probability that a word, sampled from the distribution defined by the probabilistic string read so far, is accepted by a given deterministic finite automaton. We show that this regular pattern matching problem can be solved using space that is only poly-logarithmic in the string length (and polynomial in the size of the DFA) if we are allowed a multiplicative approximation error. Then we show how to generalize this result to quantitative queries specified by additive cost register automata --- these are automata that map strings to numerical values using finite control and registers that get updated using linear transformations. Finally, we consider the case when updates in such an automaton involve tests, and in particular, when there is a counter variable that can be either incremented or decremented but decrements only apply when the counter value is non-zero. In this case, the desired answer depends on the probability distribution over the set of possible counter values that can range from 0 to n for a string of length n. Under a mild assumption, namely probabilities of the individual events are bounded away from 0 and 1, we show that there is an algorithm that can compute all n entries of this probability distribution vector to within additive 1/poly(n) error using space that is only Õ(n). In establishing these results, we introduce several new technical ideas that may prove useful for designing space-efficient algorithms for other query models over probabilistic strings.