论文标题
在流图上的常规路径查询评估
Regular Path Query Evaluation on Streaming Graphs
论文作者
论文摘要
我们研究了对流图的持续查询评估，这变得越来越重要。我们专注于确定满足用户指定约束的两个实体之间是否存在路径。我们采用常规路径查询（RPQ）模型，该模型指定具有标记约束的导航模式。我们提出确定性算法，以统一的方式在任意和简单的路径语义下有效评估持久性RPQ。对真实和合成流图的实验分析表明，所提出的算法每秒可以处理多达数万个边缘，并有效地回答现实世界中通常使用的RPQ。
We study persistent query evaluation over streaming graphs, which is becoming increasingly important. We focus on navigational queries that determine if there exists a path between two entities that satisfies a user-specified constraint. We adopt the Regular Path Query (RPQ) model that specifies navigational patterns with labeled constraints. We propose deterministic algorithms to efficiently evaluate persistent RPQs under both arbitrary and simple path semantics in a uniform manner. Experimental analysis on real and synthetic streaming graphs shows that the proposed algorithms can process up to tens of thousands of edges per second and efficiently answer RPQs that are commonly used in real-world workloads.
