pipette
ENEnglish

Truly Sub- Min-Sum Subset Convolution and Join Ordering

Mihail Stoian

PreprintDice ser un gran avance

En palabras de los autores

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two matrices with -bit integer entries can be computed in time for a fixed rational , then min-sum subset convolution on an -element universe can be solved in time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time and a deterministic algorithm with running time , strictly breaking the longstanding computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the cost function.

Resultado principalLimitación que admiten los autores

En palabras simples Resumen con IA

Los autores crearon un método determinista que convierte problemas de convolución de subconjuntos de suma mínima en problemas de producto de matrices de min-plus. Demostraron que una multiplicación de matrices de min-plus más rápida conduce a una convolución de subconjuntos de suma mínima más rápida, con fórmulas de tiempo específicas dadas. Usando avances recientes en multiplicación de matrices, lograron tiempo esperado O*(2.9987^n) y tiempo determinista O*(2.9997^n), superando el límite anterior de 3^n. Estas mismas aceleraciones se aplican directamente a la optimización de consultas de bases de datos para el ordenamiento de joins bajo la función de costo C_out.

Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Feedback welcome