I need a data structure that gives the best performance for multi-key range lookups. I do not need to update/insert/delete. This will be immutable. The use case is in-memory filtering of values over multiple dimensions. Research suggests k-d trees and BitMap indexes (specifically Roaring Bitmaps). It seems that k-d trees perform poorly. I am dealing with 1 to 6 dimensions for the key. I have not found a truly adequate solution. Ultimately I need to filter two different data sets, join them, and then reduce the values.
The closest analogy is a SQL inner join on multiple columns, multiplying the values from the two different tables, then summing the results. This is similar to Tensor Algebra with Tensor slicing. I have not found consensus on what the best data structure is for this.
Here is an example of what I would like to support using SQL to illustrate the operation. I am working in .NET. SQL is just to illustrate the problem.
Note: I am not looking for answers which are "Just use SQL". I don't need the overhead of a full RDBMS. I'm looking for the best data structure to support these use cases.
Let's say we have two tables:
Table1 has a an index on
IndexColumn and values in
Table2 is indexed by two different columns:
IndexColumn2. It has values in
ValueColumn2. I want a data structure which makes the following fast:
SELECT SUM(Table1.ValueColumn * Table2.ValueColumn2) FROM Table1 JOIN Table2 ON Table1.IndexColumn = Table2.IndexColumn1 WHERE Table1.IndexColumn < "Chicken" AND Table2.IndexColumn2 > 10
I am wanting to join these data sets on one of the index columns and perform range queries on the index columns as well. Right now I am doing this type of thing using a
Map<'Key,'Value> but I have to enumerate the keys to perform the filtering. This does not scale. It is straightforward to use a more efficient filtering if the index is one dimension. Use a sorted array and binary search to find the values of interest and then take subsets of the array.
I am having trouble scaling this up to higher dimensions. Ideally I could support up to 6 dimensions for the keys. There is only ever 1 value column. My research suggests a k-d tree but even that seems like it may not perform well.
I need to join and filter data sets quickly. The size of data fits in memory. Largest data set I am working with would be 1M rows.