<p>One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists. </p>

CC BY-SA 3.0
2011-07-08T04:54:11.910Z
2011-07-08T04:54:11.910Z
Suresh Venkat
<p>The attribute-value pairs are LARGE. this results in loads of overhead to see all partial matches. This is currently not feasible. We already use a form of inverted index.</p>

CC BY-SA 3.0
2011-07-28T07:24:01.600Z
Faisal is the engineer handling this large data set. Could you sketch your algorithm, if beyond a straightforward inverted index? Some questions I have:
1) Is it a "dynamic" structure, with runtime insertions and deletions or can you preconstruct ?
2) Are you looking for O(1) insertion, deletion, and query time or would something like a "log(n)" suffice? What kind of storage is feasible, in terms of "O"?
3) Would a randomized/amortized query time guarantee work, or do you want worst case guarantees?
4) When looking up literature, have you found anything that seems promising?
Amir
CC BY-SA 3.0
2011-08-05T09:41:21.103Z
1) Built once
2) Mostly interested in lookup. No runtime insertions. If insertions are needed, then its it re-compiled for fast lookup.
3)q
Faisal
CC BY-SA 3.0
2011-08-05T09:41:46.720Z
3) Query Time should be defined, log(n) is preferred.
Faisal
CC BY-SA 3.0
2011-08-05T09:42:36.220Z
4) Err could you guide me to relevant literature? Do not know how to search for this problem
Faisal
CC BY-SA 3.0
2011-07-27T14:42:20.530Z
2011-07-27T14:42:20.530Z
Faisal
<p>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$.</p>

<p>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$</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-06T16:05:57.593Z
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
CC BY-SA 3.0
2011-07-08T04:48:15.813Z
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
<ds.data-structures>
Maintaining multiple field dynamic values
Amir
# Maintaining multiple field dynamic values

(Asked by: username_0 on 2011-07-06)

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.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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).  

---

## 2 answers

### Answer by username_1 on 2011-07-08. Score: 5 | Accepted answer

One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists.


---

### Answer by username_2 on 2011-07-27. Score: 0

The attribute-value pairs are LARGE. this results in loads of overhead to see all partial matches. This is currently not feasible. We already use a form of inverted index.

> **Comments:**
> **username_0**: Faisal is the engineer handling this large data set. Could you sketch your algorithm, if beyond a straightforward inverted index? Some questions I have: 1) Is it a "dynamic" structure, with runtime insertions and deletions or can you preconstruct ? 2) Are you looking for O(1) insertion, deletion, and query time or would something like a "log(n)" suffice? What kind of storage is feasible, in terms of "O"? 3) Would a randomized/amortized query time guarantee work, or do you want worst case guarantees? 4) When looking up literature, have you found anything that seems promising?  
> **username_2**: 1) Built once 2) Mostly interested in lookup. No runtime insertions. If insertions are needed, then its it re-compiled for fast lookup. 3)q  
> **username_2**: 3) Query Time should be defined, log(n) is preferred.  
> **username_2**: 4) Err could you guide me to relevant literature? Do not know how to search for this problem  

---

