面向幂律图的动态图存储结构Power-PCSR

图数据在现实生活中广泛存在,且不断发生变化。传统高效的静态图存储方式——压缩行/列(Compressed Sparse Row/Column,CSR/CSR)存储方式在更新图数据时需要大量的数据迁移,不适用于动态图数据。而能够高效更新图数据的邻接表(Adjacency List,AL)存储方式往往带有大量的指针,导致其图数据读取和分析效率低。Packed Compressed Sparse Row(PCSR)是一种基于CSR的动态图存储结构。该结构在存储边数据时并不是采用连续无空隙数组,而是采用留有空槽的压缩存储阵列(Packed Memory Arrays,PMA)结构,便于边数据的插入。因此,PCSR支持高效图更新和图分析。但是,PCSR在存储幂律图时,其性能容易受大度数顶点的影响。为此,基于PCSR提出一种支持可高效更新和分析动态幂律图的图存储结构Power-PCSR。该结构将幂律图中度数较大的顶点单独存储在一个独立的PMA中,其他所有小度数顶点与PCSR一样存储在原PMA中。小度顶点变化导致的数据迁移不会触及大度数顶点,从而大大减少了数据迁移数量;同样,大度数顶点更新导致的数据迁移只限制在每个大度数顶点的PMA内部,不会涉及小度数顶点和其他大度数顶点的数据迁移。实验显示,Power-PCSR在分析图数据时与PCSR具有相似的性能,而在更新图数据时比PCSR快2倍。

EDDPC:一种高效的分布式密度中心聚类算法

聚类分析是数据挖掘中经常用到的一种分析数据之间关系的方法.它把数据对象集合划分成多个不同的组或簇,每个簇内的数据对象之间的相似性要高于与其他簇内的对象的相似性.密度中心聚类算法是一个最近发表在《Science》上的新型聚类算法,它通过评估每个数据对象的2个属性值(密度值ρ和斥群值δ)来进行聚类.相对于其他传统聚类算法,它的优越性体现在交互性、无迭代性、无数据分布依赖性等方面.但是密度中心聚类算法在计算每个数据对象的密度值和斥群值时,需要O(N^2)复杂度的距离计算,当处理海量高维数据时,该算法的效率会受到很大的影响.为了提高该算法的效率和扩展性,提出一种高效的分布式密度中心聚类算法EDDPC(efficient distributed density peaks clustering),它利用Voronoi分割与合理的数据复制及过滤,避免了大量无用的距离计算开销和数据传输开销.实验结果显示:与简单的MapReduce分布式实现比较,EDDPC可以达到40倍左右的性能提升.

地理社交网络中基于K近邻的兴趣组查询

为满足地理社交网络平台中用户对附近区域内具有相同兴趣的其他用户的查找需求,提出一种新型空间查询——基于K近邻的兴趣组查询(K-Nearest Neighbor Based Interest Group Query,KNNIG)。与基于距离约束的传统空间K近邻查询不同,KNNIG查询还加入了基于查询关键字的兴趣值约束,并在此基础上提出了D-I评价函数。查询结果为分值最高的用户集合。此外,提出了3种查询处理算法:基本KNNIG查询处理算法(KNNIG-G)、KNNIG查询的优化算法(KNNIG-G*)以及基于网格的距离松弛算法(KNNIG-DR)。在KNNIG-G基础上,KNNIG-G*和KNNIG-DR分别通过空间剪枝和距离松弛策略,在可容忍误差范围内有效地减少了计算开销,提高了查询效率。在真实数据集上进行的实验验证了所提算法的可行性与有效性。

流式处理的异步图处理框架

分布式图计算是目前处理大图数据的主流技术,但是存在诸多无法避免的问题,比如分布式计算的负载均衡和分布式实现的调试和优化仍然非常困难.另一方面,近几年的研究结果表明:通过设计合理的数据结构和处理模型,在单个PC上基于大容量磁盘的大图计算往往可以获得与分布式图计算相当的处理性能.例如,Graph Chi在单机上的处理性能与Spark在50台节点上的处理性能相差无几.结合累加迭代计算和单机并行处理技术,提出流式处理的异步计算模型ASP.它实现了对磁盘的完全顺序访问,允许流式的顺序载入结构数据的同时进行异步更新计算.基于ASP模型,提出了一种流式处理的异步图处理框架S-Maiter,实现了高效率的基于外存的单机大图处理,通过I/O线程优化、内存资源监控、shard级优先级调度等优化技术,提高了系统处理大图数据的性能.实验结果表明:在处理大图数据(1 300万顶点,5亿连边)时,仅仅需要1台PC机计算资源的S-Maiter与在16台PC上运行的分布式Maiter的性能几乎相当.并且,S-Maiter比另外一个流行的单机大图处理系统Graph Chi要快1.5倍.