1
$\begingroup$

I'm trying to figure out a more efficient solution to the following problem.

Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, and the keys are non-zero 16-bit unsigned integers.

Examples:
[(3, 100)]
[(1, 200), (1, 100), (2, 300)]
[(2, 200), (2, 300)]

Input: A fixed-length array of key-value pairs (J, U). The keys are non-zero 16-bit unsigned integers.

Example:
[(2, a), (1, b), (5, c), (1, d)]

The example is 4 elements, in the actual implementation it's always 8.

Expected Output: An array with length equal to one of the dataset arrays. The array elements are pairs of values from the dataset and input. I'm not sure how to express this in mathematical notation, so here's some pseudocode for a naive implementation:

for arr in dataset {
  let out_arr = []
  for (k, v) in arr {
    let result = null
    for (j, u) in input {
      if k == j {
        result = (j, u)
        break
      }
    }
    if result == null { break }
    input.remove((j, u))
    out_arr.push((v, u))
  }
  if out_arr.length == arr.length {
    return out_arr
  }
}
return null

This algorithm, when ran for the above dataset and input, would produce the following array: [(200, b), (100, d), (300, a)]

To attempt to state the algorithm in words: I need to see if there exists an array in the dataset for which every pair has a matching (by key) pair in the input. If there is such an array, I need to construct an output array of pairs of the values from each matching pair between the dataset and the input.

Caveat: The algorithm above is actually insufficient because if there are multiple valid outputs, one needs to be chosen at random, or at the very least in a way that prevents aliasing. In practice I'm doing this by shuffling the input array and using the solution below. This is also what makes it difficult to consider solutions that require sorting the input array.

The current working solution I have is to store a tree containing all possible continuation nodes given input in any order. Nodes which represent the completion of one of the dataset arrays also have the V values from the array in the order the array was traversed. For example the array [(1, 200), (1, 100), (2, 300)] may be represented by the tree in the following diagram (with the output values in red boxes):

enter image description here

In this case, I find the solution like this:

let node = root
for (u, j) in input {
  let next = tree.get(u)
  if next { node = next }
}
if node.output return node.output

The time taken to construct the data structure is not important, nor is maintenance cost or cost of any operation other than lookup, and generally there is plenty of space but I would like a structure that can be stored contiguously in memory.

Sorry if the way I've described the problem is confusing, I don't have the background in mathematics to know any of the terminology to help describe it. Please do ask for clarification in the comments.

$\endgroup$
4
  • $\begingroup$ I don't understand the definition of a "match" and a "full match". The condition looks rather complex. Can you specify it with mathematics? Can you give a more precise, systematic definition of "match" and "full match"? Trying to use only words (without any variable names, etc.) seems to make this challenging to follow. I don't understand what's happening in your example. $\endgroup$
    – D.W.
    Jan 13 at 22:37
  • $\begingroup$ @D.W. Thanks for the comment, I overhauled the question and added pseudocode in an attempt to clarify things. I'd be terribly lost trying to describe this in mathematical notation, so I haven't attempted it - apologies for that. I am very interested in making it possible for someone to answer this question so I'm willing to revise it much further or try to express it in mathematical notation if needed. $\endgroup$
    – Klaycon
    Jan 14 at 2:12
  • $\begingroup$ @Klaycon do you have any assumptions about the keys? $\endgroup$
    – Russel
    Jan 14 at 2:40
  • $\begingroup$ @Russel Sure, the keys are 16-bit unsigned non-zero integers. $\endgroup$
    – Klaycon
    Jan 14 at 2:43

1 Answer 1

1
$\begingroup$

If I understand correctly, we can reformulate your problem as following:

We have a database that contains a set of sets $S_1,\dots,S_n$. You are given an input set $I$. The goal is to determine whether there is any set in the database that is a subset of $I$: i.e., does there exist $i$ such that $A_i \subseteq I$?

Here I am treating each array as corresponding to the set of key values in the array. The above contains the core challenge of your problem. If such a set exists, and we can find which one it is (which is a "full match"), then we can easily derive the mapping to values and obtain the desired array of pairs.

So, you want to support subset queries. Unfortunately, this is a hard problem. You can take a look at the following questions to see if any of the methods mention there will be of use to you:

I don't know whether these will be useful to you in practice.

$\endgroup$
1
  • $\begingroup$ Thank you for interpreting my problem and giving me the terms to research it properly. I'll need to go over these questions and the linked papers again later, but from a cursory glance I can tell there's no easy solution here, and that my tree solution seems to be relatively sane, so that's good at least. $\endgroup$
    – Klaycon
    Jan 14 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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