-1

There is a database with N fixed length strings. There is a query string of the same length. The problem is to fetch first k strings from the database that have the smallest Hamming distance to q. how can I do this without traverse the whole database?

flag
2 
 Where did you come across the problem? See mathoverflow.net/faq#whatnot – Yemon Choi Feb 16 2012 at 7:23
2 
 Well-known NP-complete problem. – Felipe Voloch Feb 16 2012 at 13:37
2 
 don't do it exactly, search for "approximate nearest neighbors", "locality sensitive hashing", "metric ball trees", etc. – S. Sra Feb 16 2012 at 14:56

closed as off topic by Will Jagy, David Roberts, Willie Wong, Chris Godsil, S. Sra Feb 16 2012 at 16:52

Browse other questions tagged or ask your own question.