Может ли поиск ANN превосходить точность поиска NN в больших базах данных с многомерными представлениями?
Известно, что поиск ANN превосходит поиск NN с точки зрения эффективности, а некоторые методы сокращают объем памяти из компактных представлений. Но что происходит с точки зрения эффективности? Можно ли добиться такой же производительности, не найдя ближайшего соседа с помощью исчерпывающего поиска?
2 ответа
Если под эффективностью вы подразумеваете точность (то есть нахождение точного ближайшего соседа), то нет. Поиск NN всегда найдет точное NN, в то время как поиск ANN, в лучшем случае, найдет точное NN, что соответствует результату поиска NN.
Однако в многомерном пространстве проклятие размерности скрывается и обычные структуры данных и алгоритмы для 2D и 3D имеют тенденцию быть такими же медленными, как поиск методом грубой силы, поэтому поиск ANN - это путь, когда вы (большие) данные жить в многомерном пространстве.
Я пробовал бинарный поиск и поиск по базе данных ip2location. Он имеет такую же скорость, но с множеством оптимизаций. Вы можете найти исходный код на https://ip2locationphp.codeplex.com/.