Tengo la siguiente tabla con 2 columnas: ID y Título que contiene más de 500,000 registros. Por ejemplo

ID  Title
--  ------------------------
1   Aliens
2   Aliens (1986)
3   Aliens vs Predator
4   Aliens 2
5   The making of "Aliens"

Necesito encontrar registros que sean muy similares, y con eso quiero decir que son diferentes en 3-6 letras, por lo general, esta diferencia se encuentra al final de los Títulos. Entonces tengo que diseñar una consulta que devuelva los registros no. 1,2 y 4. Ya miré la distancia levenstein, pero no sé cómo aplicarla. Además, debido a la cantidad de registros, la consulta no debería durar toda la noche.

Gracias por cualquier idea o sugerencia