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
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.5"/>
<title>Faiss: /data/users/matthijs/github_faiss/faiss/IndexHNSW.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">Faiss
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
</ul>
</div>
</div><!-- top -->
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark"> </span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark"> </span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark"> </span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark"> </span>Friends</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div class="header">
<div class="headertitle">
<div class="title">/data/users/matthijs/github_faiss/faiss/IndexHNSW.h</div> </div>
</div><!--header-->
<div class="contents">
<div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno"> 1</span> <span class="comment">/**</span></div>
<div class="line"><a name="l00002"></a><span class="lineno"> 2</span> <span class="comment"> * Copyright (c) 2015-present, Facebook, Inc.</span></div>
<div class="line"><a name="l00003"></a><span class="lineno"> 3</span> <span class="comment"> * All rights reserved.</span></div>
<div class="line"><a name="l00004"></a><span class="lineno"> 4</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00005"></a><span class="lineno"> 5</span> <span class="comment"> * This source code is licensed under the BSD+Patents license found in the</span></div>
<div class="line"><a name="l00006"></a><span class="lineno"> 6</span> <span class="comment"> * LICENSE file in the root directory of this source tree.</span></div>
<div class="line"><a name="l00007"></a><span class="lineno"> 7</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00008"></a><span class="lineno"> 8</span> </div>
<div class="line"><a name="l00009"></a><span class="lineno"> 9</span> <span class="preprocessor">#pragma once</span></div>
<div class="line"><a name="l00010"></a><span class="lineno"> 10</span> <span class="preprocessor"></span></div>
<div class="line"><a name="l00011"></a><span class="lineno"> 11</span> <span class="preprocessor">#include <vector></span></div>
<div class="line"><a name="l00012"></a><span class="lineno"> 12</span> <span class="preprocessor">#include <omp.h></span></div>
<div class="line"><a name="l00013"></a><span class="lineno"> 13</span> </div>
<div class="line"><a name="l00014"></a><span class="lineno"> 14</span> <span class="preprocessor">#include "IndexFlat.h"</span></div>
<div class="line"><a name="l00015"></a><span class="lineno"> 15</span> <span class="preprocessor">#include "IndexPQ.h"</span></div>
<div class="line"><a name="l00016"></a><span class="lineno"> 16</span> <span class="preprocessor">#include "IndexScalarQuantizer.h"</span></div>
<div class="line"><a name="l00017"></a><span class="lineno"> 17</span> <span class="preprocessor">#include "utils.h"</span></div>
<div class="line"><a name="l00018"></a><span class="lineno"> 18</span> </div>
<div class="line"><a name="l00019"></a><span class="lineno"> 19</span> </div>
<div class="line"><a name="l00020"></a><span class="lineno"> 20</span> <span class="keyword">namespace </span>faiss {</div>
<div class="line"><a name="l00021"></a><span class="lineno"> 21</span> <span class="comment"></span></div>
<div class="line"><a name="l00022"></a><span class="lineno"> 22</span> <span class="comment">/** Implementation of the Hierarchical Navigable Small World</span></div>
<div class="line"><a name="l00023"></a><span class="lineno"> 23</span> <span class="comment"> * datastructure.</span></div>
<div class="line"><a name="l00024"></a><span class="lineno"> 24</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00025"></a><span class="lineno"> 25</span> <span class="comment"> * Efficient and robust approximate nearest neighbor search using</span></div>
<div class="line"><a name="l00026"></a><span class="lineno"> 26</span> <span class="comment"> * Hierarchical Navigable Small World graphs</span></div>
<div class="line"><a name="l00027"></a><span class="lineno"> 27</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00028"></a><span class="lineno"> 28</span> <span class="comment"> * Yu. A. Malkov, D. A. Yashunin, arXiv 2017</span></div>
<div class="line"><a name="l00029"></a><span class="lineno"> 29</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00030"></a><span class="lineno"> 30</span> <span class="comment"> * This implmentation is heavily influenced by the NMSlib</span></div>
<div class="line"><a name="l00031"></a><span class="lineno"> 31</span> <span class="comment"> * implementation by Yury Malkov and Leonid Boystov</span></div>
<div class="line"><a name="l00032"></a><span class="lineno"> 32</span> <span class="comment"> * (https://github.com/searchivarius/nmslib)</span></div>
<div class="line"><a name="l00033"></a><span class="lineno"> 33</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00034"></a><span class="lineno"> 34</span> <span class="comment"> * The HNSW object stores only the neighbor link structure, see</span></div>
<div class="line"><a name="l00035"></a><span class="lineno"> 35</span> <span class="comment"> * IndexHNSW below for the full index object.</span></div>
<div class="line"><a name="l00036"></a><span class="lineno"> 36</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00037"></a><span class="lineno"> 37</span> </div>
<div class="line"><a name="l00038"></a><span class="lineno"> 38</span> <span class="keyword">struct </span>VisitedTable;</div>
<div class="line"><a name="l00039"></a><span class="lineno"> 39</span> </div>
<div class="line"><a name="l00040"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html"> 40</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1HNSW.html">HNSW</a> {</div>
<div class="line"><a name="l00041"></a><span class="lineno"> 41</span> <span class="comment"></span></div>
<div class="line"><a name="l00042"></a><span class="lineno"> 42</span> <span class="comment"> /// internal storage of vectors (32 bits: this is expensive)</span></div>
<div class="line"><a name="l00043"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74"> 43</a></span> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">storage_idx_t</a>;</div>
<div class="line"><a name="l00044"></a><span class="lineno"> 44</span> <span class="comment"></span></div>
<div class="line"><a name="l00045"></a><span class="lineno"> 45</span> <span class="comment"> /// Faiss results are 64-bit</span></div>
<div class="line"><a name="l00046"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0"> 46</a></span> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">faiss::Index::idx_t</a> <a class="code" href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0">idx_t</a>;</div>
<div class="line"><a name="l00047"></a><span class="lineno"> 47</span> <span class="comment"></span></div>
<div class="line"><a name="l00048"></a><span class="lineno"> 48</span> <span class="comment"> /** The HNSW structure does not store vectors, it only accesses</span></div>
<div class="line"><a name="l00049"></a><span class="lineno"> 49</span> <span class="comment"> * them through this class.</span></div>
<div class="line"><a name="l00050"></a><span class="lineno"> 50</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00051"></a><span class="lineno"> 51</span> <span class="comment"> * Functions are guaranteed to be be accessed only from 1 thread. */</span></div>
<div class="line"><a name="l00052"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW_1_1DistanceComputer.html"> 52</a></span>  <span class="keyword">struct </span><a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">DistanceComputer</a> {</div>
<div class="line"><a name="l00053"></a><span class="lineno"> 53</span> </div>
<div class="line"><a name="l00054"></a><span class="lineno"> 54</span>  <a class="code" href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0">idx_t</a> d;</div>
<div class="line"><a name="l00055"></a><span class="lineno"> 55</span> <span class="comment"></span></div>
<div class="line"><a name="l00056"></a><span class="lineno"> 56</span> <span class="comment"> /// called before computing distances</span></div>
<div class="line"><a name="l00057"></a><span class="lineno"> 57</span> <span class="comment"></span> <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html#a4713167f99ec2de58afa2fd20a952e33">set_query</a> (<span class="keyword">const</span> <span class="keywordtype">float</span> *x) = 0;</div>
<div class="line"><a name="l00058"></a><span class="lineno"> 58</span> <span class="comment"></span></div>
<div class="line"><a name="l00059"></a><span class="lineno"> 59</span> <span class="comment"> /// compute distance of vector i to current query</span></div>
<div class="line"><a name="l00060"></a><span class="lineno"> 60</span> <span class="comment"></span> <span class="keyword">virtual</span> <span class="keywordtype">float</span> <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html#ac3394f35cb68cb901a5078920bd46a2f">operator () </a>(<a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">storage_idx_t</a> i) = 0;</div>
<div class="line"><a name="l00061"></a><span class="lineno"> 61</span> <span class="comment"></span></div>
<div class="line"><a name="l00062"></a><span class="lineno"> 62</span> <span class="comment"> /// compute distance between two stored vectors</span></div>
<div class="line"><a name="l00063"></a><span class="lineno"> 63</span> <span class="comment"></span> <span class="keyword">virtual</span> <span class="keywordtype">float</span> <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html#acaa9a112486a82fd2abfbcd250d058b2">symmetric_dis</a>(<a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">storage_idx_t</a> i, <a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">storage_idx_t</a> j) = 0;</div>
<div class="line"><a name="l00064"></a><span class="lineno"> 64</span> </div>
<div class="line"><a name="l00065"></a><span class="lineno"> 65</span>  <span class="keyword">virtual</span> ~<a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">DistanceComputer</a> () {}</div>
<div class="line"><a name="l00066"></a><span class="lineno"> 66</span> </div>
<div class="line"><a name="l00067"></a><span class="lineno"> 67</span>  };</div>
<div class="line"><a name="l00068"></a><span class="lineno"> 68</span> <span class="comment"></span></div>
<div class="line"><a name="l00069"></a><span class="lineno"> 69</span> <span class="comment"> /// assignment probability to each layer (sum=1)</span></div>
<div class="line"><a name="l00070"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a907c94e0eca5200af1dc8d0aea482665"> 70</a></span> <span class="comment"></span> std::vector<double> <a class="code" href="structfaiss_1_1HNSW.html#a907c94e0eca5200af1dc8d0aea482665">assign_probas</a>;</div>
<div class="line"><a name="l00071"></a><span class="lineno"> 71</span> <span class="comment"></span></div>
<div class="line"><a name="l00072"></a><span class="lineno"> 72</span> <span class="comment"> /// number of neighbors stored per layer (cumulative), should not</span></div>
<div class="line"><a name="l00073"></a><span class="lineno"> 73</span> <span class="comment"> /// be changed after first add</span></div>
<div class="line"><a name="l00074"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a1c258bb88aae9b1a754ab4690d85ed41"> 74</a></span> <span class="comment"></span> std::vector<int> <a class="code" href="structfaiss_1_1HNSW.html#a1c258bb88aae9b1a754ab4690d85ed41">cum_nneighbor_per_level</a>;</div>
<div class="line"><a name="l00075"></a><span class="lineno"> 75</span> <span class="comment"></span></div>
<div class="line"><a name="l00076"></a><span class="lineno"> 76</span> <span class="comment"> /// level of each vector (base level = 1), size = ntotal</span></div>
<div class="line"><a name="l00077"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a44847954c98957404829182c7db1b8af"> 77</a></span> <span class="comment"></span> std::vector<int> <a class="code" href="structfaiss_1_1HNSW.html#a44847954c98957404829182c7db1b8af">levels</a>;</div>
<div class="line"><a name="l00078"></a><span class="lineno"> 78</span> <span class="comment"></span></div>
<div class="line"><a name="l00079"></a><span class="lineno"> 79</span> <span class="comment"> /// offsets[i] is the offset in the neighbors array where vector i is stored</span></div>
<div class="line"><a name="l00080"></a><span class="lineno"> 80</span> <span class="comment"> /// size ntotal + 1</span></div>
<div class="line"><a name="l00081"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a0b456c521194903b29ce7c157539d771"> 81</a></span> <span class="comment"></span> std::vector<size_t> <a class="code" href="structfaiss_1_1HNSW.html#a0b456c521194903b29ce7c157539d771">offsets</a>;</div>
<div class="line"><a name="l00082"></a><span class="lineno"> 82</span> <span class="comment"></span></div>
<div class="line"><a name="l00083"></a><span class="lineno"> 83</span> <span class="comment"> /// neighbors[offsets[i]:offsets[i+1]] is the list of neighbors of vector i</span></div>
<div class="line"><a name="l00084"></a><span class="lineno"> 84</span> <span class="comment"> /// for all levels. this is where all storage goes.</span></div>
<div class="line"><a name="l00085"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a27bd11ef9a651a94bcefa5291336fc58"> 85</a></span> <span class="comment"></span> std::vector<storage_idx_t> <a class="code" href="structfaiss_1_1HNSW.html#a27bd11ef9a651a94bcefa5291336fc58">neighbors</a>;</div>
<div class="line"><a name="l00086"></a><span class="lineno"> 86</span> <span class="comment"></span></div>
<div class="line"><a name="l00087"></a><span class="lineno"> 87</span> <span class="comment"> /// entry point in the search structure (one of the points with maximum level</span></div>
<div class="line"><a name="l00088"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a95547d97c90b361a040bae0fb0d892b4"> 88</a></span> <span class="comment"></span> <a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">storage_idx_t</a> <a class="code" href="structfaiss_1_1HNSW.html#a95547d97c90b361a040bae0fb0d892b4">entry_point</a>;</div>
<div class="line"><a name="l00089"></a><span class="lineno"> 89</span> </div>
<div class="line"><a name="l00090"></a><span class="lineno"> 90</span>  <a class="code" href="structfaiss_1_1RandomGenerator.html">faiss::RandomGenerator</a> rng;</div>
<div class="line"><a name="l00091"></a><span class="lineno"> 91</span> <span class="comment"></span></div>
<div class="line"><a name="l00092"></a><span class="lineno"> 92</span> <span class="comment"> /// maximum level</span></div>
<div class="line"><a name="l00093"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#afba18a290f5f759a8a7a64ed35b950eb"> 93</a></span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#afba18a290f5f759a8a7a64ed35b950eb">max_level</a>;</div>
<div class="line"><a name="l00094"></a><span class="lineno"> 94</span> <span class="comment"></span></div>
<div class="line"><a name="l00095"></a><span class="lineno"> 95</span> <span class="comment"> /// expansion factor at construction time</span></div>
<div class="line"><a name="l00096"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#aa7309dd7826761def38233c8bbbc0c63"> 96</a></span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#aa7309dd7826761def38233c8bbbc0c63">efConstruction</a>;</div>
<div class="line"><a name="l00097"></a><span class="lineno"> 97</span> <span class="comment"></span></div>
<div class="line"><a name="l00098"></a><span class="lineno"> 98</span> <span class="comment"> /// expansion factor at search time</span></div>
<div class="line"><a name="l00099"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a6d1cb35c4220bf554af90133c71ae04f"> 99</a></span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#a6d1cb35c4220bf554af90133c71ae04f">efSearch</a>;</div>
<div class="line"><a name="l00100"></a><span class="lineno"> 100</span> <span class="comment"></span></div>
<div class="line"><a name="l00101"></a><span class="lineno"> 101</span> <span class="comment"> /// during search: do we check whether the next best distance is good enough?</span></div>
<div class="line"><a name="l00102"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#adbf81f0b21102b942182c904892e0858"> 102</a></span> <span class="comment"></span> <span class="keywordtype">bool</span> <a class="code" href="structfaiss_1_1HNSW.html#adbf81f0b21102b942182c904892e0858">check_relative_distance</a>;</div>
<div class="line"><a name="l00103"></a><span class="lineno"> 103</span> <span class="comment"></span></div>
<div class="line"><a name="l00104"></a><span class="lineno"> 104</span> <span class="comment"> /// number of entry points in levels > 0.</span></div>
<div class="line"><a name="l00105"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSW.html#a857bef0db2dc0000f312cc8a95f857b2"> 105</a></span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#a857bef0db2dc0000f312cc8a95f857b2">upper_beam</a>;</div>
<div class="line"><a name="l00106"></a><span class="lineno"> 106</span> </div>
<div class="line"><a name="l00107"></a><span class="lineno"> 107</span>  <span class="comment">// methods that initialize the tree sizes</span></div>
<div class="line"><a name="l00108"></a><span class="lineno"> 108</span> <span class="comment"></span></div>
<div class="line"><a name="l00109"></a><span class="lineno"> 109</span> <span class="comment"> /// initialize the assign_probas and cum_nneighbor_per_level to</span></div>
<div class="line"><a name="l00110"></a><span class="lineno"> 110</span> <span class="comment"> /// have 2*M links on level 0 and M links on levels > 0</span></div>
<div class="line"><a name="l00111"></a><span class="lineno"> 111</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#ae7d955690da5d6376c203e81e124ba94">set_default_probas</a>(<span class="keywordtype">int</span> M, <span class="keywordtype">float</span> levelMult);</div>
<div class="line"><a name="l00112"></a><span class="lineno"> 112</span> <span class="comment"></span></div>
<div class="line"><a name="l00113"></a><span class="lineno"> 113</span> <span class="comment"> /// set nb of neighbors for this level (before adding anything)</span></div>
<div class="line"><a name="l00114"></a><span class="lineno"> 114</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#afdb5a17487296267efaaa94e6a08996d">set_nb_neighbors</a>(<span class="keywordtype">int</span> level_no, <span class="keywordtype">int</span> n);</div>
<div class="line"><a name="l00115"></a><span class="lineno"> 115</span> </div>
<div class="line"><a name="l00116"></a><span class="lineno"> 116</span>  <span class="comment">// methods that access the tree sizes</span></div>
<div class="line"><a name="l00117"></a><span class="lineno"> 117</span> <span class="comment"></span></div>
<div class="line"><a name="l00118"></a><span class="lineno"> 118</span> <span class="comment"> /// nb of neighbors for this level</span></div>
<div class="line"><a name="l00119"></a><span class="lineno"> 119</span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#ad497ea80f352c33242ba7835370c2dba">nb_neighbors</a>(<span class="keywordtype">int</span> layer_no) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00120"></a><span class="lineno"> 120</span> <span class="comment"></span></div>
<div class="line"><a name="l00121"></a><span class="lineno"> 121</span> <span class="comment"> /// cumumlative nb up to (and excluding) this level</span></div>
<div class="line"><a name="l00122"></a><span class="lineno"> 122</span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#a49b512eaaa54ead77b564cad8e3e6ebd">cum_nb_neighbors</a>(<span class="keywordtype">int</span> layer_no) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00123"></a><span class="lineno"> 123</span> <span class="comment"></span></div>
<div class="line"><a name="l00124"></a><span class="lineno"> 124</span> <span class="comment"> /// range of entries in the neighbors table of vertex no at layer_no</span></div>
<div class="line"><a name="l00125"></a><span class="lineno"> 125</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#aa3ae6a80d358e59e3af23f918253f61d">neighbor_range</a>(<a class="code" href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0">idx_t</a> no, <span class="keywordtype">int</span> layer_no,</div>
<div class="line"><a name="l00126"></a><span class="lineno"> 126</span>  <span class="keywordtype">size_t</span> * begin, <span class="keywordtype">size_t</span> * end) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00127"></a><span class="lineno"> 127</span> <span class="comment"></span></div>
<div class="line"><a name="l00128"></a><span class="lineno"> 128</span> <span class="comment"> /// only mandatory parameter: nb of neighbors</span></div>
<div class="line"><a name="l00129"></a><span class="lineno"> 129</span> <span class="comment"></span> <span class="keyword">explicit</span> <a class="code" href="structfaiss_1_1HNSW.html#a1fc852810a2497a8eb2c41635ec05520">HNSW</a>(<span class="keywordtype">int</span> M = 32);</div>
<div class="line"><a name="l00130"></a><span class="lineno"> 130</span> <span class="comment"></span></div>
<div class="line"><a name="l00131"></a><span class="lineno"> 131</span> <span class="comment"> /// pick a random level for a new point</span></div>
<div class="line"><a name="l00132"></a><span class="lineno"> 132</span> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1HNSW.html#aa6dfdaed7bc0ad895774315166fcb197">random_level</a>();</div>
<div class="line"><a name="l00133"></a><span class="lineno"> 133</span> <span class="comment"></span></div>
<div class="line"><a name="l00134"></a><span class="lineno"> 134</span> <span class="comment"> /// add n random levels to table (for debugging...)</span></div>
<div class="line"><a name="l00135"></a><span class="lineno"> 135</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#a26710980aaca3c1c8729e5e055a42ebe">fill_with_random_links</a>(<span class="keywordtype">size_t</span> n);</div>
<div class="line"><a name="l00136"></a><span class="lineno"> 136</span> <span class="comment"></span></div>
<div class="line"><a name="l00137"></a><span class="lineno"> 137</span> <span class="comment"> /** add point pt_id on all levels <= pt_level and build the link</span></div>
<div class="line"><a name="l00138"></a><span class="lineno"> 138</span> <span class="comment"> * structure for them. */</span></div>
<div class="line"><a name="l00139"></a><span class="lineno"> 139</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#a314b809de6f329662ab09f258b49afb3">add_with_locks</a>(<a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">DistanceComputer</a> & ptdis, <span class="keywordtype">int</span> pt_level, <span class="keywordtype">int</span> pt_id,</div>
<div class="line"><a name="l00140"></a><span class="lineno"> 140</span>  std::vector<omp_lock_t> & locks,</div>
<div class="line"><a name="l00141"></a><span class="lineno"> 141</span>  <a class="code" href="structfaiss_1_1VisitedTable.html">VisitedTable</a> &vt);</div>
<div class="line"><a name="l00142"></a><span class="lineno"> 142</span> </div>
<div class="line"><a name="l00143"></a><span class="lineno"> 143</span> <span class="comment"></span></div>
<div class="line"><a name="l00144"></a><span class="lineno"> 144</span> <span class="comment"> /// search interface</span></div>
<div class="line"><a name="l00145"></a><span class="lineno"> 145</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1HNSW.html#a330107a5801680609932849fc9404594">search</a>(<a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">DistanceComputer</a> & qdis, <span class="keywordtype">int</span> k,</div>
<div class="line"><a name="l00146"></a><span class="lineno"> 146</span>  <a class="code" href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0">idx_t</a> *I, <span class="keywordtype">float</span> * D,</div>
<div class="line"><a name="l00147"></a><span class="lineno"> 147</span>  <a class="code" href="structfaiss_1_1VisitedTable.html">VisitedTable</a> &vt) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00148"></a><span class="lineno"> 148</span> </div>
<div class="line"><a name="l00149"></a><span class="lineno"> 149</span>  <span class="keywordtype">void</span> reset();</div>
<div class="line"><a name="l00150"></a><span class="lineno"> 150</span> </div>
<div class="line"><a name="l00151"></a><span class="lineno"> 151</span>  <span class="keywordtype">void</span> clear_neighbor_tables(<span class="keywordtype">int</span> level);</div>
<div class="line"><a name="l00152"></a><span class="lineno"> 152</span>  <span class="keywordtype">void</span> print_neighbor_stats(<span class="keywordtype">int</span> level) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00153"></a><span class="lineno"> 153</span> };</div>
<div class="line"><a name="l00154"></a><span class="lineno"> 154</span> </div>
<div class="line"><a name="l00155"></a><span class="lineno"> 155</span> </div>
<div class="line"><a name="l00156"></a><span class="lineno"><a class="line" href="structfaiss_1_1HNSWStats.html"> 156</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1HNSWStats.html">HNSWStats</a> {</div>
<div class="line"><a name="l00157"></a><span class="lineno"> 157</span>  <span class="keywordtype">size_t</span> n1, n2, n3;</div>
<div class="line"><a name="l00158"></a><span class="lineno"> 158</span>  <span class="keywordtype">size_t</span> ndis;</div>
<div class="line"><a name="l00159"></a><span class="lineno"> 159</span>  <span class="keywordtype">size_t</span> nreorder;</div>
<div class="line"><a name="l00160"></a><span class="lineno"> 160</span>  <span class="keywordtype">bool</span> view;</div>
<div class="line"><a name="l00161"></a><span class="lineno"> 161</span> </div>
<div class="line"><a name="l00162"></a><span class="lineno"> 162</span>  <a class="code" href="structfaiss_1_1HNSWStats.html">HNSWStats</a> () {reset (); }</div>
<div class="line"><a name="l00163"></a><span class="lineno"> 163</span>  <span class="keywordtype">void</span> reset ();</div>
<div class="line"><a name="l00164"></a><span class="lineno"> 164</span> };</div>
<div class="line"><a name="l00165"></a><span class="lineno"> 165</span> </div>
<div class="line"><a name="l00166"></a><span class="lineno"> 166</span> <span class="comment">// global var that collects them all</span></div>
<div class="line"><a name="l00167"></a><span class="lineno"> 167</span> <span class="keyword">extern</span> <a class="code" href="structfaiss_1_1HNSWStats.html">HNSWStats</a> hnsw_stats;</div>
<div class="line"><a name="l00168"></a><span class="lineno"> 168</span> </div>
<div class="line"><a name="l00169"></a><span class="lineno"> 169</span> <span class="keyword">class </span><a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a>;</div>
<div class="line"><a name="l00170"></a><span class="lineno"> 170</span> </div>
<div class="line"><a name="l00171"></a><span class="lineno"><a class="line" href="structfaiss_1_1ReconstructFromNeighbors.html"> 171</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html">ReconstructFromNeighbors</a> {</div>
<div class="line"><a name="l00172"></a><span class="lineno"> 172</span>  <span class="keyword">typedef</span> <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">Index::idx_t</a> idx_t;</div>
<div class="line"><a name="l00173"></a><span class="lineno"> 173</span>  <span class="keyword">typedef</span> <a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">HNSW::storage_idx_t</a> storage_idx_t;</div>
<div class="line"><a name="l00174"></a><span class="lineno"> 174</span> </div>
<div class="line"><a name="l00175"></a><span class="lineno"> 175</span>  <span class="keyword">const</span> <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> & index;</div>
<div class="line"><a name="l00176"></a><span class="lineno"> 176</span>  <span class="keywordtype">size_t</span> M; <span class="comment">// number of neighbors</span></div>
<div class="line"><a name="l00177"></a><span class="lineno"> 177</span>  <span class="keywordtype">size_t</span> k; <span class="comment">// number of codebook entries</span></div>
<div class="line"><a name="l00178"></a><span class="lineno"> 178</span>  <span class="keywordtype">size_t</span> nsq; <span class="comment">// number of subvectors</span></div>
<div class="line"><a name="l00179"></a><span class="lineno"> 179</span>  <span class="keywordtype">size_t</span> code_size;</div>
<div class="line"><a name="l00180"></a><span class="lineno"> 180</span>  <span class="keywordtype">int</span> k_reorder; <span class="comment">// nb to reorder. -1 = all</span></div>
<div class="line"><a name="l00181"></a><span class="lineno"> 181</span> </div>
<div class="line"><a name="l00182"></a><span class="lineno"> 182</span>  std::vector<float> codebook; <span class="comment">// size nsq * k * (M + 1)</span></div>
<div class="line"><a name="l00183"></a><span class="lineno"> 183</span> </div>
<div class="line"><a name="l00184"></a><span class="lineno"> 184</span>  std::vector<uint8_t> codes; <span class="comment">// size ntotal * code_size</span></div>
<div class="line"><a name="l00185"></a><span class="lineno"> 185</span>  <span class="keywordtype">size_t</span> ntotal;</div>
<div class="line"><a name="l00186"></a><span class="lineno"> 186</span>  <span class="keywordtype">size_t</span> d, dsub; <span class="comment">// derived values</span></div>
<div class="line"><a name="l00187"></a><span class="lineno"> 187</span> </div>
<div class="line"><a name="l00188"></a><span class="lineno"> 188</span>  <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html">ReconstructFromNeighbors</a>(<span class="keyword">const</span> <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> & index,</div>
<div class="line"><a name="l00189"></a><span class="lineno"> 189</span>  <span class="keywordtype">size_t</span> k=256, <span class="keywordtype">size_t</span> nsq=1);</div>
<div class="line"><a name="l00190"></a><span class="lineno"> 190</span> <span class="comment"></span></div>
<div class="line"><a name="l00191"></a><span class="lineno"> 191</span> <span class="comment"> /// codes must be added in the correct order and the IndexHNSW</span></div>
<div class="line"><a name="l00192"></a><span class="lineno"> 192</span> <span class="comment"> /// must be populated and sorted</span></div>
<div class="line"><a name="l00193"></a><span class="lineno"> 193</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html#a454b7a5f7437a257df7404f5778fc833">add_codes</a>(<span class="keywordtype">size_t</span> n, <span class="keyword">const</span> <span class="keywordtype">float</span> *x);</div>
<div class="line"><a name="l00194"></a><span class="lineno"> 194</span> </div>
<div class="line"><a name="l00195"></a><span class="lineno"> 195</span>  <span class="keywordtype">size_t</span> compute_distances(<span class="keywordtype">size_t</span> n, <span class="keyword">const</span> idx_t *shortlist,</div>
<div class="line"><a name="l00196"></a><span class="lineno"> 196</span>  <span class="keyword">const</span> <span class="keywordtype">float</span> *query, <span class="keywordtype">float</span> *distances) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00197"></a><span class="lineno"> 197</span> <span class="comment"></span></div>
<div class="line"><a name="l00198"></a><span class="lineno"> 198</span> <span class="comment"> /// called by add_codes</span></div>
<div class="line"><a name="l00199"></a><span class="lineno"> 199</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html#a88ca99742dccc52ebb3324b507b6c872">estimate_code</a>(<span class="keyword">const</span> <span class="keywordtype">float</span> *x, storage_idx_t i, uint8_t *code) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00200"></a><span class="lineno"> 200</span> <span class="comment"></span></div>
<div class="line"><a name="l00201"></a><span class="lineno"> 201</span> <span class="comment"> /// called by compute_distances</span></div>
<div class="line"><a name="l00202"></a><span class="lineno"> 202</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html#a6cf260c530e273e4d676804ac71128f8">reconstruct</a>(storage_idx_t i, <span class="keywordtype">float</span> *x, <span class="keywordtype">float</span> *tmp) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00203"></a><span class="lineno"> 203</span> </div>
<div class="line"><a name="l00204"></a><span class="lineno"> 204</span>  <span class="keywordtype">void</span> reconstruct_n(storage_idx_t n0, storage_idx_t ni, <span class="keywordtype">float</span> *x) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00205"></a><span class="lineno"> 205</span> <span class="comment"></span></div>
<div class="line"><a name="l00206"></a><span class="lineno"> 206</span> <span class="comment"> /// get the M+1 -by-d table for neighbor coordinates for vector i</span></div>
<div class="line"><a name="l00207"></a><span class="lineno"> 207</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html#aed256bdd9f48dc93cb9e33cfdfd5bde7">get_neighbor_table</a>(storage_idx_t i, <span class="keywordtype">float</span> *out) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00208"></a><span class="lineno"> 208</span> </div>
<div class="line"><a name="l00209"></a><span class="lineno"> 209</span> };</div>
<div class="line"><a name="l00210"></a><span class="lineno"> 210</span> </div>
<div class="line"><a name="l00211"></a><span class="lineno"> 211</span> <span class="comment"></span></div>
<div class="line"><a name="l00212"></a><span class="lineno"> 212</span> <span class="comment">/** The HNSW index is a normal random-access index with a HNSW</span></div>
<div class="line"><a name="l00213"></a><span class="lineno"> 213</span> <span class="comment"> * link structure built on top */</span></div>
<div class="line"><a name="l00214"></a><span class="lineno"> 214</span> </div>
<div class="line"><a name="l00215"></a><span class="lineno"><a class="line" href="structfaiss_1_1IndexHNSW.html"> 215</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a>: <a class="code" href="structfaiss_1_1Index.html">Index</a> {</div>
<div class="line"><a name="l00216"></a><span class="lineno"> 216</span> </div>
<div class="line"><a name="l00217"></a><span class="lineno"> 217</span>  <span class="keyword">typedef</span> <a class="code" href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">HNSW::storage_idx_t</a> storage_idx_t;</div>
<div class="line"><a name="l00218"></a><span class="lineno"> 218</span> </div>
<div class="line"><a name="l00219"></a><span class="lineno"> 219</span>  <span class="comment">// the link strcuture</span></div>
<div class="line"><a name="l00220"></a><span class="lineno"> 220</span>  <a class="code" href="structfaiss_1_1HNSW.html">HNSW</a> hnsw;</div>
<div class="line"><a name="l00221"></a><span class="lineno"> 221</span> </div>
<div class="line"><a name="l00222"></a><span class="lineno"> 222</span>  <span class="comment">// the sequential storage</span></div>
<div class="line"><a name="l00223"></a><span class="lineno"> 223</span>  <span class="keywordtype">bool</span> own_fields;</div>
<div class="line"><a name="l00224"></a><span class="lineno"> 224</span>  <a class="code" href="structfaiss_1_1Index.html">Index</a> * storage;</div>
<div class="line"><a name="l00225"></a><span class="lineno"> 225</span> </div>
<div class="line"><a name="l00226"></a><span class="lineno"> 226</span>  <a class="code" href="structfaiss_1_1ReconstructFromNeighbors.html">ReconstructFromNeighbors</a> *reconstruct_from_neighbors;</div>
<div class="line"><a name="l00227"></a><span class="lineno"> 227</span> </div>
<div class="line"><a name="l00228"></a><span class="lineno"> 228</span>  <span class="keyword">explicit</span> <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> (<span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1Index.html#a2a002388d2c081c2dbab8508dcefe73d">d</a> = 0, <span class="keywordtype">int</span> M = 32);</div>
<div class="line"><a name="l00229"></a><span class="lineno"> 229</span>  <span class="keyword">explicit</span> <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> (<a class="code" href="structfaiss_1_1Index.html">Index</a> * storage, <span class="keywordtype">int</span> M = 32);</div>
<div class="line"><a name="l00230"></a><span class="lineno"> 230</span> </div>
<div class="line"><a name="l00231"></a><span class="lineno"> 231</span>  ~<a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a>() <span class="keyword">override</span>;</div>
<div class="line"><a name="l00232"></a><span class="lineno"> 232</span> </div>
<div class="line"><a name="l00233"></a><span class="lineno"> 233</span>  <span class="comment">// get a DistanceComputer object for this kind of storage</span></div>
<div class="line"><a name="l00234"></a><span class="lineno"> 234</span>  <span class="keyword">virtual</span> <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">HNSW::DistanceComputer</a> * get_distance_computer() <span class="keyword">const</span> = 0;</div>
<div class="line"><a name="l00235"></a><span class="lineno"> 235</span> </div>
<div class="line"><a name="l00236"></a><span class="lineno"> 236</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#a04a761ce17d0f9040b3bc8a77bd627d9">add</a>(<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span> *x) <span class="keyword">override</span>;</div>
<div class="line"><a name="l00237"></a><span class="lineno"> 237</span> <span class="comment"></span></div>
<div class="line"><a name="l00238"></a><span class="lineno"> 238</span> <span class="comment"> /// Trains the storage if needed</span></div>
<div class="line"><a name="l00239"></a><span class="lineno"> 239</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#a40bc6d2c67545f95e322c63d68a47140">train</a>(<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span>* x) <span class="keyword">override</span>;</div>
<div class="line"><a name="l00240"></a><span class="lineno"> 240</span> <span class="comment"></span></div>
<div class="line"><a name="l00241"></a><span class="lineno"> 241</span> <span class="comment"> /// entry point for search</span></div>
<div class="line"><a name="l00242"></a><span class="lineno"> 242</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#ae0ddf6ab4a54239a25d6277e21e8548e">search</a> (<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span> *x, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> k,</div>
<div class="line"><a name="l00243"></a><span class="lineno"> 243</span>  <span class="keywordtype">float</span> *distances, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> *labels) <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00244"></a><span class="lineno"> 244</span> </div>
<div class="line"><a name="l00245"></a><span class="lineno"> 245</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#a660e5c8de1ba9c71bf3fe1f3bf0c8812">reconstruct</a>(<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> key, <span class="keywordtype">float</span>* recons) <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00246"></a><span class="lineno"> 246</span> </div>
<div class="line"><a name="l00247"></a><span class="lineno"> 247</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#ad4b9f97d42e2521e01f8b60012985396">reset</a> () <span class="keyword">override</span>;</div>
<div class="line"><a name="l00248"></a><span class="lineno"> 248</span> </div>
<div class="line"><a name="l00249"></a><span class="lineno"> 249</span>  <span class="keywordtype">void</span> shrink_level_0_neighbors(<span class="keywordtype">int</span> size);</div>
<div class="line"><a name="l00250"></a><span class="lineno"> 250</span> <span class="comment"></span></div>
<div class="line"><a name="l00251"></a><span class="lineno"> 251</span> <span class="comment"> /** Perform search only on level 0, given the starting points for</span></div>
<div class="line"><a name="l00252"></a><span class="lineno"> 252</span> <span class="comment"> * each vertex.</span></div>
<div class="line"><a name="l00253"></a><span class="lineno"> 253</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00254"></a><span class="lineno"> 254</span> <span class="comment"> * @param search_type 1:perform one search per nprobe, 2: enqueue</span></div>
<div class="line"><a name="l00255"></a><span class="lineno"> 255</span> <span class="comment"> * all entry points</span></div>
<div class="line"><a name="l00256"></a><span class="lineno"> 256</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00257"></a><span class="lineno"> 257</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#a5b619a41ddd52f0377efb701829c1e43">search_level_0</a>(<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span> *x, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> k,</div>
<div class="line"><a name="l00258"></a><span class="lineno"> 258</span>  <span class="keyword">const</span> storage_idx_t *nearest, <span class="keyword">const</span> <span class="keywordtype">float</span> *nearest_d,</div>
<div class="line"><a name="l00259"></a><span class="lineno"> 259</span>  <span class="keywordtype">float</span> *distances, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> *labels, <span class="keywordtype">int</span> nprobe = 1,</div>
<div class="line"><a name="l00260"></a><span class="lineno"> 260</span>  <span class="keywordtype">int</span> search_type = 1) <span class="keyword">const</span>;</div>
<div class="line"><a name="l00261"></a><span class="lineno"> 261</span> <span class="comment"></span></div>
<div class="line"><a name="l00262"></a><span class="lineno"> 262</span> <span class="comment"> /// alternative graph building</span></div>
<div class="line"><a name="l00263"></a><span class="lineno"> 263</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#a9a86c58212f3f9cf88394f5297cba525">init_level_0_from_knngraph</a>(</div>
<div class="line"><a name="l00264"></a><span class="lineno"> 264</span>  <span class="keywordtype">int</span> k, <span class="keyword">const</span> <span class="keywordtype">float</span> *D, <span class="keyword">const</span> <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> *I);</div>
<div class="line"><a name="l00265"></a><span class="lineno"> 265</span> <span class="comment"></span></div>
<div class="line"><a name="l00266"></a><span class="lineno"> 266</span> <span class="comment"> /// alternative graph building</span></div>
<div class="line"><a name="l00267"></a><span class="lineno"> 267</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW.html#ab9c75063090927f8f65d1896b6949af4">init_level_0_from_entry_points</a>(</div>
<div class="line"><a name="l00268"></a><span class="lineno"> 268</span>  <span class="keywordtype">int</span> npt, <span class="keyword">const</span> storage_idx_t *points,</div>
<div class="line"><a name="l00269"></a><span class="lineno"> 269</span>  <span class="keyword">const</span> storage_idx_t *nearests);</div>
<div class="line"><a name="l00270"></a><span class="lineno"> 270</span> </div>
<div class="line"><a name="l00271"></a><span class="lineno"> 271</span>  <span class="comment">// reorder links from nearest to farthest</span></div>
<div class="line"><a name="l00272"></a><span class="lineno"> 272</span>  <span class="keywordtype">void</span> reorder_links();</div>
<div class="line"><a name="l00273"></a><span class="lineno"> 273</span> </div>
<div class="line"><a name="l00274"></a><span class="lineno"> 274</span>  <span class="keywordtype">void</span> link_singletons();</div>
<div class="line"><a name="l00275"></a><span class="lineno"> 275</span> };</div>
<div class="line"><a name="l00276"></a><span class="lineno"> 276</span> </div>
<div class="line"><a name="l00277"></a><span class="lineno"> 277</span> </div>
<div class="line"><a name="l00278"></a><span class="lineno"> 278</span> <span class="comment"></span></div>
<div class="line"><a name="l00279"></a><span class="lineno"> 279</span> <span class="comment">/** Flat index topped with with a HNSW structure to access elements</span></div>
<div class="line"><a name="l00280"></a><span class="lineno"> 280</span> <span class="comment"> * more efficiently.</span></div>
<div class="line"><a name="l00281"></a><span class="lineno"> 281</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00282"></a><span class="lineno"> 282</span> </div>
<div class="line"><a name="l00283"></a><span class="lineno"><a class="line" href="structfaiss_1_1IndexHNSWFlat.html"> 283</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1IndexHNSWFlat.html">IndexHNSWFlat</a>: <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> {</div>
<div class="line"><a name="l00284"></a><span class="lineno"> 284</span>  <a class="code" href="structfaiss_1_1IndexHNSWFlat.html">IndexHNSWFlat</a>();</div>
<div class="line"><a name="l00285"></a><span class="lineno"> 285</span>  <a class="code" href="structfaiss_1_1IndexHNSWFlat.html">IndexHNSWFlat</a>(<span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1Index.html#a2a002388d2c081c2dbab8508dcefe73d">d</a>, <span class="keywordtype">int</span> M);</div>
<div class="line"><a name="l00286"></a><span class="lineno"> 286</span>  <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">HNSW::DistanceComputer</a> * get_distance_computer() <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00287"></a><span class="lineno"> 287</span> };</div>
<div class="line"><a name="l00288"></a><span class="lineno"> 288</span> <span class="comment"></span></div>
<div class="line"><a name="l00289"></a><span class="lineno"> 289</span> <span class="comment">/** PQ index topped with with a HNSW structure to access elements</span></div>
<div class="line"><a name="l00290"></a><span class="lineno"> 290</span> <span class="comment"> * more efficiently.</span></div>
<div class="line"><a name="l00291"></a><span class="lineno"> 291</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00292"></a><span class="lineno"><a class="line" href="structfaiss_1_1IndexHNSWPQ.html"> 292</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1IndexHNSWPQ.html">IndexHNSWPQ</a>: <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> {</div>
<div class="line"><a name="l00293"></a><span class="lineno"> 293</span>  <a class="code" href="structfaiss_1_1IndexHNSWPQ.html">IndexHNSWPQ</a>();</div>
<div class="line"><a name="l00294"></a><span class="lineno"> 294</span>  <a class="code" href="structfaiss_1_1IndexHNSWPQ.html">IndexHNSWPQ</a>(<span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1Index.html#a2a002388d2c081c2dbab8508dcefe73d">d</a>, <span class="keywordtype">int</span> pq_m, <span class="keywordtype">int</span> M);</div>
<div class="line"><a name="l00295"></a><span class="lineno"> 295</span>  <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSWPQ.html#ae99b976eeb25717d10055b1786aa011c">train</a>(<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span>* x) <span class="keyword">override</span>;</div>
<div class="line"><a name="l00296"></a><span class="lineno"> 296</span>  <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">HNSW::DistanceComputer</a> * get_distance_computer() <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00297"></a><span class="lineno"> 297</span> };</div>
<div class="line"><a name="l00298"></a><span class="lineno"> 298</span> <span class="comment"></span></div>
<div class="line"><a name="l00299"></a><span class="lineno"> 299</span> <span class="comment">/** SQ index topped with with a HNSW structure to access elements</span></div>
<div class="line"><a name="l00300"></a><span class="lineno"> 300</span> <span class="comment"> * more efficiently.</span></div>
<div class="line"><a name="l00301"></a><span class="lineno"> 301</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00302"></a><span class="lineno"><a class="line" href="structfaiss_1_1IndexHNSWSQ.html"> 302</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1IndexHNSWSQ.html">IndexHNSWSQ</a>: <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> {</div>
<div class="line"><a name="l00303"></a><span class="lineno"> 303</span>  <a class="code" href="structfaiss_1_1IndexHNSWSQ.html">IndexHNSWSQ</a>();</div>
<div class="line"><a name="l00304"></a><span class="lineno"> 304</span>  <a class="code" href="structfaiss_1_1IndexHNSWSQ.html">IndexHNSWSQ</a>(<span class="keywordtype">int</span> <a class="code" href="structfaiss_1_1Index.html#a2a002388d2c081c2dbab8508dcefe73d">d</a>, <a class="code" href="structfaiss_1_1ScalarQuantizer.html#a1201dbd1611fa5c10782ade5d0e4952e">ScalarQuantizer::QuantizerType</a> qtype, <span class="keywordtype">int</span> M);</div>
<div class="line"><a name="l00305"></a><span class="lineno"> 305</span>  <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">HNSW::DistanceComputer</a> * get_distance_computer() <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00306"></a><span class="lineno"> 306</span> };</div>
<div class="line"><a name="l00307"></a><span class="lineno"> 307</span> <span class="comment"></span></div>
<div class="line"><a name="l00308"></a><span class="lineno"> 308</span> <span class="comment">/** 2-level code structure with fast random access</span></div>
<div class="line"><a name="l00309"></a><span class="lineno"> 309</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00310"></a><span class="lineno"><a class="line" href="structfaiss_1_1IndexHNSW2Level.html"> 310</a></span> <span class="keyword">struct </span><a class="code" href="structfaiss_1_1IndexHNSW2Level.html">IndexHNSW2Level</a>: <a class="code" href="structfaiss_1_1IndexHNSW.html">IndexHNSW</a> {</div>
<div class="line"><a name="l00311"></a><span class="lineno"> 311</span>  <a class="code" href="structfaiss_1_1IndexHNSW2Level.html">IndexHNSW2Level</a>();</div>
<div class="line"><a name="l00312"></a><span class="lineno"> 312</span>  <a class="code" href="structfaiss_1_1IndexHNSW2Level.html">IndexHNSW2Level</a>(<a class="code" href="structfaiss_1_1Index.html">Index</a> *quantizer, <span class="keywordtype">size_t</span> nlist, <span class="keywordtype">int</span> m_pq, <span class="keywordtype">int</span> M);</div>
<div class="line"><a name="l00313"></a><span class="lineno"> 313</span>  <a class="code" href="structfaiss_1_1HNSW_1_1DistanceComputer.html">HNSW::DistanceComputer</a> * get_distance_computer() <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00314"></a><span class="lineno"> 314</span>  <span class="keywordtype">void</span> flip_to_ivf();</div>
<div class="line"><a name="l00315"></a><span class="lineno"> 315</span> <span class="comment"></span></div>
<div class="line"><a name="l00316"></a><span class="lineno"> 316</span> <span class="comment"> /// entry point for search</span></div>
<div class="line"><a name="l00317"></a><span class="lineno"> 317</span> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="structfaiss_1_1IndexHNSW2Level.html#a50a087a17ce5a7a1fbcca0836959b4ec">search</a> (<a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> n, <span class="keyword">const</span> <span class="keywordtype">float</span> *x, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> k,</div>
<div class="line"><a name="l00318"></a><span class="lineno"> 318</span>  <span class="keywordtype">float</span> *distances, <a class="code" href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">idx_t</a> *labels) <span class="keyword">const override</span>;</div>
<div class="line"><a name="l00319"></a><span class="lineno"> 319</span> </div>
<div class="line"><a name="l00320"></a><span class="lineno"> 320</span> };</div>
<div class="line"><a name="l00321"></a><span class="lineno"> 321</span> </div>
<div class="line"><a name="l00322"></a><span class="lineno"> 322</span> </div>
<div class="line"><a name="l00323"></a><span class="lineno"> 323</span> </div>
<div class="line"><a name="l00324"></a><span class="lineno"> 324</span> };</div>
<div class="ttc" id="structfaiss_1_1RandomGenerator_html"><div class="ttname"><a href="structfaiss_1_1RandomGenerator.html">faiss::RandomGenerator</a></div><div class="ttdoc">random generator that can be used in multithreaded contexts </div><div class="ttdef"><b>Definition:</b> <a href="utils_8h_source.html#l00048">utils.h:48</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a314b809de6f329662ab09f258b49afb3"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a314b809de6f329662ab09f258b49afb3">faiss::HNSW::add_with_locks</a></div><div class="ttdeci">void add_with_locks(DistanceComputer &ptdis, int pt_level, int pt_id, std::vector< omp_lock_t > &locks, VisitedTable &vt)</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00657">IndexHNSW.cpp:657</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSWSQ_html"><div class="ttname"><a href="structfaiss_1_1IndexHNSWSQ.html">faiss::IndexHNSWSQ</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00302">IndexHNSW.h:302</a></div></div>
<div class="ttc" id="structfaiss_1_1ScalarQuantizer_html_a1201dbd1611fa5c10782ade5d0e4952e"><div class="ttname"><a href="structfaiss_1_1ScalarQuantizer.html#a1201dbd1611fa5c10782ade5d0e4952e">faiss::ScalarQuantizer::QuantizerType</a></div><div class="ttdeci">QuantizerType</div><div class="ttdef"><b>Definition:</b> <a href="IndexScalarQuantizer_8h_source.html#l00032">IndexScalarQuantizer.h:32</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_aa3ae6a80d358e59e3af23f918253f61d"><div class="ttname"><a href="structfaiss_1_1HNSW.html#aa3ae6a80d358e59e3af23f918253f61d">faiss::HNSW::neighbor_range</a></div><div class="ttdeci">void neighbor_range(idx_t no, int layer_no, size_t *begin, size_t *end) const </div><div class="ttdoc">range of entries in the neighbors table of vertex no at layer_no </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00517">IndexHNSW.cpp:517</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSWPQ_html_ae99b976eeb25717d10055b1786aa011c"><div class="ttname"><a href="structfaiss_1_1IndexHNSWPQ.html#ae99b976eeb25717d10055b1786aa011c">faiss::IndexHNSWPQ::train</a></div><div class="ttdeci">void train(idx_t n, const float *x) override</div><div class="ttdoc">Trains the storage if needed. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01733">IndexHNSW.cpp:1733</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_1_1DistanceComputer_html_ac3394f35cb68cb901a5078920bd46a2f"><div class="ttname"><a href="structfaiss_1_1HNSW_1_1DistanceComputer.html#ac3394f35cb68cb901a5078920bd46a2f">faiss::HNSW::DistanceComputer::operator()</a></div><div class="ttdeci">virtual float operator()(storage_idx_t i)=0</div><div class="ttdoc">compute distance of vector i to current query </div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_ad497ea80f352c33242ba7835370c2dba"><div class="ttname"><a href="structfaiss_1_1HNSW.html#ad497ea80f352c33242ba7835370c2dba">faiss::HNSW::nb_neighbors</a></div><div class="ttdeci">int nb_neighbors(int layer_no) const </div><div class="ttdoc">nb of neighbors for this level </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00497">IndexHNSW.cpp:497</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW2Level_html_a50a087a17ce5a7a1fbcca0836959b4ec"><div class="ttname"><a href="structfaiss_1_1IndexHNSW2Level.html#a50a087a17ce5a7a1fbcca0836959b4ec">faiss::IndexHNSW2Level::search</a></div><div class="ttdeci">void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override</div><div class="ttdoc">entry point for search </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l02071">IndexHNSW.cpp:2071</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a95547d97c90b361a040bae0fb0d892b4"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a95547d97c90b361a040bae0fb0d892b4">faiss::HNSW::entry_point</a></div><div class="ttdeci">storage_idx_t entry_point</div><div class="ttdoc">entry point in the search structure (one of the points with maximum level </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00088">IndexHNSW.h:88</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a49b512eaaa54ead77b564cad8e3e6ebd"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a49b512eaaa54ead77b564cad8e3e6ebd">faiss::HNSW::cum_nb_neighbors</a></div><div class="ttdeci">int cum_nb_neighbors(int layer_no) const </div><div class="ttdoc">cumumlative nb up to (and excluding) this level </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00512">IndexHNSW.cpp:512</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_1_1DistanceComputer_html_acaa9a112486a82fd2abfbcd250d058b2"><div class="ttname"><a href="structfaiss_1_1HNSW_1_1DistanceComputer.html#acaa9a112486a82fd2abfbcd250d058b2">faiss::HNSW::DistanceComputer::symmetric_dis</a></div><div class="ttdeci">virtual float symmetric_dis(storage_idx_t i, storage_idx_t j)=0</div><div class="ttdoc">compute distance between two stored vectors </div></div>
<div class="ttc" id="structfaiss_1_1ReconstructFromNeighbors_html"><div class="ttname"><a href="structfaiss_1_1ReconstructFromNeighbors.html">faiss::ReconstructFromNeighbors</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00171">IndexHNSW.h:171</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a907c94e0eca5200af1dc8d0aea482665"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a907c94e0eca5200af1dc8d0aea482665">faiss::HNSW::assign_probas</a></div><div class="ttdeci">std::vector< double > assign_probas</div><div class="ttdoc">assignment probability to each layer (sum=1) </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00070">IndexHNSW.h:70</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a1c258bb88aae9b1a754ab4690d85ed41"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a1c258bb88aae9b1a754ab4690d85ed41">faiss::HNSW::cum_nneighbor_per_level</a></div><div class="ttdeci">std::vector< int > cum_nneighbor_per_level</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00074">IndexHNSW.h:74</a></div></div>
<div class="ttc" id="structfaiss_1_1ReconstructFromNeighbors_html_aed256bdd9f48dc93cb9e33cfdfd5bde7"><div class="ttname"><a href="structfaiss_1_1ReconstructFromNeighbors.html#aed256bdd9f48dc93cb9e33cfdfd5bde7">faiss::ReconstructFromNeighbors::get_neighbor_table</a></div><div class="ttdeci">void get_neighbor_table(storage_idx_t i, float *out) const </div><div class="ttdoc">get the M+1 -by-d table for neighbor coordinates for vector i </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01512">IndexHNSW.cpp:1512</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW2Level_html"><div class="ttname"><a href="structfaiss_1_1IndexHNSW2Level.html">faiss::IndexHNSW2Level</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00310">IndexHNSW.h:310</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_a40bc6d2c67545f95e322c63d68a47140"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#a40bc6d2c67545f95e322c63d68a47140">faiss::IndexHNSW::train</a></div><div class="ttdeci">void train(idx_t n, const float *x) override</div><div class="ttdoc">Trains the storage if needed. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00978">IndexHNSW.cpp:978</a></div></div>
<div class="ttc" id="structfaiss_1_1Index_html_a2a002388d2c081c2dbab8508dcefe73d"><div class="ttname"><a href="structfaiss_1_1Index.html#a2a002388d2c081c2dbab8508dcefe73d">faiss::Index::d</a></div><div class="ttdeci">int d</div><div class="ttdoc">vector dimension </div><div class="ttdef"><b>Definition:</b> <a href="Index_8h_source.html#l00064">Index.h:64</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSWStats_html"><div class="ttname"><a href="structfaiss_1_1HNSWStats.html">faiss::HNSWStats</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00156">IndexHNSW.h:156</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a0b456c521194903b29ce7c157539d771"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a0b456c521194903b29ce7c157539d771">faiss::HNSW::offsets</a></div><div class="ttdeci">std::vector< size_t > offsets</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00081">IndexHNSW.h:81</a></div></div>
<div class="ttc" id="structfaiss_1_1VisitedTable_html"><div class="ttname"><a href="structfaiss_1_1VisitedTable.html">faiss::VisitedTable</a></div><div class="ttdoc">set implementation optimized for fast access. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00054">IndexHNSW.cpp:54</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_a04a761ce17d0f9040b3bc8a77bd627d9"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#a04a761ce17d0f9040b3bc8a77bd627d9">faiss::IndexHNSW::add</a></div><div class="ttdeci">void add(idx_t n, const float *x) override</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01031">IndexHNSW.cpp:1031</a></div></div>
<div class="ttc" id="structfaiss_1_1ReconstructFromNeighbors_html_a6cf260c530e273e4d676804ac71128f8"><div class="ttname"><a href="structfaiss_1_1ReconstructFromNeighbors.html#a6cf260c530e273e4d676804ac71128f8">faiss::ReconstructFromNeighbors::reconstruct</a></div><div class="ttdeci">void reconstruct(storage_idx_t i, float *x, float *tmp) const </div><div class="ttdoc">called by compute_distances </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01378">IndexHNSW.cpp:1378</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a6d1cb35c4220bf554af90133c71ae04f"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a6d1cb35c4220bf554af90133c71ae04f">faiss::HNSW::efSearch</a></div><div class="ttdeci">int efSearch</div><div class="ttdoc">expansion factor at search time </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00099">IndexHNSW.h:99</a></div></div>
<div class="ttc" id="structfaiss_1_1Index_html_a040c6aed1f224f3ea7bf58eebc0c31a4"><div class="ttname"><a href="structfaiss_1_1Index.html#a040c6aed1f224f3ea7bf58eebc0c31a4">faiss::Index::idx_t</a></div><div class="ttdeci">long idx_t</div><div class="ttdoc">all indices are this type </div><div class="ttdef"><b>Definition:</b> <a href="Index_8h_source.html#l00062">Index.h:62</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_1_1DistanceComputer_html_a4713167f99ec2de58afa2fd20a952e33"><div class="ttname"><a href="structfaiss_1_1HNSW_1_1DistanceComputer.html#a4713167f99ec2de58afa2fd20a952e33">faiss::HNSW::DistanceComputer::set_query</a></div><div class="ttdeci">virtual void set_query(const float *x)=0</div><div class="ttdoc">called before computing distances </div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_adbf81f0b21102b942182c904892e0858"><div class="ttname"><a href="structfaiss_1_1HNSW.html#adbf81f0b21102b942182c904892e0858">faiss::HNSW::check_relative_distance</a></div><div class="ttdeci">bool check_relative_distance</div><div class="ttdoc">during search: do we check whether the next best distance is good enough? </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00102">IndexHNSW.h:102</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a1fc852810a2497a8eb2c41635ec05520"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a1fc852810a2497a8eb2c41635ec05520">faiss::HNSW::HNSW</a></div><div class="ttdeci">HNSW(int M=32)</div><div class="ttdoc">only mandatory parameter: nb of neighbors </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00527">IndexHNSW.cpp:527</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a857bef0db2dc0000f312cc8a95f857b2"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a857bef0db2dc0000f312cc8a95f857b2">faiss::HNSW::upper_beam</a></div><div class="ttdeci">int upper_beam</div><div class="ttdoc">number of entry points in levels &gt; 0. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00105">IndexHNSW.h:105</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_afdb5a17487296267efaaa94e6a08996d"><div class="ttname"><a href="structfaiss_1_1HNSW.html#afdb5a17487296267efaaa94e6a08996d">faiss::HNSW::set_nb_neighbors</a></div><div class="ttdeci">void set_nb_neighbors(int level_no, int n)</div><div class="ttdoc">set nb of neighbors for this level (before adding anything) </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00503">IndexHNSW.cpp:503</a></div></div>
<div class="ttc" id="structfaiss_1_1ReconstructFromNeighbors_html_a88ca99742dccc52ebb3324b507b6c872"><div class="ttname"><a href="structfaiss_1_1ReconstructFromNeighbors.html#a88ca99742dccc52ebb3324b507b6c872">faiss::ReconstructFromNeighbors::estimate_code</a></div><div class="ttdeci">void estimate_code(const float *x, storage_idx_t i, uint8_t *code) const </div><div class="ttdoc">called by add_codes </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01531">IndexHNSW.cpp:1531</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html"><div class="ttname"><a href="structfaiss_1_1HNSW.html">faiss::HNSW</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00040">IndexHNSW.h:40</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a153fa41ad41a4905aa60683360a3cdf0"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a153fa41ad41a4905aa60683360a3cdf0">faiss::HNSW::idx_t</a></div><div class="ttdeci">faiss::Index::idx_t idx_t</div><div class="ttdoc">Faiss results are 64-bit. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00046">IndexHNSW.h:46</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSWPQ_html"><div class="ttname"><a href="structfaiss_1_1IndexHNSWPQ.html">faiss::IndexHNSWPQ</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00292">IndexHNSW.h:292</a></div></div>
<div class="ttc" id="structfaiss_1_1ReconstructFromNeighbors_html_a454b7a5f7437a257df7404f5778fc833"><div class="ttname"><a href="structfaiss_1_1ReconstructFromNeighbors.html#a454b7a5f7437a257df7404f5778fc833">faiss::ReconstructFromNeighbors::add_codes</a></div><div class="ttdeci">void add_codes(size_t n, const float *x)</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01572">IndexHNSW.cpp:1572</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html">faiss::IndexHNSW</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00215">IndexHNSW.h:215</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_aa6dfdaed7bc0ad895774315166fcb197"><div class="ttname"><a href="structfaiss_1_1HNSW.html#aa6dfdaed7bc0ad895774315166fcb197">faiss::HNSW::random_level</a></div><div class="ttdeci">int random_level()</div><div class="ttdoc">pick a random level for a new point </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00539">IndexHNSW.cpp:539</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_ae7d955690da5d6376c203e81e124ba94"><div class="ttname"><a href="structfaiss_1_1HNSW.html#ae7d955690da5d6376c203e81e124ba94">faiss::HNSW::set_default_probas</a></div><div class="ttdeci">void set_default_probas(int M, float levelMult)</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00553">IndexHNSW.cpp:553</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_ad4b9f97d42e2521e01f8b60012985396"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#ad4b9f97d42e2521e01f8b60012985396">faiss::IndexHNSW::reset</a></div><div class="ttdeci">void reset() override</div><div class="ttdoc">removes all elements from the database. </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01043">IndexHNSW.cpp:1043</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSWFlat_html"><div class="ttname"><a href="structfaiss_1_1IndexHNSWFlat.html">faiss::IndexHNSWFlat</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00283">IndexHNSW.h:283</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a330107a5801680609932849fc9404594"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a330107a5801680609932849fc9404594">faiss::HNSW::search</a></div><div class="ttdeci">void search(DistanceComputer &qdis, int k, idx_t *I, float *D, VisitedTable &vt) const </div><div class="ttdoc">search interface </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00711">IndexHNSW.cpp:711</a></div></div>
<div class="ttc" id="structfaiss_1_1Index_html"><div class="ttname"><a href="structfaiss_1_1Index.html">faiss::Index</a></div><div class="ttdef"><b>Definition:</b> <a href="Index_8h_source.html#l00060">Index.h:60</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_ab9c75063090927f8f65d1896b6949af4"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#ab9c75063090927f8f65d1896b6949af4">faiss::IndexHNSW::init_level_0_from_entry_points</a></div><div class="ttdeci">void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)</div><div class="ttdoc">alternative graph building </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01200">IndexHNSW.cpp:1200</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_ae0ddf6ab4a54239a25d6277e21e8548e"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#ae0ddf6ab4a54239a25d6277e21e8548e">faiss::IndexHNSW::search</a></div><div class="ttdeci">void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override</div><div class="ttdoc">entry point for search </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00985">IndexHNSW.cpp:985</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_a9a86c58212f3f9cf88394f5297cba525"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#a9a86c58212f3f9cf88394f5297cba525">faiss::IndexHNSW::init_level_0_from_knngraph</a></div><div class="ttdeci">void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)</div><div class="ttdoc">alternative graph building </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01162">IndexHNSW.cpp:1162</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_a5b619a41ddd52f0377efb701829c1e43"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#a5b619a41ddd52f0377efb701829c1e43">faiss::IndexHNSW::search_level_0</a></div><div class="ttdeci">void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe=1, int search_type=1) const </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01092">IndexHNSW.cpp:1092</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a26710980aaca3c1c8729e5e055a42ebe"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a26710980aaca3c1c8729e5e055a42ebe">faiss::HNSW::fill_with_random_links</a></div><div class="ttdeci">void fill_with_random_links(size_t n)</div><div class="ttdoc">add n random levels to table (for debugging...) </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l00913">IndexHNSW.cpp:913</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a27bd11ef9a651a94bcefa5291336fc58"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a27bd11ef9a651a94bcefa5291336fc58">faiss::HNSW::neighbors</a></div><div class="ttdeci">std::vector< storage_idx_t > neighbors</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00085">IndexHNSW.h:85</a></div></div>
<div class="ttc" id="structfaiss_1_1IndexHNSW_html_a660e5c8de1ba9c71bf3fe1f3bf0c8812"><div class="ttname"><a href="structfaiss_1_1IndexHNSW.html#a660e5c8de1ba9c71bf3fe1f3bf0c8812">faiss::IndexHNSW::reconstruct</a></div><div class="ttdeci">void reconstruct(idx_t key, float *recons) const override</div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8cpp_source.html#l01050">IndexHNSW.cpp:1050</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_aa7309dd7826761def38233c8bbbc0c63"><div class="ttname"><a href="structfaiss_1_1HNSW.html#aa7309dd7826761def38233c8bbbc0c63">faiss::HNSW::efConstruction</a></div><div class="ttdeci">int efConstruction</div><div class="ttdoc">expansion factor at construction time </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00096">IndexHNSW.h:96</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_ae1342fc2f07c325598a73b733e88ee74"><div class="ttname"><a href="structfaiss_1_1HNSW.html#ae1342fc2f07c325598a73b733e88ee74">faiss::HNSW::storage_idx_t</a></div><div class="ttdeci">int storage_idx_t</div><div class="ttdoc">internal storage of vectors (32 bits: this is expensive) </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00043">IndexHNSW.h:43</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_1_1DistanceComputer_html"><div class="ttname"><a href="structfaiss_1_1HNSW_1_1DistanceComputer.html">faiss::HNSW::DistanceComputer</a></div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00052">IndexHNSW.h:52</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_a44847954c98957404829182c7db1b8af"><div class="ttname"><a href="structfaiss_1_1HNSW.html#a44847954c98957404829182c7db1b8af">faiss::HNSW::levels</a></div><div class="ttdeci">std::vector< int > levels</div><div class="ttdoc">level of each vector (base level = 1), size = ntotal </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00077">IndexHNSW.h:77</a></div></div>
<div class="ttc" id="structfaiss_1_1HNSW_html_afba18a290f5f759a8a7a64ed35b950eb"><div class="ttname"><a href="structfaiss_1_1HNSW.html#afba18a290f5f759a8a7a64ed35b950eb">faiss::HNSW::max_level</a></div><div class="ttdeci">int max_level</div><div class="ttdoc">maximum level </div><div class="ttdef"><b>Definition:</b> <a href="IndexHNSW_8h_source.html#l00093">IndexHNSW.h:93</a></div></div>
</div><!-- fragment --></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by  <a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.5
</small></address>
</body>
</html>