hgg

层次贪婪图

它是如何工作的

首先，这种数据结构是由Geordon Worley设计的，没有相应的论文。任何想要撰写关于这种数据结构论文的人都可以随时联系Geordon Worley。如果在论文中使用这里提到的想法，请引用此存储库和Rust CV项目。

这种数据结构基于最近邻搜索图层次结构的概念，这是在HNSW 论文中首先提出的。然而，该论文中用于插入和搜索图的许多算法都被放弃了，转而采用更多依赖于数据的方法。这种数据结构的设计旨在最大化数据依赖性。

在度量空间中，点的维度可能比空间本身的维度要低。例如，构成桌面表面的点存在于三维空间中，但它们本身是二维的。同样，如果你在地图的海岸线上画点，它被称为具有1到2之间的分形维度，因为它既不是线，也不是平面。当你有二维或三维数据时，存在已知的精确最近邻搜索结构，这些结构利用空间的维度。同样，存在降维技术，可以使你使用较低维度的数据结构来存储数据。与其试图为整个数据集推导出这种维度，HGG允许数据在自然形成不同尺度的结构，以促进基于其自身局部维度的基于贪婪搜索的高召回率，这意味着度量空间的不同区域和不同尺度可以考虑到它们的维度。它是通过函数optimize_layer_neighborhood来实现的。此函数接收一个邻域，并迭代邻域中的每个节点，从最近邻开始。它检查当前节点是否不是贪婪搜索路径上的局部最小值。如果是，算法将从这个节点添加边到其最近邻，直到满足所有邻居的条件。鉴于传入的最近邻数量足够大，这确保了在所有已知方向上，我们都有任何方向的贪婪搜索路径，并将图连接到满足这一贪婪标准的所需的最小最近邻数。

设置 insert_knn 参数可以调整这些连接的范围。如果 insert_knn 足够大，且数据集中没有可能存在点的凹凸外区域，那么在足够大的 insert_knn 的情况下，搜索应该是精确的。搜索集中的凹边缘会降低此算法的有效性，因此输入点覆盖潜在搜索候选人的表面边界非常重要，否则无法知道搜索图在底层度量空间中表示的体积有多大，算法总是可以找到绕凹区域的路。对于高维数据，精确搜索是非常不希望的。如果您在 Hamming 空间或具有少量固定位置的离散维度性工作，那么 T. Trzciński、V. Lepetit 和 P. Fua 的论文 "Binary Space 的厚边界及其对最近邻搜索的影响" 中提到了一个原因，其中点之间的等距边界非常大，以至于邻居的数量会爆炸性增长，甚至比其他空间中的高维性还要糟糕。其次，无论 Hamming 还是其他情况，维度诅咒 是一个众所周知的现象，它使得在更高维中进行精确搜索变得难以实现。简单来说，执行精确搜索所需的边数太大，无法使具有薄 Voronoi 边界的特定数据集高效，这种现象是由于上述现象引起的。因此，您可以使用 insert_knn 参数来控制您的图连接的紧密程度。默认参数设置为 64，这限制了每次插入（或刷新操作）可以添加的边的数量，但您可能需要根据您的数据集进行调整。如果设置得太高，且数据集较大，如果使用较慢的内存（如交换空间），可能会降低性能，因为会消耗更多内存。insert_knn 与插入速度成反比，因此如果您需要更快地插入，可以将其降低，可以通过在贪婪搜索中使用更多最近邻来延长查找时间，以在较低的速度下达到相同的召回率。

为了搜索图，仅使用贪婪搜索。保留一个迄今为止看到的最节点，如果节点比最差的节点好，则将其插入池中。然后它迭代最佳池以找到尚未搜索其邻居的节点。它总是从最好的节点开始，并消除从池中搜索的节点。在 1 nn 情况下，不需要池，它只是重复取当前节点的最佳邻居，直到达到最小值。所有邻居的键也存储在每个节点的单个内存地址中，该地址包含该节点的一切信息，这使得仅通过每个节点的单个随机查找和在贪婪搜索中搜索其邻居，就可以快速遍历贪婪搜索。

为了将图转换为“层次结构”，采用了一种简单的方法。当一个节点被插入时，从顶层开始，向下执行1nn贪婪搜索。它保留每个层次上找到的nn。然后，在每个插入的层次上执行knn搜索，以进一步精炼并找到最佳nn，并使用该knn搜索调用optimize_layer_neighborhood。当一个节点被插入到某个层次时，它会检查是否有至少一个邻居位于下一层（或更高）。如果没有邻居位于下一层，它会迭代到下一层，然后执行相同的knn搜索和优化。与HNSW不同，HNSW使用先验方法选择层次，不考虑数据依赖性，该算法创建了一个隐式多维跳表，其维度与局部区域中的底层数据大致成比例，并且更准确地分布跳表。例如，如果数据在空间中形成一个完美的直线，那么在所有层次上，最多每隔一个（1/2）和至少每隔三个（1/3）个节点都会存在下一层。这是因为当插入一个节点时，它要么被插入到同一层的两个节点之间，要么被插入到同一层的节点和更高层的节点之间。假设_表示较低/同一层的节点，而*表示上一层或更高层的节点。在前一种情况下，它将被提升到下一层，形成一个_-*-_模式，在后一种情况下，它不会提升到下一层，形成一个_-_-*模式。如果形成了一个_-_-*模式，该模式可能扩展为_-_-_-*，因此，可能不是每个节点在下一层都有一个物理邻居，但这不是一个重要的问题，因为更左侧的节点仍然连接到右侧的节点，并且将作为图邻居存在，直到图刷新。

echo ~/2011_09_29/2011_09_29_drive_0071_extract/image_*/data/* | xargs python generate.py akaze > akaze

source runrecall.sh

runrecall recall

recall,search_size,knn,num_queries,seconds_per_query,queries_per_second
1.0,1,1,32768,1.58e-7,6329113.924050633