TITLE: Data structure that allow efficient tag based lookups
QUESTION [12 upvotes]: 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)

REPLY [5 votes]: 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 Ids should be $O(n * log (m))$ in the size of the list and the size of the sets of tags.
{"set_name": "stack_exchange", "score": 12, "question_id": 6405}