У меня нет определенного ответа для вас, но у меня есть предложение о подходе, который может привести к решению.
Я думаю, что стоит изучить хеширование с учетом локальных особенностей .Я думаю, что разделение точек равномерно и затем применение этого вида LSH к каждому набору должно быть легко распараллеливаемым.Если вы спроектируете свой алгоритм хеширования так, чтобы размер сегмента определялся в терминах R, представляется вероятным, что для данного набора точек, разделенных на сегменты, точки, удовлетворяющие вашим критериям, вероятно, будут присутствовать в наиболее полных сегментах.
Выполнив это локально, возможно, вы сможете применить некоторую стратегию в стиле уменьшения карты, чтобы пошагово комбинировать пространственные сегменты из разных параллельных прогонов алгоритма LSH, используя тот факт, что вы можете начатьчтобы исключить части вашего проблемного пространства путем дисконтирования целых сегментов.Очевидно, вы должны быть осторожны с краевыми случаями, которые охватывают разные сегменты, но я подозреваю, что на каждом этапе объединения вы можете применять разные размеры / смещения сегментов, чтобы убрать этот эффект (например, выполнить слияние пространственно эквивалентных сегментов).как соседние ведра).Я полагаю, что этот метод можно использовать для поддержания небольших требований к памяти (т. Е. Вам не нужно хранить гораздо больше, чем сами точки в любой момент, и вы всегда работаете с небольшими (ish) подмножествами).
Если вы ищете какую-то эвристику, то я думаю, что этот результат немедленно приведет к чему-то, напоминающему «хорошее» решение, то есть даст вам небольшое количество вероятных точек, которые вы можете проверить, удовлетворяя вашим критериям.Если вы ищете точный ответ, то вам придется применить некоторые другие методы, чтобы урезать пространство поиска, когда вы начинаете объединять параллельные сегменты.
Еще одна мысль, которая у меня была, заключалась в том, что это может относиться к нахождению метрики k -центр .Это определенно не та же самая проблема, но, возможно, некоторые из методов, используемых в решении, которые применимы в этом случае.Проблема в том, что это предполагает, что у вас есть метрическое пространство , в котором возможно вычисление метрики расстояния - однако в вашем случае наличие миллиарда точек делает нежелательным и трудным выполнение любого вида глобального обхода(например, сортировка расстояний между точками).Как я уже сказал, только мысль и, возможно, источник дальнейшего вдохновения.