kNN在高昏暗空间中具有动态插入

Question

我正在寻找一种方法来做快速最近邻居(希望是O(log n))的高维点(通常是~11-13维).我希望它在初始化结构后的插入过程中表现得最佳.KD树出现在我的脑海中,但是如果你不进行批量加载但是进行动态插入,则kd树不再平衡,并且afaik平衡是一项昂贵的操作.

所以,我想知道你喜欢哪种数据结构进行这种设置.您有高维度点,并且您想要插入并查询最近邻居.

Answer 1

维度的诅咒在这里受到阻碍.您可以考虑应用主成分分析(PCA)来降低维数,但据我所知,没有人对此有很好的答案.

我之前(在音频和视频指纹识别中)处理过这种类型的问题,有时最多有30个维度.分析通常显示某些维度不包含搜索的相关信息(实际上是模糊搜索,我的主要目标),所以我从用于访问数据的索引结构中省略了它们,但是将它们包含在逻辑中以确定来自搜索期间找到的候选人名单.这有效地将维度降低到易处理的水平.

我通过严格量化剩余维度来进一步简化了事情,使得整个多维空间被映射为32位整数.我使用它作为STL映射(红黑树)中的键,尽管我可以使用哈希表.我能够在大约一两分钟内动态地向这样的结构(基于RAM)添加数百万条记录,并且搜索平均花费大约一毫秒,尽管数据并非均匀分布.搜索需要仔细枚举映射到32位密钥的维度中的值,但是足够可靠,可以在商业产品中使用.如果我的消息来源正确的话,我相信它在iTunes Match中已经习惯了.:)

最重要的是,我建议你看看你的数据并做一些利用其中的功能的自定义,以便快速索引和搜索.找到变化最大且彼此最独立的维度.量化这些并将它们用作索引中的关键字.索引中的每个存储桶都包含共享该密钥的所有项目(可能会有多个).要查找最近的邻居,请查看"附近"键并在每个桶中查找附近的值.祝好运.

ps我写了一篇关于我的技术的论文,可以在这里找到.对于付费墙感到抱歉.也许你可以在其他地方找到免费副本.如果您对此有任何疑问,请与我们联系.

Answer 2

想到的另一个数据结构是封面树.与最初为回答范围查询而开发的KD树不同,此数据结构对于最近邻居查询是最佳的.它已被用于涉及计算所有数据点的k个最近邻居的n体问题.在密度估计方案(Parzen窗口)中也会出现这样的问题.我对您的具体问题了解不多,但我知道这个数据结构的在线版本.查看Alexander Gray的页面和此链接