I'm currently in the process of designing a Google Maps Store Locator application.
For the same, the store data will be hosted in Google and Google Maps API will be used to render the maps.
The data can either be stored in Google Maps Engine (paid) or Google Fusion Tables (Experimental but free).
I'm having a hard time deciding which one to go with.
Questions:
Has anyone worked on both or either?
What are the pros and cons of both?
Here's a quick summary...
Most of this data comes from the product page.
There's lots of useful Fusion Tables info in this question.
I can't really suggest one solution or the other, as it will depend on your specific needs. If you're serious about long-term use of geo data (especially if you already have it in a GIS platform, or have a lot of data) I'd probably use Maps Engine. If you're looking to do some quick visualisations of a "small" set of data (<100k rows) and aren't too worried about the inherent risks of experimental tools, then I'd use Fusion Tables.
Regarding your store locator specifically, the Maps Engine docs describe Best Practices for creating a Store Locator, as well as a video demo.