Лучший способ хранить пары с весами для 500 000 пользователей?

Question

Я создаю сайт, на котором хочу подбирать людей по общим интересам.Я делаю это, вычисляя вес между каждым пользователем и определяя, кто является лучшим - те, кто имеет большой вес:

Пример:

user 1 with user 2 = weight of 1
user 1 with user 3 = weight of 10
user 1 with user 4 = weight of 20

Я хочу поместить веса вDB.Проблема в том, что если у меня 500 000 пользователей, то это 500 000 x 500 000 возможных комбинаций или 125 000 000 000 записей - в базе данных mysql.Нереально вставить столько данных в одну из многих таблиц.

Мой вопрос: есть ли способ обработки такого количества пар с весами с использованием другого типа БД?Я читал о векторах и вещах, но не знаю достаточно, чтобы оценить это.

Я проверил документацию о:

• Базы данных NoSQL: MongoDB
• Объектные базы данных: (db4o, Versant)
• Базы данных графиков: neo4j, sones ...
• Широкий столбец: Hadoop, HBASE
• Хранение документов: CouchDB
• КлючХранилище значений: Redis, Voldemort
• Базы данных Grid: Gigaspaces ..
• Базы данных XML.

Но я не вижу решения.Кто-нибудь сталкивался с этой проблемой и может дать мне подсказку?

Answer 1

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

Кстати, пользователи обычно имеют фильтры.Эти фильтры могут автоматически игнорировать 95% вашей пользовательской базы.Вы можете использовать это в своих интересах.

Answer 2

Я собираюсь выйти на конечность и сказать, что нет хорошего решения поставленного вопроса.Похоже, нет способа избежать сохранения значений вес / пользователь 125B при заданном вопросе.

Просмотр другого типа БД не поможет.Вы просто не можете обойти тот факт, что у вас есть значения 125B, которые нужно сохранить.

Есть несколько способов обойти это

• Найти связь между пользователями и весами.Например, если вес всегда равен сумме двух идентификаторов пользователя (при условии, что у пользователя есть идентификатор), вам не нужно сохранять веса.
• Рассчитывайте на лету и не сохраняйте

Answer 3

Проблема не существует, на мой взгляд. Поскольку нереально, что один человек знает 500 тысяч человек. Может быть, одного человека знают 500 000 человек, но этот человек, вероятно, знает лишь малую часть из них лично, например Lady Gaga

Вероятно, реалистичное среднее значение составляет 300 для социальных сетей за всю жизнь. Таким образом, у вас "только" 150-200 миллионов отношений.

Я бы пошел с графиком дБ, так как с ними довольно легко смоделировать отношения.

Answer 4

Готовы ли вы создать решение с нуля?
Если вы готовы, возможно, вам следует создать 500000 файлов, по одному для каждого пользователя, и сохранить 500000 весов в каждом файле, отсортированном по идентификатору пользователя, с фиксированной длиной. Затем вы можете перейти в нужное место в нужном вам файле и прочитать значение, не используя разделители и не сохраняя идентификаторы пользователя. (Если ваши идентификаторы пользователей не являются числами от 1-500000, вам также потребуется сопоставление идентификатора пользователя с новым идентификатором от 1-500000, и вы должны отсортировать по этому идентификатору)

Какая гранулярность вам нужна на ваших весах?
Вы можете округлить каждый вес до ближайшего кратного n / (2 ^ k), который соответствует вашим потребностям. В случае 3 десятичных разрядов вы можете хранить каждое число как 10 бит с k = 10. Таким образом, каждый файл будет только 500000 * 10 бит = 625 КБ, а весь набор данных будет 312,5 ГБ. Вы даже можете сжать файлы и разархивировать их только при необходимости, в зависимости, конечно, от компромиссов между скоростью и пространством. Это решение также предполагает, что изменения вносятся редко, и вы получаете только одно значение за раз (или некоторый диапазон значений).

Answer 5

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

Если ваши данные меняются не часто и у вас есть несколько компьютеров для работы, то вы сможетевнедрите свою собственную простую стратегию разделения или используйте Gizzard для управления простым кластером с совместимым хранилищем данных ключ-значение на каждом компьютере.(Gizzard требует, чтобы все операции были коммутативными и идемпотентными.)

Answer 6

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

Кроме того, посмотрите, можете ли вы отказаться от топологии полностью связанных ячеек и принять что-то вроде разреженных кластеров или иерархии и т. Д. Если так, то каждому такому кластеру может быть присвоен идентификатор, и вы можете иметь весадля каждого пользователя с его / ее собственным кластером (степень принадлежности) и весами для соединения кластера с кластером.Вес для соединения пользователя-1 в кластере-1 с пользователем-2 в кластере-2 можно затем определить как функцию от весов между кластерами и «степени принадлежности» пользователей к их собственным кластерам.

Answer 7

Из вопроса кажется, что структура представляет собой сетку, где каждый пользователь подключен к другим (500K X (500k -1)).Звучит очень сложно.Делая некоторые эвристические предположения, оптимизации могут быть возможны.

Предположение Случай 1: Не каждая пара пользователей может иметь вес, это может привести к разреженной матрице.Так почему бы не хранить ненулевые веса в одиночку

Предположение Случай 2: У меня есть сильное ощущение, что диапазон весов может быть ограничен.Я не думаю, что было бы 500 000 различных весов, вероятно, 500 различных весов.Если это так, создайте 500 различных групп, в которых хранятся пользовательские пары.Не большая экономия места, но метод разделения.

Чтобы добиться экономии места в случае 2, исключите необходимость хранить пользователей в этих группах.Объедините характеристики, представляющие интерес (нижняя граница и верхняя граница).Чтобы получить совпадение для данного пользователя, выполните следующие действия:

1. Пройдите 500 групп нечетного веса и выберите наиболее подходящие нижнюю и верхнюю границы.Вы не будете знать точного пользователя, но теперь вы знаете, как он / она наносит на карту.
2. Поиск в таблице пользователей пользователей, попадающих в эти границы
3. Подробно проведите васанализ фактической группы пользователей, возвращенной на шаге 2.

Мои предположения могут быть неверными.Я в этом случае только что подстрелил приятеля.