8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, slam-dunk! Thanks! (I actually rest easier knowing this has an answer.) $\endgroup$ – Dale Jun 17 '17 at 12:35
0
$\begingroup$

EDIT: This solution does not work.

If we simply maintain a BBST (Balanced Binary Search Tree) for each field, with entries corresponding to values in each row of that field, the operations take the following amounts of time:

  1. Insert: $O(k \log N)$. Each BBST has N elements, so each insert is $O(log N)$, and there are $k$ BBSTs to insert into.
  2. Delete: $O(k \log N)$. Delete is also $O(\log N)$ on each BBST.
  3. Find lexicographic successor, with specified field ordering: $O(k \log N)$. Finding the first entry at or beyond a given value in a BBST is $O(\log N)$, and at worst we will need to perform this operation on all k BBSTs.

Thus, all of the operations can be performed in O(k \log n).

If you are looking for something more "index-y", such as with lower space overhead, this might not be the best solution, but it solves the question as asked.

$\endgroup$
  • $\begingroup$ It seems to me that strategy doesn't work, or at least, it's not obvious how to apply it. For instance, assume that the rows have first field values $1, 2, \ldots, N$, and that the second field values are some arbitrary permutation of $1, 2, \ldots, N$. If the current row is $(i, j)$, the first BSST can be used to find that the first field of the next row is $i+1$. But the second BSST doesn't tell us what the second field value is, because it could be anywhere from $1$ to $N$. What we would want is a BSST of the second-field values of all rows with first field value $> i$. $\endgroup$ – Dale Jul 3 '14 at 19:24
  • $\begingroup$ @Dale You're right - I'll think about it more. $\endgroup$ – isaacg Jul 3 '14 at 20:08

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.