I'm designing a web app (using Google Maps) that will allow users to search for residential postal addresses in my database.
That is, users will provide addresses and I'll store them; later, other users will type in an address to see if that address is in my database.
But addresses are notoriously hard to normalize; I can't figure out how best to store/query them. (Especially since Google's Geocoder doesn't let me store the results of the geocoder.)
What's the best approach?
This is a problem that can be solved both by lat-long (use R-trees for quick 2-D closest neighbours! Comes as standard in MongoDB, but certainly availiable i Psql among others as well)
There's also the text matching, described here: SO: What are ways to match street addresses in SQL Server?
There seems to be third party products availiable as well: SO: I need an address matching algorithm
If you want to combine these two approaches, look for the term "data fusion", which is a quite disparate collection of methods that essentially put higher weight to answers that are more certain, and bases the final answer on the aggregated certainty.
A description of some Harward Design GIS-project research could be of interest as well: http://www.gsd.harvard.edu/gis/manual/geocoding/
There's a list of all the cities in the world with their corresponding coordinates: http://www.maxmind.com/en/worldcities