Page 382 - 《软件学报》2025年第9期

王尚 等: 基于神经网络的分布式追踪数据压缩和查询方法 4293

算法 1. 嵌入过程.
输入: 追踪图的根节点列表 roots, 窗口长度 N;
输出: 追踪图的向量表示 embeddings.

1. function get_embeddings(roots, N)
2. embeddings ← [], paths ← []
3. for each root in roots
4. paths ← get_paths(root, N) ∪ paths //获取所有结构的路径列表
5. vocab ← set(paths) // 将路径的集合作为词汇表
6. for each path in paths
7. counter ← Counter(path), embedding ← [] // 初始化每个结构的路径计数器和向量表示
8. for each word in vocab
9. embedding ← counter.get(word) ∪ embedding //每个维度取值为路径数量
10. embeddings ← embedding ∪ embeddings //将该结构的向量表示加入结果列表
11. return embeddings
12. function get_paths(root, N)
13. all_paths ← [], path ← stack()
14. function dfs(node, depth)
15. path.push(node)
16. if depth ≥ N
17. all_paths ← path[–N:] ∪ all_paths //取末尾 N 个节点的序列作为尾节点的调用路径
18. if depth < N and node is leaf
19. all_paths ← path ∪ all_paths //叶子节点若路径长度不足 N, 则将整个序列作为其调用路径
20. for each child in node.children
21. dfs(child, depth + 1)
22. path.pop()
23. dfs(root, 1) //从树的根节点开始向下搜索
24. return all_paths

0
尾节点 3-gram
2 0 2
1 2 3 4 0 1 4
5 0 1 5 向
量
4 5 6 6 0 3 6
7 1 5 7
7

图 6 图嵌入

在聚类算法上, NCQT 使用 K-means 算法聚类所有种类的调用图. 对调用图聚类旨在为后续分组提供依据, 进
一步提高压缩的效果和查询的效率. 由于聚类主要是为后续的分组压缩和搜索提供辅助支持, 即使聚类效果欠佳,
方法依然能够实现对追踪数据的无损压缩, 但复杂的聚类算法会带来更多的压缩时间开销. 为了平衡聚类速度和
聚类效果, 我们选择线性时间复杂度的聚类算法 K-means. K-means 算法 [47] 是一种广泛使用的聚类方法, 可以快速