А>можно посмотреть в сторону метрических деревьев. гугли bk-tree, m-tree. критическим моментом при построении таких структур является выбор разбивающего элемента(-ов)

спасибо! хорошая идея с метрическими деревьями — к счастью, уже давно найдены алгоритмы даже в более общем виде для моей задачи