论文标题
优化在动态图上优化差异维护的递归查询
Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs
论文作者
论文摘要
差分计算（DC）是一种高度通用的增量计算/视图维护技术，可以在更改其基本输入的情况下维护任意和可能的递归数据流计算的输出。因此，这是图形数据库管理系统（GDBMS）的一种有希望的技术，该技术支持在动态图上支持连续的递归查询。尽管差分计算可以高效地维持这些查询，但它可能需要大量的内存。本文研究了如何减少DC的内存开销，目的是提高采用系统的可扩展性。我们提出了一套优化的套件，这些优化是基于完全或部分或部分地放弃操作员的差异，并在必要时重新计算这些差异。我们提出确定性和概率数据结构，以跟踪掉落的差异。广泛的实验表明，优化可以提高基于直流的连续查询处理器的可扩展性。
Differential computation (DC) is a highly general incremental computation/view maintenance technique that can maintain the output of an arbitrary and possibly recursive dataflow computation upon changes to its base inputs. As such, it is a promising technique for graph database management systems (GDBMS) that support continuous recursive queries over dynamic graphs. Although differential computation can be highly efficient for maintaining these queries, it can require a prohibitively large amount of memory. This paper studies how to reduce the memory overhead of DC with the goal of increasing the scalability of systems that adopt it. We propose a suite of optimizations that are based on dropping the differences of operators, both completely or partially, and recomputing these differences when necessary. We propose deterministic and probabilistic data structures to keep track of the dropped differences. Extensive experiments demonstrate that the optimizations can improve the scalability of a DC-based continuous query processor.
