Hashing tag list to perform faster search

Question

I have a list of items. Each item have various properties. Each item can be tagged, like tagging a post here. Right now, tags are represented using a Tags property, that is a string and it looks like tag1:tag2:...:tagN.

A user can search for an item based on its tags (i.e. get me items that has tag2 and tagN). To do this I need to scan the full items list and, even worst I need to split the Tags property and search if those tags are present.

What I'm searching for is a sort of hashing filter or a better algorithm to perform this type of search. Note that, if searching for tag2 would mean give me items with just tag2 the search would be simpler, alas what this really means is give me items that contains tag2, so splitting (at least, for now) is mandatory.

We would change the representation from tag1:tag2:...:tagN to a better one, in order to provide a faster search. Possibly without a lookup structure or something like that.

Answer 1

Having Tags as string forces you to parse it ever and ever again for every Item and for every search. If the tags do not appear in a predefined order, you'd also need to traverse it several times.

Improvements at item level

Improvement 1: make Tags an ordered list of strings. If you search for several tags then order them as well. You'd then traverse the Tags searching for the first tag. If it is found you can continue with the second tag (starting at the next item).

Improvement 2: make Tags a set of strings. Then it's even more efficient because your language/library will make use of an efficient access to elements, certainly in O(log n). Most languages even offer some kind of hash sets that allow an O(1) access (e.g. C++ std::unordered_set, java HashSet or C# HashSet).

Improvement 3: instead of hashing the same search tag strings for every single item, manage tags as an integer key, using a dictionary to map the tag strings to the tag keys. So Tags would end up as set of Tag

Improvements at collection level:

Until now, we just improved the performance of searching tags in an item. However, all these solutions still did require that every single item is searched.

Improvement 4: Make Tag and Item be related entities that impelment bidirectional navigability. So Item would still have a set of tags, but each Tag would have a collection of Item. This significantly prunes the search space: order the tag list from the one with the smallest collection of items to the larges. Look for the items in the collection of the first one. Then go through the items found to look if they match the others.

Improvement 5: You could as well make intersections between several collections (especially if they are ordered). However, if you have very large lists of items.

If you have huge collections

The approach proposed work all very well, but were more conceived for in-memory processing. If you have huge number of items and tag, you may need a db.

If you use a relational DB, the relation between tags and items (many to many association) will be a table of its own. The good news is that the db engine will optimize these kind of searches using similar strategies and even more elaborate ones, so that it will be ultra-efficient.