Существует ли вероятностная структура данных для хранения отношений?

Ответ 1

Это может быть не решение, которое вы искали, но вы могли бы использовать ElasticSearch фильтр условий и иметь один документ, подобный этому для каждого пользователя:

{
  "id": 12345,
  "topics": ["Apache", "GitHub", "Programming"]
}

Фильтры условий напрямую реагируют на запрос, "который подписывается пользователями по крайней мере на один из этих тем", и ES очень хорошо разбирается в том, как кэшировать и повторно использовать фильтры.

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

Изменить. Я реализовал поиск и сканирование/прокрутку API в Python и получил некоторые интересные результаты. Я выполнил запросы пользователей, которые подписываются на любые три из этих тем, с этими пользователями 20 м и набором данных подписки 200 м, и в целом сам поиск заканчивается через 4-8 миллисекунд. Запросы возвращают 350.000 - 750.000 пользователей.

Проблемы возникают из-за получения идентификаторов пользователей из ES, даже с помощью API сканирования/прокрутки. На Core i5 я, кажется, получаю только 8200 пользователей в секунду, поэтому он меньше 0,5 миллиона в минуту (с "_source": false). Сам запрос выглядит так:

{
  "filtered": {
    "filter": {
      "terms": {
        "topics": [ 123, 234, 345 ],
        "execution": "plain",
        "_cache": false
      }
    }
  }
}

В производстве я использовал бы "execution": "bool", чтобы частичные результаты запроса могли кэшироваться и повторно использоваться в других запросах. Я не знаю, что такое бутылочная горловина с получением результатов, загрузка центрального процессора на 50%, и я запускаю клиентский python script на том же компьютере, используя elasticsearch.helpers.scan.

Ответ 2

Что делать, если в каждой записи пользователя было поле BIT FIELD, представляющее все темы.

TABLE Пользователи (ID INT, UserName VARCHAR (16), Темы BINARY (8000))

Двоичный 8k позволит вам иметь 64000 тем. Я бы, вероятно, использовал несколько столбцов BINARY (1024) для каждого, поэтому я мог бы добавить еще несколько тем.

Теперь, когда приходит событие, помеченное тегами 1, 10, 20, 30, 40. Я должен искать каждого пользователя, но это может быть распараллелировано и всегда будет N сложностью, где N - количество пользователей.

SELECT ID 
FROM Users (READPAST)
WHERE 
    SUBSTRING(Topics, 1 / 8, 1) & (1 * POWER(2, (1 % 8))) > 0
    OR
    SUBSTRING(Topics, 10 / 8, 1) & (1 * POWER(2, (10 % 8))) > 0
    OR
    SUBSTRING(Topics, 20 / 8, 1) & (1 * POWER(2, (20 % 8))) > 0
    OR
    SUBSTRING(Topics, 30 / 8, 1) & (1 * POWER(2, (30 % 8))) > 0
    OR
    SUBSTRING(Topics, 40 / 8, 1) & (1 * POWER(2, (40 % 8))) > 0
OPTION (MAXDOP = 64)

• Нет дубликатов. Мы сканируем пользователей один раз, чтобы не беспокоиться о союзах.
• Некоторые пользователи пропускают подсказка READPAST пропускает любые строки, которые в настоящее время заблокированы (обновляется), поэтому некоторые пользователи могут отсутствовать в результате.
• SUbscribe Вы можете [un] подписаться на тему, просто переключив бит тем в столбце "Темы".

Ответ 3

Как я уже сказал в комментариях, точное решение на основе памяти, безусловно, возможно.

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

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

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

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

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

Также можно корректно выселить из представления BST с помощью дерева статистики заказов: сохранить количество потомков в каждом node, Тогда вы всегда можете найти n-й элемент в сортированном порядке ключей, где n является псевдослучайным и выселяет его.

Я знаю, что вы искали эффективность побитового пространства фильтра Bloom, но гарантировать отсутствие ложных срабатываний, похоже, не следует.

Ответ 4

[Это решение похоже на Louis Ricci, за исключением инвертированного в таблицу тем, что может сделать подписки более менее практичными, быть предупрежденными!]

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

Но, глядя на разреженность ваших данных, биты теряют пространство над целыми массивами. И даже с целыми массивами операция union по-прежнему довольно недорогая, учитывая, что у вас есть только 10 000 подписчиков на одну тему.

Так что, может быть, просто мертвая простая структура данных, учитывая ваш случай использования, просто:

Topic 1 => [array of subscriber IDs]
Topic 2 => [array of subscriber IDs]
...
Topic 20,000 => [array of subscriber IDs]

Сохранение (avg) 10 000 идентификаторов подписчиков (предполагая 32-разрядные целые числа) требует только 40 кбайт для каждой темы.

[В массиве или BLOB, в зависимости от вашей базы данных]

С 20 000 тем это добавляет только 800 мб данных в вашу таблицу тем... и очень мало этого (~ 200kb avg) необходимо загрузить в память при возникновении события уведомления!

Затем, когда происходит среднее событие (затрагивающее 5 тем), все, что должно произойти:

• Запрос/Вытяните данные для соответствующих тем (в среднем 5 записей) в память ( avg ~ 200kb ввода/вывода)

• Сбросьте их в структуру данных Set (удаляет дубликаты списка подписчиков)

• Оповещать подписчиков в наборе.