# Efficient data structure for multidimensional lookup

I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once.

It turns out that if a tuple is GOOD, then every strictly smaller tuple is BAD. ("A is smaller than B" means that "A[i] <= B[i] for every component i". "Strictly smaller" means that, additionally, "A[i] ≨ B[i] for at least one component i".)

I have a primitive subroutine which takes a tuple and returns a smaller GOOD tuple if one exists, or else null. I'm using this subroutine to help divide up the space into promising regions to check for GOOD points.

I feel like I need a data structure to keep track of known GOOD and BAD tuples, so that I don't re-explore the same regions. For example, you should be able to efficiently query "Is there a previously-seen GOOD point that is smaller than me?" or "Am I smaller than some previously-seen BAD point?"

If I were searching a one-dimensional space, I know I could do this with a tree. I'm not sure how to do this with a multi-dimensional space.

• "Am I smaller than some previously-seen BAD point?" -> Do you possibly mean "Am I smaller than some previously-seen GOOD point?" Commented May 19 at 19:59

Multidimensional lookup is hard, especially when the number of dimensions is large (say, larger than 10 or so). I don't know of any data structure that does what you want and is significantly more efficient than simple linear search (compare to each point in the data structure, one by one).

It seems that your problem could be expressed as "orthogonal range searching". This wiki page has a section with links to some algorithms, maybe one of them could work for you. https://en.wikipedia.org/wiki/Range_searching

Here is an idea:

Let us first define that a tuple $$A$$ dominates another tuple $$B$$ if, $$\forall i$$, $$A_i \le B_i$$. Now consider a DAG-like data structure where the tuples are represented as nodes, and there is an edge from tuple $$A$$ to tuple $$B$$ if $$A$$ dominates $$B$$. We canmaintain a list of all nodes having zero in-degrees (thus no one dominates them). Simply return this list as your required 'GOOD' tuples.

Insertion and deletion operations can easily be done on this DAG.

• "easily" - Unfortunately, this looks expensive. To add a tuple, you have to compare it to all other tuples, which the poster seems to be trying to avoid.
– D.W.
Commented May 16 at 23:29
• We may not need to compare them all for insertion. But yes, in the worst-case scenario, it is required. Commented May 17 at 8:10
• One thing we can do here is only maintain the GOOD list with us. Maybe that helps in most practical cases. But again, worst-case complexity remains the same. Commented May 17 at 8:13

I depends on what you mean by efficient and what your general dataset looks like.

A while ago it did a comparison of multiple multidimensional indexes, one scenario was datastructure with 1'000'000 entries (20-dimensional datapoints -> 20-tuples). Using Java implementations of various indexes, I achieved about 1'000'000 lookups per second, that was in 2017 on a reasonably modern desktop at the time, using Java 8.

The results are available here. "Lookup" is called "exact match query", see Fig.24 (evenly distributed data) and Fig. 26 (strongly clustered data).

For your case, window queries may also be important, e.g. to find all tuples that are strictly smaller than a given tuple. This is shown in Fig. 18 and 20. Some more details can be found at the beginning of the document.

In my tests the best indexes for insertion and lookup are KD-trees and PH-trees (disclaimer: PH-tree is my own project). Quadtrees were also good, but be warned that they may have excessive memory requirements when running with 18 dimensions.

Disclaimer: more self-advertisement: Java implementation of all indexes are available here and here. A C++ version of the PH-tree is available here. In this case, C++ is actually several times faster than C++.

-EDIT-

How does this help?

• The OP writes "list all of the GOOD tuples exactly once": finding duplicates can be done with an exact match query. I admit this part can also be done with a hashmap or similar.

• The OP also writes "Is there a previously-seen GOOD point that is smaller than me?": for strictly smaller tuples, this can be done with a simple window query.

• The OP writes "Am I smaller than some previously-seen BAD point?": This is a bit harder, I think it can be done with a custom window query implementation. I maybe able to help with that if there is enough interest?

• An exact match lookup lookup is not the same as checking whether there exists any point in the database that domains a query point. The question is asking about the latter type of query, not about exact match lookup queries. As such, I don't believe this answers the question.
– D.W.
Commented May 16 at 23:29
• The OP writes "list all of the GOOD tuples exactly once", I think finding duplicates can be done perfectly with an exact match query. The OP also writes "Is there a previously-seen GOOD point that is smaller than me?" which can be done with a window query. Commented May 17 at 11:46
• The hard point isn't avoiding duplicates. The hard part is checking whether a point is GOOD (whether it is dominated). Exact match lookup helps with avoiding duplicates, which are easy to avoid (e.g., just use any hashtable). Exact match lookup doesn't help with the hard part, avoiding quadratic runtime in the dominance checks.
– D.W.
Commented May 17 at 20:32
• Yes, I agree, that is almost exactly what I wrote 2 days ago (maybe I should have mentioned explicitly that I edited the answer). However I claim that using a spatial index and window queries, the runtime is less than quadratic. Commented May 19 at 20:02

If I understand your problem correctly, this problem is also known as Skyline query. Well, almost, I think in Skyline queries a point is GOOD if it is strictly smaller, but I think all traditional solutions apply if you invert your dataset.

There are many algorithms, see for example here.

• Yeah, it looks like the skyline query is another useful search term when trying to find the pareto frontier. Thanks! Commented May 23 at 19:26

IF the set of GOOD tuples is fixed and you only need to know if the new point would be classified as GOOD or BAD, then you could train a binary classifier(like a decision tree) to reach the binary decision efficiently.

IF your setting is dynamic (i.e., new tuples may be added and removed, and the set of GOOD points may change), then you have to keep a candidate set of GOOD points from the stream of points being inserted. As TilmannZ pointed out in his answer, this is a large area of research.