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?