Структура данных для кругов Эйлера?

Question

[uvelichitel]

Есть сущности, объединенные в множества тегами. Одна сущность может маркироваться несколькими тегами. Подскажите структуру данных позволяющую делать запросы Тег1+Тег2-Тег3 за константное время(возможно с out_of_process балансировкой структуры).
Если такая структура возможна, то ее ориентировочный memory_layout(на бумаге круги Эйлера выглядят привлекательно, но как их уложить в одномерную последовательную память/файл)
Профиль нагрузки - 1000 элементов, 100 тегов, чаще чтение чем запись.
Для key-value store например:

• структура данных - dictionary/associative_array
  
• memory layout - sparse_array
  

а для tags-values?

Comments

[Roman]

Делал я похожее на С++ STL
Исходник прототипа есть.
Со структурой все понятно, упрется все в алгоритмы
объединения/пересечения/разности множеств тегов в елементах.

Answer 1

[longclaps]

битовые поля

Answer 2

[Владимир Олохтонов]

Классический подход к решению этой задачи - булев индекс:
map[tag]set[id]

Comments

[uvelichitel]

Ага, идею кажется уловил. Посоветуйте что почитать или как погуглить. Вобщем, если не трудно, разверните ответ и я отмечу решением.

[Владимир Олохтонов]

uvelichitel, сходу вот эти лекции нагуглились: https://m.habr.com/company/mailru/blog/329072/#lek...
https://m.habr.com/company/mailru/blog/329072/#lek...

Возможно вам весь цикл про инфопоиск будет небесполезно изучить.