DM-数据挖掘小白-研究生入门自述
数据挖掘小白-研究生入门学习
Graph Sketching（一）
我是一名正在数据挖掘领域深造的学生，在过去一段时间里，在导师的帮助下，在数据挖掘领域的研究方向上进行了初步探索。我的主要核心工作是阅读graph sketching方向上的相关论文，并以此为基础展开学习。通过梳理和总结这些研究资料的过程，打算将这一阶段内所有涉及graph sketching的研究成果进行系统梳理，并在此平台进行分享。期待能与志同道合的研究新生们共同进步。
Query-Friendly Compression_Graph_Streams
**研究背景和目的**
该论文是基于由大量的通讯、网络社交、购物等产生大量的即时数据而形成的图流，为了对这些即时数据进行某些需求(场景)的查询。设计了一种图流的压缩结构，能够对现有的结构进行改进，提供更友好的信息查询，也就是提供更多的查询功能[^主要增加了一些结构化的查询，即涉及到底层的点(假设一条信息流为一条边)集合的查询]。
2.**现存图流压缩--COUNT-MIN**
之前很多的图压缩都支持对__high-frequency__的node或者edge的查询，但是不支持进行结构化的查询。比较经典的是**COUNT-MIN**。这个方法的主要思路是，构造一个w*h大小二维数组，利用w[^ w由特定公式算出，此处略，见原文]个两两相互独立的哈希函数g~k~ 。每个哈希函数对应一个一维的数组空间。
![在这里插入图片描述]()
1. 更新操作
当一条信息流edge过来时，对这个信息流用w个哈希分别计算，算出它在每个哈希函数对应的一维数组中的对应位置，该相应位置的单元的frequency+1。
2.查询操作
求信息流edge的相应frequency，首先分别用w个哈希函数对这个信息流进行哈希，求出w个相应的位置，对这w个位置的frequency进行比较，选择最小的那个作为该信息流frequency的估计值。原因是由于每个信息流流过时，哈希函数对应的相应位置的操作是非负的，并且由于进行了图压缩，会产生哈希碰撞，不同的edge可能会哈希到同一个位置。因此最小的count-min是不小于真实的frequency的。原文后面推算了一个置信区间的概率，略过。论文的新方法-gMatrix
1.更新操作
对每个信息流edge(i,j)，分别对它的两个顶点进行哈希，来确定它在每个哈希函数对应空间中的位置。然后将这w个相应的位置的frequency+fij[^这个是信息流本次带的frequency]。
2.边的frequency查询
类似于COUNT-MIN
3.frequency >= F的边查询
1. 扫描gMatrix中所有的位置，找出frequency>=F的所有位置。
2.对每个哈希所对应的空间中被选出的位置，分别进行哈希函数的求逆运算，算出符合该位置(p,q,k)的点集（Q1,Q2），推出符合该位置的边集：S（Q1,Q2）。
3.对w个哈希函数的所算出的点集合进行两两求∩运算。即分别从两个个哈希空间的被选出的位置中，选出一个。用其所对应的点集合(Q1,Q2), (P1,P2)。来进行顶点求∩运算。如(Q1∩P1，Q2∩P2)得到新的点集合(U1,U2)。这就能推出同时符号这个两个哈希函数的边集合S（U1,U2）。依此类推，算出符号这w个哈希函数的边集合S，问题得解。
4.可达性查询
通过方法3求出frequency>F的边edge(i,j)。由于求出了其顶点i,j，因此可以基于这高频的边集合(人为设置F的值使其较大，则求出的边集较小，能够满足性能要求)，进行某个起点到终点的可达性查询。
该论文说能支持六种查询，有几种没有介绍，好像被略过
了？？？
[参考文献：Query-Friendly Compression of Graph Streams ，Arijit Khan]