Оптимальный способ найти элементы из одной коллекции не в другом

Question

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

Вот несколько идей, у меня есть:

1. Использование присоединяется к реляционной базе данных, чтобы решить эту проблему. Мой единственный запрос заключается в том, что этот дескриптор действительно большой набор данных.
2. Используйте цветной фильтр, чтобы сохранить список собранных элементов, а при запросе элементов проверьте, нет ли в фильтре.

Если вышеуказанная мысль не будет масштабироваться, вы можете предоставить мне алгоритмы, которые будут. Они не могут быть решениями в памяти, поскольку я определенно должен будет сохранять данные.

Answer 1

Вы также можете использовать биты.

Load into some bitset ItemList (ItemID is index in the bitset). 
Load into another bitset IDs_for_user for this user. 
Perform opearation: Resut = ItemList ANDNOT IDs_for_user. 

Бесплатная библиотека BitSet вы можете получить здесь: http://bmagic.sourceforge.net/