Структура данных для эффективного извлечения ближайшего элемента из множества

tl;dr Как можно эффективно реализовать что-то вроде Nearest системы Mathematica?

В системе Mathematica есть функция Nearest которая принимает список "вещей" (это могут быть числа, координаты в n-мерном пространстве, строки и т.д.) и возвращает объект NearestFunction. Этот объект представляет собой функцию, которая, будучи примененной к x, вернет элемент списка, который ближе всего к x по некоторой метрике расстояния. Метрику расстояния можно передать в качестве параметра в Nearest: по умолчанию он использует евклидово расстояние для числовых данных и что-то вроде edit distance для строк.

Пример (надеюсь, это сделает вопрос более понятным):

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50] вернет 58, элемент, ближайший к 50. nf[50, 2] вернет {58, 39}, два ближайших элемента.

Вопрос: Каков эффективный способ реализации этой функции? Какого рода структуру данных NearestFunction, вероятно, будет использовать внутри? Какова наилучшая возможная сложность вычисления ближайшего элемента для различных типов данных?

Для простого списка чисел подойдет сортировка и двоичный поиск, но Nearest работает с многомерными данными, а также с произвольной функцией расстояния, поэтому я полагаю, что она использует что-то более общее. Но я не удивлюсь, если окажется, что он специализирован для определенных типов данных / функций расстояния.