Если я использую алгоритм DBSCAN с minPts, равным 1, он все еще будет работать за время O (nlogn)?

Question

Я делаю домашнюю задачу, которая упростила группировку звезд в созвездия с учетом их координат x, y и минимального расстояния. Любая звезда может быть созвездием сама по себе. так, например, 5 звезд не могут соединиться друг с другом, тогда будет получено 5 созвездий.

Я изначально создал алгоритм, который проверяет каждую точку с временем выполнения O (n ^ 2). Я хочу сделать это быстрее и увидел, что DBSCAN работает за O (nlogn) времени.

Мой вопрос заключается в том, что, если бы я использовал DBSCAN, алгоритм говорит, что он будет работать за O (nlogn) время, но если мои minPts равны 1 (размер моих кластеров), это сведет на нет эффективность DBSCAN. и беги в O (n ^ 2) ??

Answer 1

Время выполнения зависит от того, насколько epsilon достаточно мал, чтобы размеры результатов были небольшими, а также от индекса, способного ускорить эти запросы. Требования к minpts не предъявляются, поэтому он будет работать для «вырожденного» случая кластеризации с одной связью.

Но в вашем случае вы можете просто захотеть использовать пространственный индекс для поиска соседей напрямую, а не идтичерез прокси DBSCAN?

Answer 2

Насколько мне известно, время работы DBSCAN в этом случае зависит от расчета соседей, который выполняется в каждой точке на заданном расстоянии. Как вы упомянули, если вы выполните линейное сканирование, вы получите O (n ^ 2) всего. Тем не менее, чтобы ускорить поиск, вы можете использовать структуру на основе индекса, которая выполняет поиск за O (logn). Пожалуйста, проверьте пространственные базы данных .