| Плотностный алгоритм кластеризации (DBScan)
|
| Последовательный алгоритм
|
| Последовательная сложность
|
[math]\displaystyle{ O(n \log n) }[/math]
|
| Объём входных данных
|
[math]\displaystyle{ - }[/math]
|
| Объём выходных данных
|
[math]\displaystyle{ - }[/math]
|
| Параллельный алгоритм
|
| Высота ярусно-параллельной формы
|
[math]\displaystyle{ - }[/math]
|
| Ширина ярусно-параллельной формы
|
[math]\displaystyle{ - }[/math]
|
Автор описания: Орпанен И.С.
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
ЧАСТЬ. Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
| Реализация
|
Технологии
|
Лицензия
|
Посдедовательная сложность
|
Структуры данных
|
Метрики
|
Параллельность
|
| Scikit learn
|
Python
|
BSD 3
|
[math]\displaystyle{ O(n \log n) }[/math]
|
k-d tree, ball tree
|
Любые
|
Есть
|
| alitouka/spark_dbscan
|
Scala, Spark
|
GPLv2
|
[math]\displaystyle{ O(n \log n) }[/math]
|
r-tree
|
Euclidean
|
Есть
|
| irvingc/dbscan-on-spark
|
Scala, Spark
|
GPLv2
|
[math]\displaystyle{ O(n \log n) }[/math]
|
r-tree
|
Euclidean
|
Есть
|
| propanoid/DBSCAN
|
C++, Boost, OpenMP
|
ABRMS
|
[math]\displaystyle{ O(n \log n) }[/math]
|
vantage-point tree
|
Euclidean
|
Есть
|
| CRAN
|
R, C++
|
GPLv3
|
[math]\displaystyle{ O(n \log n) }[/math]
|
k-d tree
|
Euclidean
|
Нет
|
| Weka
|
Java
|
GPLv3
|
[math]\displaystyle{ O(n^2) }[/math]
|
-
|
Euclidean, Manhattan
|
Нет
|
| Apache Commons
|
Java
|
Apache 2.0
|
[math]\displaystyle{ O(n^2) }[/math]
|
-
|
Euclidean
|
Нет
|
| choffstein/dbscan
|
Python
|
-
|
[math]\displaystyle{ O(n^2) }[/math]
|
-
|
Euclidean
|
Нет
|
Литература
