1
$\begingroup$

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:

"MATCH (person)--[likes]-->(food)--[madeBy]-->(company),

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.

$\endgroup$
1
$\begingroup$

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.

A simple way to program this would be to insert your data into a database. Most databases will automatically build indices and update them as you change the data in the database. This will spare you having to implement that logic yourself.

$\endgroup$
  • $\begingroup$ This is a very good idea. Given that I already have a index sorted on the first dimension, what your proposal is essentially to build additional indexes for each additional dimension. Then, I can search using whichever dimension I want. The tradeoffs are that now I have n-indexes to maintain whenever the graph changes, and I have the requirement to store all these additional indexes, which are as large as the initial index I am building. This may be the best solution, and one I want to address, but I feel that there may be solutions like quadtrees or r-trees that better suit this problem. $\endgroup$ – Jonathan Sumrall May 4 '15 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.