title: how to do fuzzy search in big data
body: <p>I'm new to that area and I wondering mostly what the state-of-the-art is and where I can read about it.</p>
  
  <p>Let's assume that I just have a key/value store and I have some distance(key1,key2) defined somehow (not sure if it must be a metric, i.e. if the triangle inequality must hold always).</p>
  
  <p>What I want is mostly a search(key) function which returns me all items with keys up to a certain distance to the search-key. Maybe that distance-limit is configureable. Maybe this is also just a lazy iterator. Maybe there can also be a count-limit and an item (key,value) is with some probability P in the returned set where P = 1/distance(key,search-key) or so (i.e., the perfect match would certainly be in the set and close matches at least with high probability).</p>
  
  <hr>
  
  <p>One example application is fingerprint matching in <a href="http://musicbrainz.org" rel="noreferrer">MusicBrainz</a>. They use the <a href="http://acoustid.org" rel="noreferrer">AcoustId</a> fingerprint and have defined <a href="https://github.com/lalinsky/acoustid-server/blob/master/postgresql/acoustid_compare.c" rel="noreferrer">this compare function</a>. They use the PostgreSQL GIN Index and I guess (although I haven't fully understood/read the acoustid-server code) the <a href="http://www.postgresql.org/docs/devel/static/gin-implementation.html#GIN-PARTIAL-MATCH" rel="noreferrer">GIN Partial Match Algorithm</a> but I haven't fully understand wether that is what I asked for and how it works.</p>
  
  <hr>
  
  <p>For text, what I have found so far is to use some <a href="http://en.wikipedia.org/wiki/Phonetic_algorithm" rel="noreferrer">phonetic algorithm</a> to simplify words based on their pronunciation. An example is <a href="http://playnice.ly/blog/2010/05/05/a-fast-fuzzy-full-text-index-using-redis/" rel="noreferrer">here</a>. This is mostly to break the search-space down to a smaller space. However, that has several limitations, e.g. it must still be a perfect match in the smaller space.</p>
  
  <p>But anyway, I am also searching for a more generic solution, if that exists.</p>