Эффективное линейное сканирование 1 миллиона записей такого типа должно занимать долю секунды на современной машине; скомпилированный цикл должен иметь возможность делать это примерно с пропускной способностью памяти, что передало бы это за две или три миллисекунды.
Но, если вам действительно нужно оптимизировать это, вы можете создать хеш-таблицу из целочисленных значений, которая делит работу на количество целочисленных бинов. И, если данные хранятся отсортированными по числам с плавающей точкой, это улучшает местность сопоставления по ним; Вы знаете, что можете остановиться, когда выйдете за пределы терпимости. Сохранение смещений каждого из нескольких бинов даст вам возможность начать.
Полагаю, я пока не вижу необходимости в причудливом алгоритме ... опишите проблему немного подробнее, возможно (вы можете предположить довольно высокий уровень знаний по химии и физике, если хотите; я физик по обучению)?
Хорошо, учитывая дополнительную информацию, я все еще не вижу необходимости в чем-то лучше, чем прямой линейный поиск, если есть только 1 миллион опорных векторов и алгоритм такой простой. Я только что попробовал, и даже чистая реализация линейного сканирования на Python заняла всего около трех секунд. Потребовалось в несколько раз больше времени, чтобы составить несколько случайных данных для тестирования. Это в некоторой степени зависит от довольно сумасшедшего уровня оптимизации в библиотеке сортировки Python, но это преимущество языков высокого уровня.
from cmath import *
import random
r = [(random.uniform(0,20), random.randint(1,18)) for i in range(1000000)]
# this is a decorate-sort-undecorate pattern
# look for matches to (7,9)
# obviously, you can use whatever distance expression you want
zz=[(abs((7-x)+(9-y)),x,y) for x,y in r]
zz.sort()
# return the 50 best matches
[(x,y) for a,x,y in zz[:50]]