Алгоритм приближённого joinа на потоках данных Выполнил : Юра Землянский, 445 группа Научный руководитель : Б.А. Новиков СПб, 2011 Санкт-Петербургский. - презентация

1 Алгоритм приближённого joinа на потоках данных Выполнил : Юра Землянский, 445 группа Научный руководитель : Б.А. Новиков СПб, 2011 Санкт-Петербургский Государственный Университет Математико-механический факультет Кафедра системного программирования

2 Потоки данных Телекоммуникации и компьютерные сети – записи звонков – сетевой трафик – клики пользователей на страницах – логи Web-сервиса Бизнес – банковские транзакции – биржевые статистики Метеорологические данные

3 Потоки данных Memory vs Скорость vs Качество

4 Потоки данных Входные данные - набор точек в N-мерном пространстве. Данные поступают последовательно Размер входных данных заранее неизвестен и может быть произвольно большим.

5 Потоки данных Предоставляется один последовательный обход этим данных. Временная сложность - линейная Размер используемой памяти ограничен константой, не зависящей от размера входных данных

6 Similarity Join Нахождение пар близких объектов В нашем случае – для точек

7 Основная идея Сохранение точек в структуру, позволяющую значительно ускорять поиск пар для joinа Кластеризация : – Разбиение точек на группы близких В работе используем алгоритм для работы с потоками - BIRCH

8 algo. BIRCH

9 В вершине храниться информация о множестве точек P

10 algo. BIRCH Объём памяти, занимаемой деревом ограничен Радиус листовых множеств ограничен

11 algo. BIRCH-JOIN Листовые вершины хранят сами точки множества При превышении допустимого объёма памяти – часть дерева удаляется

12 algo. BIRCH-JOIN Поддержка модифицированного Cluster- Feature дерева. Поиск пары для точки – Рекурсивный обход дерева – В вершине проверяется – пересекается ли круг (центр – искомая точка, радиус – пороговое значение для joinа) с кругом (центр – центр масс вершины)

13 algo. BIRCH-JOIN Параметры для настройки – Стратегии удаления вершин – Условие для запуска рекурсивной процедуры от вершины – Размер используемой памяти – Степень ветвления – Максимальный радиус листьев

14 algo. BIRCH-JOIN Линейная сложность алгоритма Объём используемой памяти ограничен

15 Заключение Исходный код выложен на Google Code : – Всем спасибо!