Existe um índice universal?

Dada uma tabela de dados contendo um número muito grande de linhas, com cada linha contendo um grande número de campos, e cada campo contendo um número grande mas fixo de bits, existem vários métodos para construir uma estrutura de "índice" que as seguintes operações podem ser executadas na tabela e indexar no tempo (relativo a e ):$N$$k$$O(k\log N)$$N$$k$

1. Inserir um novo elemento na tabela.

2. Remova um elemento especificado da tabela.

3. Dado um conjunto de valores dos campos, obtenha o primeiro registro que está na tabela com valores de campo maiores que os valores de campo especificados, quando a tabela é classificada na ordem lexicográfica com o campo 1 primeiro, o campo 2 segundo, etc.

Desejamos generalizar essa construção para que, quando a operação 3 for concluída, qualquer um dosas ordens dos campos podem ser especificadas para determinar a ordem dos registros na tabela.$k!$$k$

Claramente, isso pode ser feito através da construção de k! índices, um para cada ordem dos campos. Em seguida, as operações levam tempo .$O(k!k\log N)$

Queremos um algoritmo cujas operações sejam muito mais rápidas (em relação a ), preferencialmente em .$k$$O(k\log k \log N)$

Existe tal estrutura de algoritmo / dados? Parece provável que, se existisse, alguém teria publicado e implementado até agora, mas não encontrei sinais de que exista. Por outro lado, talvez seja possível provar que esse algoritmo não existe. Mas não encontrei sinais de que essa prova exista.

Pode-se mostrar um limite inferior para a estrutura de dados que você está solicitando sob a hipótese de Tempo Exponencial Forte. Em particular, se todas as entradas tiverem um bit, é possível usar a estrutura de dados para realizar consultas de subconjunto: ou seja, a estrutura de dados armazena uma família de conjuntos, cada um com tamanho máximo de . Em seguida, o usuário pode fazer consultas "subconjunto" - dar um conjunto e perguntar se existe um tal que .${\cal F}$$N$$k$$S$$X \in {\cal F}$$S \subseteq X$

Essa consulta pode ser suportada se tivermos um "índice universal" - se procurarmos a primeira entrada lexicograficamente após , onde classificamos primeiro pelas colunas onde é e depois pelas que é e qualquer elemento aparecendo após de acordo com este fim deve ser um subconjunto de .$S$$S$$1$$S$$0$$S$$S$

Agora, as consultas de subconjunto são equivalentes às consultas "dot product = 0" desta resposta incrível de Ryan Williams - leia-a. Apenas resumirei os efeitos dessa resposta no problema do índice universal; assumindo a hipótese de tempo exponencial forte, não é possível suportar consultas com tempo de execução , mesmo que a família seja fornecida com antecedência e só tenhamos consultas do tipo ( isto é, a estrutura de dados é estática) e temos tempo de pré-processamento .$O(poly(k)N^{0.99})$${\cal F}$$3$$poly(N,k)$