Как эффективно хранить «связность» между пользователями?
Приветствую!
Имеется алгоритм, вычисляющий показатель (число), характеризующий отношение пользователя А к пользователю В.
Алгоритм транзитивный, симметричный, т.е. A->B = B->A.
С ростом числа пользователей потребуется хранить результаты и пересчитывать их (например, при изменении некоторых параметров пользователя A нужно пересчитать его отношение ко всем остальным).
Встает вопрос, как эффективно хранить, быстро обновлять и считывать такие данные? SQL, NoSQL? Какой движок/база подойдет лучше? Ведь всего на 1000 пользователей будет уже 1 000 000 записей.
Еще, я так понимаю, для пары пользователей считается некоторое число d(A, B). Оно является метрикой? d(A, B) + d(B, C) >= d(A, C), d(A, A) = 0? И какие оно принимает значения?
Транзитивность в моем понимании означает
A->B + B->C = A->C
Среди тысячи пользователей вряд ли все связны.
В таких посылках речь идет о связности графа. Иерархические структуры данных(дерево, граф) инородны для реляционной алгебры SQL. Известные решения Adjacency list и Nested sets. Adjacency list требует применения WITH RECURSIVE. Nested sets предполагает очень много пересчета при операциях(особенно INSERT).
Нужную вам модель данных было бы удобней реализовать в hierarchical DB (например просто hierarchical key value, Redis или levelDB сойдет) или graph DB или документарной DB (например просто в XML который в сути своей иерархичен)
Если алгоритм задает метрику, и готовы пожертвовать точностью, можно всех пользователей отобразить в O(log n)-мерное пространство. В худшем случае расстояния испортятся в O(log n), но при этом можно хранить всего O(n log n) бит информации.
Вам точно нужно хранить эту циферку таки для всех? Если только для тех, у кого она меньше/болше некоего порога - то это O(N) или O(NlogN), что уже влезет в обычный SQL, а не O(N^2), что действительно плохо.
Средний
Простой
Средний
