Ellipsoid tree

Конечно, каждый из нас когда-либо озадачивался проблемой эффективного поиска в произвольном обобщённом метрическом пространстве! И внимание исследователей не могло не привлечь M-tree, которое можно частично реализовать в GiST. Но по-видимому M-tree не пригодно для поиска многомерных данных,
поскольку в том виде, в котором оно представлено автором, эта структура имеет существенный недостаток. А именно, если пытаться посдедовательно добавлять данные в M-tree, то дерево быстро деградирует, поскольку быстро растёт пересечение sibling узлов дерева. Разумеется, во всём виноваты волшебные пузырьки!
Дело в том, что узел дерева описывается точкой и радиусом, что является безобразным упрощением реальности. Как всегда бывает в таких случаях, приходит мысль всё усложнить.

Почему бы не использовать эллипсоиды вместо шаров?
Всё безобразие будем производить в терминах и правилах GiST. Возьмём две опорные точки и число r, равное максимальной сумме расстояний точки данного множества до опорных точек. Вот этими тремя объектами будем ограничивать узел дерева. Нужно решить, как разбивать множество точек, как искать ограничивающий "эллипсоид", как определить стратегию поиска. Алгортим Хачияна, скажете? Нет, мы будем честно погибать в обощённом пространстве, поэтому подходящих алгоритмов не знаю. Будем использовать очень простой приблизительный алгоритм.
Чтобы разбить множество на 2 подмножества, как это требуется в GiST, сделаем так:

def findTwoPivots(points, ntrials):
    p1 = points[0]
    p2 = p1
    for i in range(ntrials):
        t = max(points, key=lambda x: metricDistance(x, p1))
        p2 = p1
        p1 = t
    return p1, p2
def splitPoints(points, K):
    p1, p2 = findTwoPivots(points, K)
    left = []
    right = []
    for p in points:
        if metricDistance(p1, p) < metricDistance(p2, p):
            left.append(p)
        else:
            right.append(p)
    return p1, left, p2, right

(алгоритм в findTwoPivots содран из FastMap; вместо инициализации первой точкой в массиве, можно иницивлизировтаь случайной)
А примерно так мы построим "эллипсоид" по подмножеству, его дополнению и опорным точкам:

from random import sample
def buildEllipse(points, neighbours, K1, K2):
    def crossScore(a, b, candidates):
        d = max(metricDistance(a, x)
            + metricDistance(b, x) for x in candidates)        
        s = sum(metricDistance(a, x) + metricDistance(b, x) 
            for x incounterparts)        
        return s / len(counterparts) - d
    cnt1 = min(K1, len(points))
    cnt2 = min(K2, len(neighbours))
    candidates = sample(points, cnt1)
    counterparts = sample(neighbours, cnt2)
    bestPair = max(
        iterateAllPairs(candidates), 
            key = lambda x: crossScore(
                x[0], 
                x[1], 
                candidates))
    r = max(
        [metricDistance(pivots[0], x) 
            + metricDistance(pivots[1], x) for x in points])
    return Ellipsoid(bestPair, r)

Функция iterateAllPairs должна перечислять все сочетания по 2 элемента последовательности.
Еще должен быть в наличии метод, вычисления penalty для выбора лучшего узла при поиске и для вставки элемента в дерево.
Испытания GiST с таким расширением дало свои результаты. Несмотря на то, что посещение одного узла теперь обходится в два вычисления функции расстояния, в целом получается выйгрыш.