# An n-dimensional index where the search key specifies an exact match on certain dimensions?

I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value for that dimension. The value n, the number of dimensions, will be 4 or 5 in most cases.

For example, if I have a vector (1, 5, 9, 3, 7), I would want to be able to find such a vector by searching in the index with a search key specified as (*, *, 9, *, *), where * is a wildcard, and finding that vector and all other vectors with the value 9 in the 3rd position.

The reason for doing this is that I am building a path index for a graph database, where I precompute a large number of paths in a graph of length 4 or 5. These paths I store as vectors, where the first index in the vector specifies which path this is, and the remaining items specify the id of the nodes along that path. You can you use this to quickly answer graph queries such as:

RETURN person, food, company".

You determine what ID you assigned the [likes],[madeBy] path, search in the B+tree for this ID, and now you have all the nodes on that path.

However, if you delete a specific food node from the graph, finding the relevant nodes in the B+Tree is not possible, since you don't know which paths it could be in. Therefore, finding it is O(n) in the index. You can also look at that node in the graph and compute all the paths it is in, which is another option I am looking in to, but it would be nice if there was a way to do this in the index itself. Such as, if you deleted a node with ID 5, for a 5-dimensional index you could perform deletions: (*, 5, *, *, * ), (*, *, 5, *, * ), (*, *, *, 5, * ), (*, *, *, *, 5).

I appreciate any insight anyone has. Multi-dimensional indexing is new to me, and I have limited time to complete the project.

If you only want to be able to search on a single dimension at a time (as in your example), this is readily solved by precomputing an index. Basically, you scan the entire database and build up an index for each dimension. For instance, an index for the first dimension is a hashtable that maps from the value of $x_1$ to the tuple $(x_1,\dots,x_n)$, for each tuple. You then build an index for the second dimension, for the third dimension, etc. You do this once, in advance. Once you have the index, it's easy to answer queries. Also, it's easy to update the index when you insert or delete vectors.