A RLR-Tree: Uma Árvore R Baseada em Aprendizado por Reforço para Dados Espaciais

Índices aprendidos foram propostos para substituir estruturas de índice clássicas como a Árvore B por modelos de aprendizado de máquina (ML). Eles requerem a substituição tanto dos índices quanto dos algoritmos de processamento de consultas atualmente implementados pelos bancos de dados, e tal mudança radical provavelmente encontrará desafios e obstáculos. Em contraste, propomos uma maneira fundamentalmente diferente de usar técnicas de ML para construir uma melhor Árvore R sem a necessidade de alterar a estrutura ou os algoritmos de processamento de consultas da Árvore R tradicional. Especificamente, desenvolvemos modelos baseados em aprendizado por reforço (RL) para decidir como escolher um subárvore para inserção e como dividir um nó ao construir e atualizar uma Árvore R, em vez de depender de regras heurísticas elaboradas manualmente atualmente utilizadas pela Árvore R e suas variantes. Experimentos em conjuntos de dados reais e sintéticos com mais de 100 milhões de objetos espaciais mostram que nosso índice baseado em RL supera a Árvore R e suas variantes em termos de tempo de processamento de consultas.