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?
Efficient Value-Lookup in List of k-Tuples
algorithms;data structures;search;indexing;query