Gulico

  • 首页

  • 标签

  • 分类

  • 归档

  • 留言

  • 搜索

近似最近邻算法SSG学习笔记(二)伪码注释

发表于 2019-08-14 更新于 2019-10-25 分类于 算法 阅读次数: Valine:

以下为出现在文章《Satellite System Graph: Towards the Efficiency Up-Boundary of Graph-Based Approximate Nearest Neighbor Search(卫星系图:接近基于图的近似最近邻搜索效率的上界)》中的两个算法,下面做简单注释。

算法1:贪婪搜索Search-on-Graph(G, p, q, l)

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
/**
* 功能:在图G上从起始点p开始搜索,得到k个距离查询点q最近的点
* 参数:图G
* 起始点p
* 查询点q
* 候选池大小l
* 返回:k个距离查询点q最近的点
**/

Require: graph G, start node p, query point q, candidate pool size l
Ensure: k nearest neighbors of q

i = 0, candidate pool S = ∅ //最初候选池S为空,候选池中元素索引序号i = 0
S.add(p) //起始点加入候选池S

while i < l do //当候选池中点的索引序号i小于l
i = the index of the first unchecked node in S //i = 候选池中首个未查询的点的索引序号
mark pi as checked //标记pi为查询过的点

for all neighbor n of pi in G do //将pi的所有邻居加入候选池
S.add(n)
end for
sort S in ascending order of the distance to q //将候选池中的点,以与q点的距离为依据升序排列

If S.size() > l, S.resize(l) //若S的大小大于l,则更新S的大小
end while
return the first k nodes in S

算法2:建立SSG图索引SSGIndexing(D, l, r, s, α)

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
/**
* 算法2:SSGIndexing(D, l, r, s, α)
* 功能:建立SSG索引
* 传入参数:数据集D,
* 候选集大小L
* 最大度r
* 导航点的数量s
* 边之间的最小角度α
* 返回:SSG图G
**/

Require: dataset D, candidate set size l, maximum outdegree r, number of navigating points s, minimum angle α.

Ensure: an SSG G.

/**
* 1.建立近似kNN图:GkNN
**/

Build an approximate kNN graph Gknn.
G = ∅.


for all node i in Gknn do //遍历Gknn图中的所有点i
P = ∅. //候选集P为空

/**
* 2.候选集P从对应点的邻居和邻居的邻居中产生
**/
for all neighbor n of node i do //遍历i的所有邻居n,加入候选集P
P.add(n).
for all neighbor n0 of node n do //遍历n的所有邻居n0,加入候选集P
P.add(n0).
end for
remove the redundant nodes in P. //移除P中多余的边
if P.size() ≥ l then //若P的大小大于l,则跳出循环
break.
end if
end for

/**
* 3.从候选集P中挑选符合SSG的i的邻居
**/
sort P in the ascending order of the distance to i. //对候选集中的点,按照与i的距离升序排序。

select neighbors from P according to the definition of SSG. //根据SSG选编策略,从P中选择i的邻居
end for

/**
* 4.加强图的连通性
**/

Random select s points from the datasets as N. //随机选择s个导航点N
for all point n in N do //遍历导航点
Strengthen the connectivity of the graph with
DFS-expanding from s. //利用深度优先扩展算法,加强图的连通性
end for 23: return G.
# 搜索
近似最近邻算法SSG学习笔记(一)介绍
集束搜索(Beam Search Algorithm)
  • 文章目录
  • 站点概览
Gulico

Gulico

I`ll spend forever wondering if you knew
19 日志
7 分类
9 标签
GitHub E-Mail Weibo
  1. 1. 算法1:贪婪搜索Search-on-Graph(G, p, q, l)
  2. 2. 算法2:建立SSG图索引SSGIndexing(D, l, r, s, α)
© 2020 Gulico
由 Hexo 强力驱动 v3.9.0
|
主题 – NexT.Mist v7.3.0