Google is testing a new ad format associated with it’s Google Maps service, as pointed out by the Search Engine Round Table. If you do a geographic search, little icons will show up on the map that identify advertisers close to your search location. For example, if you search "hotels san francisco" you’ll find a small icon with a bed near all of the generic pushpins. Click on the icon, and you see a "Sponsored Link" from the Mark Hopkins Hotel. Do a search on "booksellers nyc" and you’ll find an icon for a coffee shop, sponsored by Barnes and Noble. I did a little searching around on other cities and business types, and couldn’t find anything else, so it must be pretty early in the rollout.