I have 10 millions of filenames and I need to determine whether filename corresponds to some movie or video game. For this I initially thought to compare filenames using Levenshtein distance with imdb list ftp://ftp.funet.fi/pub/mirrors/ftp.imdb.com/pub/ but it turns out that direct compassion requires $O(nm)$ where n is number of filenames and m is number of items in imdb database, both of which in millions range. I think there should be a way to organize imdb list in some tree like suffix structure to speed up comparisons to something like $O(n \log m)$. Any other advices and ideas are very much appreciated, too.
This blog post discusses and contains code for the use of tries (prefix trees) for fast Levenshtein distance computations.: http://stevehanov.ca/blog/index.php?id=114
If reducing space complexity is also a concern, read the follow-up post too: http://stevehanov.ca/blog/index.php?id=115