Puitar's Blog
0%

黑标签统计安排

Posted on Edited on In

黑标签统计

实验安排（更新）

基于内存版本

基于内存版本的黑标签统计，在这里不做过多介绍。项目地址

[基于内存黑标签统计]: https://github.com/PUITAR/BlackLabelCount

1
git clone git@github.com:PUITAR/BlackLabelCount.git

基于磁盘版本

由于后续实验需要一个基准baseline，因此这里使用RocksDB作为基准工作的基础。

1_0版本概述

版本设计思路分为两个模块：

  • 小世界模型图生成
  • 小世界模型图的读取和计算

小世界网络生成

[matlab生成小世界网络思路]: https://ww2.mathworks.cn/help/matlab/math/build-watts-strogatz-small-world-graph-model.html

生成的算法如附录B，实验先用已有数据集。

和前面内存版本一样，只是获取一阶好友的方式由从内存取到从磁盘取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @description: 通过点的id从数据库获取一阶好友
 * @param <str_t> k 传入点id作为键
 * @param <DB*> db 传入数据库指针
 * @return <*> 返回一阶好友的数组
 */
vec_t GetFriends1Vec(str_t k, DB* db) {
    str_t v;
    vec_t vec;
    db->Get(ReadOptions(), k, &v);
    stringstream ss(v);
    while (ss >> v)
        vec.push_back(v);
    return vec;
}

由于在数据库中以字节流的形式（字符串）存储，所以需要用stringstream读出每一个一阶好友。

2_0统计结果

该版本是多线程版本，工程文件树和代码放在附录A中，其中计算时间和IO时间单位都是时钟周期数

wiki-topcats

下图是wiki数据集在黑点比例为0.005的情况下，计算总时间和IO所用的时间，其中纵轴单位是时钟周期

[可视化链接]: https://puitar.github.io/echarts/wiki_chart1

下图是wiki数据集在黑点比例为0.005的情况下，IO所用时间占总体计算时间的占比的折线图，纵轴单位是“1”

[可视化链接]: https://puitar.github.io/echarts/wiki_chart2

就wiki的数据集来看，当线程数量较大的时候的计算时间很长，而且IO占总时间的比例很大（大于30%）。但是，随着现成的数量减少，计算时间和IO占比都下降。可以推测，限制计算的瓶颈是磁盘的IO，而磁盘的IO瓶颈在图计算的随机读过程中充分体现，这种现象会随着线程数目的增加而加剧。

twitter-2010

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/twitter_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/twitter_chart2

arabic-2005

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/arabic_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/arabic_chart2

enwiki-2021

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/enwiki_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/enwiki_chart2

论文阅读

HyperANF

文献名称：HyperANF_ Approximating the Neighbourhood Function of Very Large Graphs on a Budget

HyperLogLog（HLL）

参考：HyperLogLog · 语雀 (yuque.com)

Triangle Enumeration

Improving I/O Complexity of Triangle Enumeration

ICDE2023-VEND-524(RevisionOf-37)-C

先看这篇文章Introduction部分Algorithm 2 Trigon的原理，有助于理解

优化版本

伪代码

  • 需要两种边集文件

    • Partition文件：对边以目的点进行排序（分interval）
    • Edges：对边以源点进行排序（不分interval）

  • 对于边集E的某个子集Esub的两种操作：

    • Esub.first：表示边集的源点集合
    • Esub.second：表示边集的目的点集合

  • 一个映射函数：

    FindTwoHopRange(S[i], P[i])：找到P[i]中起点在S[i]中的边的中点集合

  • 函数Union(1, p, R)的含义是

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 求点v的二阶范围内所有点，带去重效果 */
function FindTwoHopNeighbors(v) {
	Nv ← Edges[v].second;						// 从Edges文件种读取以v为源点的边集的目的点集合
    for each partition P[i] in PartitionFile {
        S[i] = Nv ∩ P[i].first;					// 找到2阶在400-500范围内的一阶好友
        R[i] = FindTwoHopRange(S[i], P[i]); 	// R[i]是v的在400-500范围内的二阶好友
    }
    Fv = {v} ∪ Nv ∪ Union(1, p, R) 		   	   // 二阶范围所有点为v、一阶好友、二阶好友
    return Fv;
}

/* 统计二阶标签过程 */
compute(v, Fv, lables);

由于上一阶段的统计发现IO占时间为70%到80%，因此FindTwoHopNeighbors可能对IO存在优化，使得整体有优化效果。

附录

附录A

附录A是黑标签统计基于磁盘版本的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
/*
 * @author: puitar
 * @Description: 版本2.0
 * @Date: 2022-07-30 15:15:11
 * @LastEditTime: 2022-07-30 23:48:14
 * @FilePath: /rocksdb/bkc/2_0.cc
 */

#include <iostream>
#include <assert.h>
#include <fstream>
#include <unordered_map>
#include <string>
#include <vector>
#include <sstream>
#include <thread>
#include <stdlib.h>
#include <time.h>

#include "rocksdb/db.h"
#include "rocksdb/slice.h"
#include "rocksdb/options.h"
#define MAX_MUT_NUM 80


using namespace std;
using ROCKSDB_NAMESPACE::DB;
using ROCKSDB_NAMESPACE::Options;
using ROCKSDB_NAMESPACE::ReadOptions;
using ROCKSDB_NAMESPACE::Status;
using ROCKSDB_NAMESPACE::WriteBatch;
using ROCKSDB_NAMESPACE::WriteOptions;

typedef int ReturnType;
typedef string str_t;
typedef vector<str_t> vec_str_t;
typedef vector<int> vec_int_t;

const char kDBPath[] = "db/data2/";
str_t gTxtPath = "2.txt";

enum ReturValue {
    SUCCESS,
    FAILED,
};

/* 计算全局变量 */
DB* db = nullptr;
vec_int_t result;
vec_str_t visited;
mutex mutexs[MAX_MUT_NUM];
vec_str_t blacks;
int threads = 0;
int bkn = 0;
double io_time = 0;


/**
 * @description: 从txt中读取将图以键值对形式存入数据库，其中键是点id，值是邻接表
 * @param <str_t> gTxtPath txt路径
 * @param <DB*> db 数据库指针
 * @return <*> 若成功返回SUCCESS, 否则返回FAILED
 */
ReturnType Generation(str_t gTxtPath)
{
    Status s;
    ReturnType r = FAILED;
    ifstream fin(gTxtPath);
    str_t k, v;
    unordered_map<str_t, str_t> g;
    while (fin >> k >> v) {
        g[k] += v + " ";
        g[v] += k + " ";
    }
    int n = g.size();
    for (int u = 0; u < n; u++) {
        str_t v = to_string(u);
        s = db->Put(WriteOptions(), v, g[v]);
        if (!s.ok()) return r;
    }
    r = SUCCESS;
    return r;
}


/**
 * @description: Get函数的封装，可以对IO时间进行累加
 * @param <str_t> k 键
 * @param <str_t> &v 值
 * @param <DB*> db 传入数据库指针
 * @return <*>
 */
void MyGet(str_t k, str_t &v) {
    clock_t start_time = clock();
    db->Get(ReadOptions(), k, &v);
    io_time += (double)(clock()-start_time);
}

/**
 * @description: 通过点的id从数据库获取一阶好友
 * @param <str_t> k 传入点id作为键
 * @param <DB*> db 传入数据库指针
 * @return <*> 返回一节好友的数组
 */
vec_str_t GetFriends1Vec(str_t k)
{
    str_t v;
    vec_str_t vec;
    MyGet(k, v);
    stringstream ss(v);
    while (ss >> v)
        vec.push_back(v);
    return vec;
}


/**
 * @description: 线程计算函数
 * @param <int> start 线程的初始黑点
 * @return <*>
 */
void Computation(int start)
{
    for (int u = start; u < bkn; u += threads)
    {
        str_t v = blacks[u];
        vec_str_t friends1 = GetFriends1Vec(v);
        for (auto f1: friends1) {
            int f1_;
            stringstream ss1(f1);
            ss1 >> f1_;
            mutexs[f1_%MAX_MUT_NUM].lock();
            if (visited[f1_] != v) {
                result[f1_]++;
                visited[f1_] = v;
            }
            mutexs[f1_%MAX_MUT_NUM].unlock();
            vec_str_t friends2 = GetFriends1Vec(f1);
            for (auto f2: friends2) {
                int f2_;
                stringstream ss2(f2);
                ss2 >> f2_;
                mutexs[f2_%MAX_MUT_NUM].lock();
                if (visited[f2_] != v) {
                    result[f2_]++;
                    visited[f2_] = v;
                }
                mutexs[f2_%MAX_MUT_NUM].unlock();
            }
        }
    }
}



int main(int argc, char* argv[])
{
    /* 一些必要的声明 */
    Options options;
    Status s;
    options.IncreaseParallelism();
    options.OptimizeLevelStyleCompaction();
    options.create_if_missing = true;
    int rm = 0;   

    // 参数列表有参数则生成图，否则直接计算
    assert(argc == 2);
    gTxtPath = argv[1];   

    assert(DB::Open(options, kDBPath, &db).ok());

/* 产生图 */
generation: 
    cout << "generation start!" << endl;
    assert(Generation(gTxtPath) == SUCCESS);
    cout << "generation finish!" << endl;


/* 计算黑标签过程 */
computation: 
    /* 获取数据库中键值对的数量 */
    uint64_t n;
    db->GetIntProperty("rocksdb.estimate-num-keys", &n);
    cout << "vertex numbers: " << n << endl;
    
    /* 黑标签生成 */
    float p = 0;
    while (p<=0 || p>=1) {
        cout << "black ratio: "; 
        cin >> p;
        cout << p << endl;
    }
    bkn = n*p;
    for (int i = 0; i < bkn; i++) {
        blacks.push_back(to_string(rand()%n));
    }  
    // cout << "blacks:\n";
    // for (auto b: blacks)
    //     cout << b << endl;
    bkn = blacks.size();
    cout << "black numbers: " << bkn << endl;
    
    /* 开始计算 */
    result.resize(n);
    visited.resize(n);

    while (threads <= 0 || threads > MAX_MUT_NUM) {
        cout << "threads: ";
        cin >> threads;
        cout << threads << endl;
    }

    thread pool[threads];
    double total_time;

    clock_t start_time = clock();
    for (int start = 0; start < threads; start++)
    {
        pool[start] = thread(Computation, start);
    }
    for (int start = 0; start < threads; start++)
    {
        pool[start].join();
    }
    total_time = (double)(clock()-start_time);

    /* 输出结果 */
    // cout << "result:" << endl;
    // for (int v = 0; v < n; v++) {
    //     cout << v << ": " << result[v] << endl; 
    // }

    printf("Coputation Time: %.0f CLKs\n", total_time);
    printf("I/O Time: %.0f CLKs\n", io_time);
    rm = system("make rm2");
    cout << "Work Finished!\n\n\n\n" << endl;

    delete db;
    return 0;
}

工程文件树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bash-4.2$ tree
.
├── 1_0
├── 1_0.cc
├── 2_0
├── 2_0.cc
├── data		# 用于导入图的txt文件
│   ├── arabic-2005.txt
│   ├── comfriends.txt
│   ├── twitter-2010.txt
│   └── wiki-topcats.txt
├── db			# 数据库，包含不同版本存储图的数据
│   ├── data1
│   └── data2
├── input 		# 输入文件输入各种配置，设置黑标签占比以及运行线程数
│   ├── input_0.00001_1
│   ├── input_0.00001_10
│   ├── input_0.00001_20
│   ├── input_0.00001_40
│   ├── input_0.005_1
│   ├── input_0.005_10
│   ├── input_0.005_20
│   └── input_0.005_40
└── Makefile	# makefile

5 directories, 17 files

附录B

如果需要自己生成小世界网络，则使用该伪代码的算法生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* `Watts-Strogatz`小世界网络生成算法伪码 */
Function SmallWorldNetwork(n, k, p)
Output: 小世界网络图
Require: k是偶数且p∈[0, 1]
begin
	procedure 参数初始化
    	n: 网络节点总数;
        k: 每个节点的边连接数;
        p: 每条边发生重连的概率;
	end
    procedure 初始边连接
    	for 网络中的每一个结点v do
    		将其与所有距离小于等于k/2的其他结点相连; // 要求k为偶数
    	end
    end
    procedure 已有边重连
    	for 网络中的每一条边e do
    		以概率p重连此边; // 要求不能有自环或者重复边
    	end
    end
end