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

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

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

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

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

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

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

algo. BIRCH

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

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

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

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

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

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

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