Limites Superiores para a Complexidade de Índices Aprendidos Assintoticamente Ótimos

Índices aprendidos aproveitam modelos de aprendizado de máquina para acelerarem a resposta a consultas em bancos de dados, mostrando um desempenho prático impressionante. No entanto, a compreensão teórica desses métodos permanece incompleta. Pesquisas existentes sugerem que os índices aprendidos têm uma complexidade assintótica superior em comparação com seus homólogos não aprendidos, mas essas descobertas foram estabelecidas sob pressupostos probabilísticos restritivos. Especificamente, para um array ordenado com n elementos, foi demonstrado que os índices aprendidos podem encontrar uma chave em O ( (n) ) de tempo esperado usando no máximo espaço linear, em comparação com O (n) para métodos não aprendidos. Neste trabalho, provamos que um tempo esperado de O (1) pode ser alcançado com no máximo espaço linear, estabelecendo assim o limite superior mais apertado até agora para a complexidade de tempo de um índice aprendido assintoticamente ótimo. Notavelmente, usamos pressupostos probabilísticos mais fracos do que trabalhos anteriores, o que significa que nossos resultados generalizam esforços anteriores. Além disso, introduzimos uma nova medida de complexidade estatística para dados. Essa métrica exibe uma interpretação teórica da informação e pode ser estimada na prática. Essa caracterização fornece uma compreensão teórica adicional dos índices aprendidos, ajudando a explicar por que alguns conjuntos de dados parecem ser particularmente desafiadores para esses métodos.