百富勤：模式感知图挖掘系统

Peregrine是一种高效的单机系统，用于在大型图形上执行数据挖掘任务。一些图挖掘应用程序包括：

Peregrine是高度可编程的，因此您可以使用其新颖的，声明性的，以图形模式为中心的API轻松开发自己的图形挖掘应用程序。要编写Peregrine程序，请描述您对挖掘感兴趣的图形模式以及如何处理这些模式的每次出现。您提供内容，运行时处理方式。

有关完整的详细信息，您可以阅读我们发表在EuroSys 2020或arXiv上较长版本的论文。

Peregrine已在Ubuntu 18.04和Arch Linux上进行了测试，但应可在任何POSIX-y OS上使用。它需要C ++ 20支持（GCC版本> = 9.2.1）。此外，测试需要UnitTest ++。

随代码一起发布了几个示例应用程序，查询模式和示例数据集。调用不带参数的任何应用程序将向您显示他们的期望：

$ bin / count data / citeseer 3-motifs 8Counting 3-motifs完成的读取数据图：| V | = 3264 | E | = 4536 [...]所有图案在0.030265s [2-3] [1-3]之后完成：23380 [1-2] [1-3] [2-3]：1166

字符串[2-3] [1-3]编码由边（1、3），（2、3）组成的模式，而23380是在引子图中发现的百富勤的唯一出现次数。

$ bin / count data / citeseer 4-clique 8 [...]所有模式在0.030265s [3-4] [1-2] [1-3] [1-4] [2-3] [2- 4]：255 $$ bin / count数据/ citeseer查询/ p1。图8 [...]所有模式在0.003368s [3-4] [1-2] [1-3] [1-4] [ 2-3]：3730

$ bin / fsm data / citeseer 3 300 8＃size 3 FSM，支持300 [...]常见模式：[1,0-2,0] [1,0-3,0] [2,0-4， 0]：303 [1,1-2,1] [1,1-3,1] [2,1-4,1]：335完成于0.078629s

$ bin / existence-query data / citeseer 14-clique 8 [...] 0.005509s之后完成的所有模式[由于长度而省略了模式]在data / citeseer中不存在

在Peregrine的编程模型中，您将提供一个数据图，一组您感兴趣的模式以及一个回调，系统将对数据图中这些模式的每次出现应用回调。我们从构建模式开始对API进行简要概述。

我们尚未发布对有向图的支持。该代码当前假定所有图形都是无向的。

标签是可选的32位整数。要指示顶点未标记为部分标记的模式，请为其分配标记-1。为了表示反边缘，可以在行尾放置任何其他整数。

int size = 4; std :: vector vertex_ductive = PatternGenerator :: all（size，PatternGenerator :: VERTEX_BASED，// 4个顶点PatternGenerator :: INCLUDE_ANTI_EDGES）; //在所有不相邻的顶点之间插入反边//在所有不相邻的顶点之间插入反边//没有插入额外的反边缘//没有插入多余的边缘

可以从预处理的边列表（请参见数据图）或SmallGraph构造数据图。

使用命名空间Peregrine #include“ Peregrine.hh”;无效主题（int size）{int nthreads = 16; DataGraph g（“ data / citeseer /”）;自动模式= PatternGenerator :: all（大小，PatternGenerator :: VERTEX_BASED，PatternGenerator :: INCLUDE_ANTI_EDGES）;自动结果=计数（g，模式，nthreads）; for（const auto＆[pattern，count]：结果）{std :: cout （g，模式，nthreads，回调）;

除回调外，常规参数与计数示例相同。这个函数将在每次匹配模式时被调用，它带有两个参数：Peregrine的聚合器的句柄和匹配本身。

在这里，回调将匹配的模式映射到1。请注意，此阵容具有传递给match的类型：聚合键是Pattern，值是整数。 Peregrine自动处理诸如uint64_t之类的简单类型，并使用内置的sum运算符将它们聚合。

使用更复杂的聚合值要求它们实现一些方法并实现视图功能。 FSM示例应用程序就是一个很好的例子：同时检查apps / fsm.cc和apps / Domain.hh来查看视图功能和聚合值方法。

Peregrine的数据处理器提取图边缘列表并将其存储为二进制邻接列表格式。对于标记的数据图，使用单独的顶点-标签对文件。顶点ID和标签都应为无符号的32位整数。

衷心感谢您决定在此项目上花费宝贵的时间！PR很受欢迎，只要不影响性能或损害正确性，我们会仔细考虑。

@inproceedings {10.1145 / 3342195.3387548，作者= {Jamshidi，Kasra和Mahadasa，Rakesh和Vora，Keval}，标题= {Peregrine：一种模式感知图挖掘系统}，年份= {2020}，isbn = {9781450368827}，出版商= {计算机技术协会}，地址= {美国纽约州纽约}，网址= {https://doi.org/10.1145/3342195.3387548}，doi = {10.1145 / 3342195.3387548}，书名= {第十五届会议论文集欧洲计算机系统大会}，文章编号= {第13条}，页数= {16}，位置= {希腊伊拉克利翁}，系列= {EuroSys '20}}