2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Jul 6, 2011 at 16:05
  • $\begingroup$ 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). $\endgroup$
    – Amir
    Jul 8, 2011 at 4:48

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Amir
    Jul 28, 2011 at 7:24
  • $\begingroup$ 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 $\endgroup$
    – Faisal
    Aug 5, 2011 at 9:41
  • $\begingroup$ 3) Query Time should be defined, log(n) is preferred. $\endgroup$
    – Faisal
    Aug 5, 2011 at 9:41
  • $\begingroup$ 4) Err could you guide me to relevant literature? Do not know how to search for this problem $\endgroup$
    – Faisal
    Aug 5, 2011 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.