<p>This is not exactly an answer of an efficient data structure, but rather an elaboration on the comments of @bbejot and @Kaveh giving a hand-waving argument for why given the current question we should not expect something that does a lot better than searching the whole database. The argument is based on a reduction from SAT, the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis">exponential time hypothesis</a>, and a lot of hand-waving.</p>

<p>Assume we have upto $n$ different tags, then we can think of each id as being associated with a bitvector $x$ of length $|x| = n$ where $x_j = 1$ if we have the $j$-th tag, and $x_j = 0$ otherwise. Since there is no real restrictions on what the database looks like, I can assume it has ids $1$ through $2^n$ with the $k$-th id having an associated tag vector of $k$ written in binary. The order fields can be arbitrary, since they only make the problem harder. Now, if we are given an arbitrary query of $AND$, $OR$, and $NOT$s then this is just asking a SAT question on $n$ variables. By the exponential time hypothesis, we can't expect this to be much faster than $2^n$... or in other words, we can't expect this to be much faster than searching the whole database.</p>

<p>We shouldn't expect efficient search in the length of the query (by reduction to SAT). We also shouldn't expect much better than looking at all the items in the database by the exponential time hypothesis.</p>

<p>To hope for an efficient data-structure for this question, we will have to make some serious assumptions on the structure of the database that are not made in this question. For instance, if we assume a special structure on the queries (such as CNF) then we can hope for something more efficient. An alternative assumption is on the structure of the database. We could probably assume that given $n$ tags, only a small fraction of the tags will be present on any given id (say a logarithmicly few $1$s). This is not an unreasonable assumption given the application of tagged questions (what use are tags if almost every single tag is used for a question).</p>

CC BY-SA 3.0
2011-05-07T04:39:17.800Z
Good observation. Each question has at most 5 tags, so a query about tags is equivalent to a 5-CNF.
Kaveh
CC BY-SA 3.0
2011-05-07T11:22:21.647Z
thank you! yes we can assume 5-CNF here further more, tagging behavior is not random. In general people will tag stuff with the most common tags, so that will allow for a few other shortcuts.
Sam Saffron
CC BY-SA 3.0
2011-05-28T12:15:14.170Z
@Kaveh, we ended up rolling an in memory structure. There are a few non-trivial shortcuts, sort is a bottleneck, using heap sort or a modified quick sort allows you to efficiently select top N without needing to perform a full sort. pre-calculating sorts allows you to pick pivots more efficiently and avoid sorts when a full scan is needed. multithreading speeds up selections. a lot of work can be deferred to the background before users interact with the structures. amazingly our in-memory structures are averaging 0ms for a search on the stack overflow data set.
Sam Saffron
CC BY-SA 3.0
2011-10-20T15:41:56.007Z
@SamSaffron - Where's the MSO post detailing this feature?  We've got a bug report [here](http://meta.stackexchange.com/q/109812/146495).
Kevin Vermeer
CC BY-SA 3.0
2011-05-06T14:56:12.937Z
2011-05-06T14:56:12.937Z
Artem Kaznatcheev
<p>This is a pretty straightforward answer, but I think effective:</p>

<p>A suggestive type for your datastructure: <code>Map Tag ([Id],[Id])</code> where the two lists of Ids are ordered by order1 and order2 respectively. Maintaining and generating this structure has a cost, but queries on a single tag should be $O(log (n))$ in the number of tags. Storing the length of the lists with the lists would help with query optimization, and much better than an actual list would be a lazy bitvector which would make negation extremely cheap as well.</p>

<p>If you thrown in another map of type <code>Map Id (Set Tag)</code> then generating the related frequencies given a list of <code>Id</code>s should be $O(n * log (m))$ in the size of the list and the size of the sets of tags.</p>

CC BY-SA 3.0
2011-05-07T10:51:07.870Z
I am tending to agree that some very simple structures like a map spooled multiple times may be the best way to go here. memory is cheap and maintaining multiple caches is not too hard
Sam Saffron
CC BY-SA 3.0
2011-05-06T20:22:04.623Z
2011-05-06T20:22:04.623Z
sclv
<p>I am looking for a highly efficient data structure for storage of data similar to the following.</p>

<pre>
Id    Tags   Order1 Order2 
--------------------------
1     1,2     1      1
2     2,5     2      3
3     1,7     4      7
4     6       3      0
</pre>

<p>I need to be able to query this structure in such a way that it would give me a list of all ids containing an expression of tags - supporting <code>AND</code> and <code>OR</code> and <code>NOT</code> operations. Eg. ((1 or 2) and not 7)</p>

<p>I also need to be able to specify the ordering of the results (Order1 or Order2) and be able to specify maximum rows returned with an optional offset. Performance for the fetch of the first 30-100 results is key. </p>

<p>Finally, I need a cheap way to lookup "tag relations" for example I want to know which tags "relate" to tags (1 OR 2) and in what frequency. Meaning which tags appear in the same set as 1 OR 2 ... ordered by frequency. </p>

<p>Any idea of what data structure (or set of structures) would be highly efficient for this kind of work?</p>

<p>(I would like to use this as a proof of concept for redesigning the <a href="https://cstheory.stackexchange.com/questions/tagged/cc.complexity-theory">tagged</a> pages of the SE family of sites) </p>

CC BY-SA 3.0
2011-05-05T10:29:47.257Z
Just a comment (perhaps trivial). Why don't you rely on a relational database management system? You can define a table with the <id,tag> pairs and add an index on the tag column. Then you can use standard SQL queries for extracting data. The RDBMS will efficiently do the "dirty" work of query optimization and output sorting.
Marzio De Biasi
CC BY-SA 3.0
2011-05-05T12:33:09.930Z
@Vor, the expressions are incredibly inefficient at high scale, the self joins become nightmarish queries.
Sam Saffron
CC BY-SA 3.0
2011-05-05T13:39:18.243Z
@Sam: ok. Your task is quite common so I thought that a good RDBMS (with a data mining tool) could do the job. I leave the floor to a data structure expert. :-)
Marzio De Biasi
CC BY-SA 3.0
2011-05-05T15:04:52.587Z
I believe allowing all combinations of AND, OR, NOT is going to make it difficult to create a data structure that doesn't list through all the items (perhaps it could be limited to 3-CNF?).  If no such limitation exists, then perhaps just run through the records (in the specified order) until you find 30-100 that pass your tag requirements.  Although, in general, I agree with Vor's suggestion of using a database to do the heavy lifting for you.
bbejot
CC BY-SA 3.0
2011-05-05T23:19:37.313Z
Not an expert, but I think if you don't put some restrictions on the way you can ask about tags then it is going to be difficult. Limiting them to CNFs (as bbejot suggested) is one way, another is restricting the number of different tags that query can ask about by a small number (say 6).
Kaveh
CC BY-SA 3.0
2011-05-05T23:35:25.687Z
@Kaveh very good point, the actual work people are doing is usually going to be a single tag lookup or a two tag intersect, I guess I could pre-spool a few caches. The 6 limit will be fine 99% of the time.
Sam Saffron
CC BY-SA 3.0
2011-05-05T23:46:22.280Z
FYI, this is the standard issue RDBMS have http://i.imgur.com/hym3p.png ... to figure out tag relations the algorithm is a very naive, scan + hash lookup. Which it horribly expensive. Similar issues exist around the expressions
Sam Saffron
CC BY-SA 3.0
2011-05-06T08:09:59.123Z
@Sam in the image of the query execution I don't see anything "horribly expensive": first there is an INDEX scan to retrieve Posts that contains TagId 1 then an INDEX seek to retrieve and group tags from those posts. SQL should do it efficiently (with [postid,tagid] as PK, and [tagid], [tagid,postid] as secondary indexes). If you need faster co-occurrence calculation, perhaps you could use another <tag1,tag2,count> table and mantain it while inserting/updating/deleting posts.
Marzio De Biasi
CC BY-SA 3.0
2011-05-06T08:59:21.360Z
@Vor that is possible, been thinking of ways to optimise this for common cases, one other idea I had was storing a bitmap of the most common N tags, that way I could pull any combination for the common tags in a single sweep.
Sam Saffron
CC BY-SA 3.0
2011-05-06T09:02:16.040Z
@Vor, further more if I ordered on bitmap you would be able to skip through the list really fast for aggregation type work.
Sam Saffron
CC BY-SA 3.0
2011-05-07T04:42:50.837Z
Here is some ideas: I guess that you don't need to compute the relations between tags all the time, maybe once in a week would suffice. Also ignoring very low frequency tags might improve things. Finally, I would guess that the relation between tags is homogeneous, so if you don't need exact numbers a randomly chosen sample of question might work as well. (It might also be interesting to try to understand the distribution of tags over time).
Kaveh
CC BY-SA 3.0
2011-05-07T10:52:04.063Z
@Kevah I like the idea of sampling and heavy caching
Sam Saffron
CC BY-SA 3.0
2015-08-10T16:19:23.993Z
http://stackoverflow.com/questions/12596045/algorithms-and-data-structures-for-tag-or-key-word-based-query-on-large-data-s
Ciro Santilli OurBigBook.com
<ds.data-structures><application-of-theory><db.databases>
Data structure that allow efficient tag based lookups
Sam Saffron
# Data structure that allow efficient tag based lookups

(Asked by: username_0 on 2011-05-05)

I am looking for a highly efficient data structure for storage of data similar to the following.

Id    Tags   Order1 Order2 
--------------------------
1     1,2     1      1
2     2,5     2      3
3     1,7     4      7
4     6       3      0

I need to be able to query this structure in such a way that it would give me a list of all ids containing an expression of tags - supporting AND and OR and NOT operations. Eg. ((1 or 2) and not 7)
I also need to be able to specify the ordering of the results (Order1 or Order2) and be able to specify maximum rows returned with an optional offset. Performance for the fetch of the first 30-100 results is key. 
Finally, I need a cheap way to lookup "tag relations" for example I want to know which tags "relate" to tags (1 OR 2) and in what frequency. Meaning which tags appear in the same set as 1 OR 2 ... ordered by frequency. 
Any idea of what data structure (or set of structures) would be highly efficient for this kind of work?
(I would like to use this as a proof of concept for redesigning the tagged pages of the SE family of sites)

**Tags:** ds.data-structures, application-of-theory, db.databases

> **Comments:**
> **username_1**: Just a comment (perhaps trivial). Why don't you rely on a relational database management system? You can define a table with the <id,tag> pairs and add an index on the tag column. Then you can use standard SQL queries for extracting data. The RDBMS will efficiently do the "dirty" work of query optimization and output sorting.  
> **username_0**: @Vor, the expressions are incredibly inefficient at high scale, the self joins become nightmarish queries.  
> **username_1**: @Sam: ok. Your task is quite common so I thought that a good RDBMS (with a data mining tool) could do the job. I leave the floor to a data structure expert. :-)  
> **username_2**: I believe allowing all combinations of AND, OR, NOT is going to make it difficult to create a data structure that doesn't list through all the items (perhaps it could be limited to 3-CNF?).  If no such limitation exists, then perhaps just run through the records (in the specified order) until you find 30-100 that pass your tag requirements.  Although, in general, I agree with Vor's suggestion of using a database to do the heavy lifting for you.  
> **username_3**: Not an expert, but I think if you don't put some restrictions on the way you can ask about tags then it is going to be difficult. Limiting them to CNFs (as username_2 suggested) is one way, another is restricting the number of different tags that query can ask about by a small number (say 6).  
> **username_0**: @username_3 very good point, the actual work people are doing is usually going to be a single tag lookup or a two tag intersect, I guess I could pre-spool a few caches. The 6 limit will be fine 99% of the time.  
> **username_0**: FYI, this is the standard issue RDBMS have http://i.imgur.com/hym3p.png ... to figure out tag relations the algorithm is a very naive, scan + hash lookup. Which it horribly expensive. Similar issues exist around the expressions  
> **username_1**: @Sam in the image of the query execution I don't see anything "horribly expensive": first there is an INDEX scan to retrieve Posts that contains TagId 1 then an INDEX seek to retrieve and group tags from those posts. SQL should do it efficiently (with [postid,tagid] as PK, and [tagid], [tagid,postid] as secondary indexes). If you need faster co-occurrence calculation, perhaps you could use another <tag1,tag2,count> table and mantain it while inserting/updating/deleting posts.  
> **username_0**: @Vor that is possible, been thinking of ways to optimise this for common cases, one other idea I had was storing a bitmap of the most common N tags, that way I could pull any combination for the common tags in a single sweep.  
> **username_0**: @Vor, further more if I ordered on bitmap you would be able to skip through the list really fast for aggregation type work.  
> **username_3**: Here is some ideas: I guess that you don't need to compute the relations between tags all the time, maybe once in a week would suffice. Also ignoring very low frequency tags might improve things. Finally, I would guess that the relation between tags is homogeneous, so if you don't need exact numbers a randomly chosen sample of question might work as well. (It might also be interesting to try to understand the distribution of tags over time).  
> **username_0**: @Kevah I like the idea of sampling and heavy caching  
> **username_4**: http://stackoverflow.com/questions/12596045/algorithms-and-data-structures-for-tag-or-key-word-based-query-on-large-data-s  

---

## 2 answers

### Answer by username_5 on 2011-05-06. Score: 6

This is not exactly an answer of an efficient data structure, but rather an elaboration on the comments of @username_2 and @username_3 giving a hand-waving argument for why given the current question we should not expect something that does a lot better than searching the whole database. The argument is based on a reduction from SAT, the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis), and a lot of hand-waving.

Assume we have upto $n$ different tags, then we can think of each id as being associated with a bitvector $x$ of length $|x| = n$ where $x\_j = 1$ if we have the $j$-th tag, and $x\_j = 0$ otherwise. Since there is no real restrictions on what the database looks like, I can assume it has ids $1$ through $2^n$ with the $k$-th id having an associated tag vector of $k$ written in binary. The order fields can be arbitrary, since they only make the problem harder. Now, if we are given an arbitrary query of $AND$, $OR$, and $NOT$s then this is just asking a SAT question on $n$ variables. By the exponential time hypothesis, we can't expect this to be much faster than $2^n$... or in other words, we can't expect this to be much faster than searching the whole database.

We shouldn't expect efficient search in the length of the query (by reduction to SAT). We also shouldn't expect much better than looking at all the items in the database by the exponential time hypothesis.

To hope for an efficient data-structure for this question, we will have to make some serious assumptions on the structure of the database that are not made in this question. For instance, if we assume a special structure on the queries (such as CNF) then we can hope for something more efficient. An alternative assumption is on the structure of the database. We could probably assume that given $n$ tags, only a small fraction of the tags will be present on any given id (say a logarithmicly few $1$s). This is not an unreasonable assumption given the application of tagged questions (what use are tags if almost every single tag is used for a question).

> **Comments:**
> **username_3**: Good observation. Each question has at most 5 tags, so a query about tags is equivalent to a 5-CNF.  
> **username_0**: thank you! yes we can assume 5-CNF here further more, tagging behavior is not random. In general people will tag stuff with the most common tags, so that will allow for a few other shortcuts.  
> **username_0**: @username_3, we ended up rolling an in memory structure. There are a few non-trivial shortcuts, sort is a bottleneck, using heap sort or a modified quick sort allows you to efficiently select top N without needing to perform a full sort. pre-calculating sorts allows you to pick pivots more efficiently and avoid sorts when a full scan is needed. multithreading speeds up selections. a lot of work can be deferred to the background before users interact with the structures. amazingly our in-memory structures are averaging 0ms for a search on the stack overflow data set.  
> **username_6**: @SamSaffron - Where's the MSO post detailing this feature?  We've got a bug report [here](http://meta.stackexchange.com/q/109812/146495).  

---

### Answer by username_7 on 2011-05-06. Score: 5

This is a pretty straightforward answer, but I think effective:

A suggestive type for your datastructure: `Map Tag ([Id],[Id])` where the two lists of Ids are ordered by order1 and order2 respectively. Maintaining and generating this structure has a cost, but queries on a single tag should be $O(log (n))$ in the number of tags. Storing the length of the lists with the lists would help with query optimization, and much better than an actual list would be a lazy bitvector which would make negation extremely cheap as well.

If you thrown in another map of type `Map Id (Set Tag)` then generating the related frequencies given a list of `Id`s should be $O(n \* log (m))$ in the size of the list and the size of the sets of tags.

> **Comments:**
> **username_0**: I am tending to agree that some very simple structures like a map spooled multiple times may be the best way to go here. memory is cheap and maintaining multiple caches is not too hard  

---

