Efficient lookup when key is made of multiple elements and elements can be empty I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored key is the lookup value or it is a generalised version - index key has empties where lookup value has values. I think the formalisation would be "the lookup value logically subsumes the index-key". I also want the lookup function to return the most specific index-key, that is the key with the fewest empties.

For example, if the data is stored in a (&lt;key&gt;, &lt;value&gt;) tuple with the key being a tuple of the elements and ? representing the empty set/null value:

((1, ?, 6, 3), "hey")
((1, 5, 6, 3), "hi")
((2, ?, ?, ?), "hello")


So lookup((2, 4, 5, 6)) -&gt; "hello". And lookup((1, 5, 6, 3)) -&gt; "hi" because (1, 5, 6, 3) is more specific than (1, ?, 6, 3).

A simple solution is to store them as shown above and simply look through them. This would take $O(nm)$ where $n$ is the number of entries and $m$ is the number of elements in the key. Checking in most-to-least specific would mean a match could be returned immediately.

This there an approach that could improve this?

Thank you
This is the problem of building a data structure for storing rectangles in $m$-dimensional space, so you can answer stabbing queries efficiently.

For instance, if your keys have 4 elements, then we are in $m=4$ dimensions.  The key $(1,5,6,3)$ corresponds to a single point in 4-dimensional space.  The key $(1,?,6,3)$ corresponds to a line in 4-dimensional space.  The key $(2,?,?,?)$ corresponds to an (infinite) box in 4-dimensional space.

So, in general, each key can be thought of as an (axis-aligned) box in $m$-dimensional space.  A query is a point in $m$-dimensional space, and you want to find all boxes that contain that point.  That is sometimes known in the literature as a "stabbing query" (particularly when we're talking about intervals, i.e., $m=1$).

There are many data structures for this problem.  Take a look at R-trees, for example.  You can also look at $m$-dimensional segment trees.  It is known that you can build a $m$-dimensional segment tree in $O(n (\lg n)^m)$ time and $O(n (\lg n)^m)$ space; each lookup can be answered in $O(k + (\lg n)^m)$ time, where $k$ is the number of entries that match the query.  Thus, segment trees will likely be a good representation if the dimension $m$ is small.  (Optimizations: The exponent can be reduced slightly from $m$ to $m-1$.  There are also special algorithms that achieve even better performance in the case of $m=2$, $m=3$, or $m=4$.)

See also Data structure to hold list of rectangles?.