Does a universal index exist?

Question

Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of methods for constructing an "index" structure so that the following operations can be performed on the table and index in $O(k\log N)$ time (relative to $N$ and $k$):

1. Insert a new element into the table.

2. Remove a specified element from the table.

3. Given a set of values of the fields, obtain the first record that is in the table with field values greater than the given field values, when the table is sorted into the lexicographic order with field 1 first, field 2 second, etc.

We wish to generalize this construction so that when operation 3 is done, any of the $k!$ orderings of the $k$ fields can be specified to determine the ordering of the records in the table.

Clearly, this can be done by constructing k! indexes, one for each ordering of the fields. Then the operations take $O(k!k\log N)$ time.

We want an algorithm whose operations are much faster (relative to $k$), preferably $O(k\log k \log N)$ time.

Does such an algorithm/data structure exist? It seems likely that if it existed, someone would have published and implemented it by now, but I've found no signs that one exists. Conversely, perhaps it can be proven that no such algorithm exists. But I've found no signs that such a proof exists.

Answer 1

One can show a lower bound for the data structure you are asking for under the Strong Exponential Time hypothesis. In particular, if all the entries have one bit, then one can use the data structure to do subset queries: i.e the data structure stores a family ${\cal F}$ of $N$ sets, each of size at most $k$. Then, the user may make "subset" queries - give a set $S$ and ask whether there is an $X \in {\cal F}$ such that $S \subseteq X$.

Such a query can be supported if we have a "universal index" - if we look for the lexicographically first entry coming after $S$, where we sort first by the columns where $S$ is $1$ and then along the ones where $S$ is $0$ then any element appearing after $S$ according to this order must be a superset of $S$.

Now, subset queries are equivalent to "dot product = 0" queries from this awesome answer by Ryan Williams - go read it. I will just summarize the effects of this answer on the universal index problem; assuming the Strong Exponential Time Hypothesis one can't support queries with running time $O(poly(k)N^{0.99})$, even if the family ${\cal F}$ is given in advance and we only have queries of type $3$ (i.e the data structure is static), and we have $poly(N,k)$ pre-processing time.