Maintaining multiple field dynamic values

This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with multiple attributes. That is, there is a set of $k$ global properties, or key/value fields, where each node may maintain only a subset of them. E.g, $A$ is ($x=1$), $B$ is ($x=1$,$y=4$), $C$ is ($x=1$,$z=5$), where $x$, $y$, and $z$ are attributes. There should be no repetition of nodes, although one may be a subset of another in it's filled values. For example, here node $A$ is a subset of $B$.

The structure would initially be constructed from a large amount of nodes "on disk" (let us call this parameter $n$) in preprocessing and then would go in live query mode. Whenever a new query $Q$ comes in, the query $Q$ will also have between 1 to $k$ of the key/value pairs filled. The structure has to specify ALL matching nodes of the structure (e.g, $A(x=1)$, $B(y=4)$, $C(x=1,y=4)$ all would match $Q(x=1,y=4)$) and if $Q$ does not already exist in the structure, it has to be inserted. Given a query node, $Q$, a matching node $M$ is defined to be such that it's filled key-value pairs are a superset of those of $Q$

Which data structure would produce such a result in optimal insertion/lookup/deletion time, and of course, linear storage? Both amortized and worst case guarantees would be interesting, since this structure will handle a large number of queries. A link to relevant papers or literature would also help.

I thought about posting this on stackoverflow, but in this case the engineer is looking for a sound algorithm, not code, and preferably with theoretical performance guarantees. Apologies if it is fairly trivial for someone well-versed in data structures.

• it appears that if an entry does NOT contain a particular attribute, it can match any query that DOES contain that attribute (the record B in your example above).Is that correct ? I'm asking because that's slightly strange. – Suresh Venkat Jul 6 '11 at 16:05
• If Q is the query entry, all filled attributes of Q must be present in a node M returned by our search, i.e a subset relationship from Q to M is fine. So, for example, Q(x=1) would match M(x=1, y=4). The converse does not apply though: Q(x=1,y=4) as query node should not return a match M(x=1). – Amir Jul 8 '11 at 4:48