What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?

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):

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.

• 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.
– D.W.
Jan 13, 2023 at 22:37
• @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. Jan 14, 2023 at 2:12
• @Klaycon do you have any assumptions about the keys? Jan 14, 2023 at 2:40
• @Russel Sure, the keys are 16-bit unsigned non-zero integers. Jan 14, 2023 at 2:43

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$$?