title: Which data structure should I use for geocoding?
body: <p>I am trying to create a Python script which will take an address as input and will spit out its latitude and longitude, or latitudes and longitudes in case of multiple matches, quite like <a href="http://wiki.openstreetmap.org/wiki/Nominatim" rel="nofollow">Nominatim</a>.</p>
  
  <p>So, the possible input and outputs could be:-</p>
  
  <ol>
  <li><em>In:</em> New York, USA <em>=> Out:</em> New York (lat:x1 lon:y1)</li>
  <li><em>In:</em> New York <em>=> Out:</em> New York (lat:x1 lon:y1)</li>
  <li><em>In:</em> Pearl Street, New York, USA <em>=> Out:</em> Pearl Street (lat:x2 lon:y2)</li>
  <li><em>In:</em> Pearl Street, USA <em>=> Out:</em> Pearl Street (lat:x2 lon:y2), Pearl Street (lat:x3 lon:y3)</li>
  <li><em>In:</em> Pearl Street <em>=> Out:</em> Pearl Street (lat:x2 lon:y2), Pearl Street (lat:x3 lon:y3)</li>
  <li><em>In:</em> 103 Alkazam, New York, USA <em>=> Out:</em> New York (lat:x1 lon:y1)</li>
  </ol>
  
  <p>In 6 above, New York was returned since no place was found with address <code>103 Alkazam, New York, USA</code>, but it could at least find <code>New York, USA</code>.</p>
  
  <p>Initially I thought of building a tree representing the hierarchy relation where siblings are sorted alphabetically. It could have been like:-</p>
  
  <pre><code>                                     GLOBAL
                                         |
                     ---------------------------------------------
                     |            | ...
                    USA
               ---------------
               |        | ...
           CALIFORNIA  NEW YORK 
              |         |
       -----------    -------------
       |        |..   |          |....
   PEARL STREET      PEARL STREET
  </code></pre>
  
  <p>But the problem was user can provide incomplete address as in 2, 4 and 5.</p>
  
  <p>So, I next thought of using a search tree and store the fully qualified address in each node. But this too is quite bad since:-</p>
  
  <ul>
  <li>This will store highly redundant data in each node. Since this will be a really big data so, space conservation matters.</li>
  <li>It won't be able to leverage the fact that user has narrowed down the search space.</li>
  </ul>
  
  <p>I have one <em>additional requirement</em>. I need to detect misspellings. I guess that will have to be dealt as a separate problem and can treat each node as generic strings.</p>
  
  <p><strong>Update 1</strong></p>
  
  <p>A little elaboration. The input would be a list, where the item on lower index is parent of the item in higher index; and they of course may or may not be immediate parent or child. So for query 1, input would be <code>["USA", "NEW YORK"]</code>. So, it is perfectly fine that <code>USA, New York</code> returns no result.</p>
  
  <p>The user should be able to locate a building if he has the address and our data is so detailed.</p>
  
  <p><strong>Update 2 (Omission Case)</strong></p>
  
  <p>If user queries <code>Pearl Street, USA</code>, so our algo should be able to locate the address since it knows <code>Pearl Street</code> has <code>New York</code> as parent and <code>USA</code> is its parent.</p>
  
  <p><strong>Update 3 (Surplus Case)</strong></p>
  
  <p>Suppose the user queries for <code>101 C, Alley A, Pearl Street, New York</code>. Also suppose our data does know of <code>101 C</code> but not about <code>Alley A</code>. According to it <code>101 C</code> is a immediate child of <code>Pearl Street</code>. Even in this case it should be able to locate the address.</p>