Partial match retrieval in implicit data structures (Q800083)

We consider partial match retrieval in implicit data structures. Consider a set of n records of k attributes each. This set is to be stored in an n by k array such that partial match retrieval can be done efficiently. A partial match query specifies a subset of the attributes, say s attributes, and asks for all tuples in the set agreeing with the query in the set of specified attributes. The complexity of this problem is studied in the paper and matching upper and lower bounds are shown. The model of computation is the comparison model.