Data structure to speed up the search for objects with tags in memory in a boolean tag function?

Question

If I have a set of tags (<100) and a set of objects (~ 25000), where each object has a certain subset of tags, do you know about the existing data structure that would allow for quick retrieval of those objects that satisfy some Boolean function of tags?

Adding / removing tags and objects should not be particularly fast, but the selection of these objects with tags that satisfy the logical function should be.

Now that I have written my question, it looks like I am describing a database in memory, but initially I was thinking of some kind of binary tree, such as a structure for objects, where for each branch, the right branch would be equivalent to the decision to have / have- not any tag. But would that not allow tags with idle attention? I ask how I was wondering if this had been done before, and it’s hard to find Google for data structures.

• Thanks in advance - Paddy.

Answer 1

Here is a suggestion: use a bit array for each tag, with as many elements as there are objects; each index of which represents one object. The value for each index is 1 if this object has this tag.

Boolean functions in tags are quickly defined operations on this bitmap. And the resulting bit array provides you with documents that meet the criteria.

This is not very effective if tags or objects change frequently, but may be applicable to you.

Answer 2

How fast will you need? How complicated is your boolean function, for example, how many tags are used in one typical function?

How to use some SQL database? You can then express the boolean function with a simple SELECT query.