Как найти клики / одинаковые комбинации в битовом массиве?

Рейтинг: 4Ответов: 1Опубликовано: 23.04.2015

В массив у каждого элемента u1..uN есть своя комбинация битовых свойств b1..bN.

Задача найти наиболее крупные группы с одинаковыми включенными битами. Например:

пример данных и искомых подгрупп

Зеленым отмечены «включённые» биты, и ниже – две найденные группы. Чем-то задача похожа на поиск клик в графе, но вроде бы, задача с графом сложнее. Первый найденный кластер: строки u1 и u2 обе содержат включенными биты 1,3,4,5. Второй кластер: строки 2,3,4 одинаково содержат включенными биты 2 и 4.

В моей задаче число строк измеряется миллионами, а свойств (бит) – сотнями. Поэтому надеюсь, что есть какое-то более эффективное решение, чем перебор всех возможных комбинаций.

Находить собираюсь наиболее крупные «компании», ограничив поиск неким порогом. Бизнес цель – анализ данных пользователей в соц. сетях для выявления значимых «общностей».

Подскажите, какая здесь математика поможет?

Связанный вопрос, задавал раньше.

Ответы

Ответов пока нет.