Сравнение времени поиска между деревом KD и грубой силой

Question

Это график скорости выполнения в соответствии с размером дерева k-d и грубой силой, который я написал.Количество наборов указателей было зафиксировано на уровне 1 М (1 000 000), и Query измерял скорость, выполненную 1000 раз.Увеличение k - d дерева огромно, но грубой силы нет.Интересно, почему появились эти результаты и как их можно улучшить.

Answer 1

Некоторые идеи:

• Производительность может сильно зависеть от характеристик данных.Например, равномерно ли распределены, сгруппированы или иным образом распределены точки данных?

• Кроме того, какой тип запроса вы выполняете?Одним из объяснений будет то, что вы используете оконный запрос, который возвращает весь набор точек или его большие части.В этом случае грубая сила всегда будет быстрее.

• Может быть, есть изъян в реализации KD-Tree?

Обычно это такИзвестно, что kD-деревья плохо масштабируются при высокой размерности.Так, например, в машинном обучении размерность часто уменьшается примерно до 10-20. Однако, если вы не используете грубую силу на GPU, KD-Tree должен работать быстрее.

Если вы ищете структурыкоторые лучше масштабируются при больших размерах (вставка / запрос окна), посмотрите на R * Trees или PH-Tree (последний является саморекламой и в настоящее время ограничен 60размеры, но версия с высокой яркостью будет выпущена на этой неделе).Для поиска k-ближайшего соседа посмотрите CoverTrees или BallTrees .Если вы используете Java, вы можете взглянуть на реализации в my repo .Я также реализовал R * Tree здесь .