3D clustering Algorithm
Постановка задачи: У меня следующая проблема:
В трехмерном пространстве более миллиарда точек. Цель состоит в том, чтобы найти верхние N точек, которые имеют наибольшее число соседей в пределах заданного расстояния R. Другое условие состоит в том, что расстояние между любыми двумя точками этих верхних N точек должно быть больше R. Распределение этих точек не является равномерным. Очень часто некоторые области пространства содержат много точек.
Цель: Найти алгоритм, который хорошо масштабируется для многих процессоров и требует небольшого объема памяти.
Мысли: Нормального пространственного разложения недостаточно для такого рода проблем из-за неравномерного распределения. Неправильная пространственная декомпозиция, которая равномерно делит количество точек, может помочь нам решить проблему. Я буду очень признателен, если кто-то сможет пролить свет на то, как решить эту проблему.
1 ответ
У меня нет для вас однозначного ответа, но у меня есть предложение о подходе, который может привести к решению.
Думаю, стоит изучить хеширование с учетом локальности . Я думаю, что равномерное разделение точек и последующее применение этого типа LSH к каждому набору должно быть легко распараллеливаемым. Если вы спроектируете свой алгоритм хеширования так, что размер сегмента определяется в терминах R , кажется вероятным, что для данного набора точек, разделенных на сегменты, точки, удовлетворяющие вашим критериям, вероятно, будут существовать в самом полном объеме. ведра.
Выполнив это локально, возможно, вы сможете применить какую-то стратегию в стиле сокращения карты для пошагового объединения пространственных сегментов из разных параллельных прогонов алгоритма LSH, используя тот факт, что вы можете начать исключите части вашего проблемного пространства, исключив целые ведра. Очевидно, вам нужно быть осторожным с крайними случаями, которые охватывают разные сегменты, но я подозреваю, что на каждом этапе слияния вы можете применять разные размеры / смещения сегментов, чтобы удалить этот эффект (например, выполнить слияние пространственно эквивалентных сегментов, а также как соседние ведра). Я считаю, что этот метод можно использовать для сохранения небольших требований к памяти (т.е. вам не нужно хранить намного больше, чем сами точки в любой момент, и вы всегда работаете с небольшими (иш) подмножествами).
Если вы ищете какую-то эвристику, то я думаю, что этот результат немедленно приведет к чему-то, напоминающему «хорошее» решение, то есть даст вам небольшое количество вероятных точек, которые, как вы можете проверить, удовлетворяют вашим критериям.Если вы ищете точный ответ, вам придется применить некоторые другие методы, чтобы сократить пространство поиска, когда вы начнете объединять параллельные сегменты.
Другая мысль, которая у меня была, заключалась в том, что это могло быть связано с нахождением метрического k -центра . Это определенно не та же самая проблема, но, возможно, некоторые из методов, используемых при ее решении, применимы в этом случае. Проблема в том, что это предполагает, что у вас есть метрическое пространство , в котором возможно вычисление метрики расстояния - однако в вашем случае наличие миллиарда точек делает нежелательным и трудным выполнение любого вида глобального обхода (например, сортировка расстояний между точками). Как я уже сказал, просто мысль и, возможно, источник дальнейшего вдохновения.