Алгоритм обучения с помощью к ближайших соседних точек является очень простым для реализации, требует весьма небольшой настройки и часто показывает достаточно приемлемую производительность. Вполне целесообразно, столкнувшись с новой задачей обучения, вначале попытаться воспользоваться этим алгоритмом. Но при наличии больших наборов данных требуется эффективный механизм поиска соседних точек, ближайших к точке запроса х, поскольку выполнение метода, в котором просто вычисляется расстояние до каждой точки, занимает слишком много времени. Было предложено много остроумных методов, позволяющих повысить эффективность этого этапа, которые основаны на предварительной обработке обучающих данных. Но, к сожалению, большинство из этих методов не достаточно хорошо масштабируются с увеличением количества размерностей пространства (т.е. количества характеристик).

При использовании многомерных пространств возникает еще одна проблема, связанная с тем, что ближайшие соседние точки в таких пространствах в действительности часто находятся очень далеко! Рассмотрим набор данных с размером N в d-мерном единичном гиперкубе и предположим, что нужно найти гиперкубическую окрестность с размером b и объемом(те же рассуждения относятся к гиперсферам, но формула объема гиперсферы является более сложной). Чтобы в нее вошло Сточек, средняя окрестность должна занимать долю k/N всего объема гиперкуба, который равен 1. Поэтому, или. До сих пор все шло хорошо.

А теперь допустим, что количество характеристик d равно 100, и предположим, что Нравно 10, а N равно 1 000 000. В таком случае получаем, что, т.е. что окрестность должна охватывать почти все пространство входных данных! Эти расчеты говорят о том, что методам с ближайшими соседними точками нельзя доверять, когда дело касается многомерных данных, а в случае малого количества размерностей не возникает никаких проблем; при d=2 получаем b=0.003.