3

I've encountered a problem in a personal project that I think could be solved by a particular data structure but I'm not sure what. The problem is as follows:

Given a set of k-tuples, provide an efficient data structure that given a position, i, and a value, p, returns a list of tuples that contain value p at position i.

I know that I can do this in O(n) time by mapping a filter through the list (the filter returns true if p is at i in the given tuple). However I wonder if it can be done in < O(n)?

I also know that I could create k maps, one for each position, that maps a value at a position to the list of tuples containing that value at that position. However, this 1) takes up a lot of space (k^k?) and 2) if I update the set of tuples (adding a tuple, removing a tuple, updating a value within a tuple) many of the k maps may need to be updated.

Is there a compromise between these two solutions that are efficient in querying time and storage space?

  • I think this may strongly depend on what usages you want to support and which ones you want to optimize for/against. Is the search for "items with value X inside position N" much more frequent than "add/remove item"? – Darien May 3 '16 at 18:50
  • If possible, it'd be nice to know the solution in both cases (search being more frequent vs. add/remove and vice versa). – geofflittle May 3 '16 at 19:45
  • This is what Datascript essentially does. You can see how it's implemented here: github.com/tonsky/datascript – M-x May 3 '16 at 21:14
1

You might find some useful inspiration from relational-database indices, which seek to solve a similar problem of finding rows which have a certain value in a column.

However I wonder if it can be done in < O(n)?

I'd look at trees, either self-balancing search trees or (if you have a lot of data) B-trees. You can probably achieve O(n) storage and searching/changing at O(log(n)). However, whenever you add, remove, or alter a tuple, you'll need to update the trees corresponding to its columns so that searches are accurate.

If you really want to get fancy, your system could use different indexing strategies depending on the number of rows and the nature of the data being indexed.

  • 1
    For that matter, he should probably consider just using a relational database, instead of partially reinventing one. – Karl Bielefeldt May 3 '16 at 21:58

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.