Buying place details with a greedy set cover

The quickest way to burn an API budget is to ask for everything on every call. My sweep of India’s automation firms made 49,695 searches, and the average place turned up on 3.8 of them. Asking for names and phone numbers each time would have bought most places several times over.

Three tiers for the same search

The Places API lets you choose which fields come back, and the fields decide the billing tier:

• IDs only: each place’s unique code, plus a token for the next page. This is the free kind.
• Basic details: name, address, Google category and Maps link. Paid.
• Full details: adds website, phone and rating. Paid, at a higher tier.

The quadtree sweep needs thousands of searches to get under the 60-result cap, and most of them matter only because they prove a square was covered. So every sweep search asked for IDs only. Each page of results was saved with its keyword, its square and its page number. Nothing was bought yet.

Every saved page is a possible purchase

That left a menu. Mumbai’s sweep produced 4,300 non-empty result pages holding 5,911 distinct places. India’s produced 34,227 pages holding 78,624. Any page can be fetched again with paid fields, and it returns up to 20 places in one call. A single place lookup returns one.

So the question became: which pages, bought again, cover every place I want with the fewest paid calls? That’s the set cover problem. The exact answer is impractical at this size, but the greedy answer is good:

need = set(wanted_ids)
while need:
    page = max(pages, key=lambda p: len(p.ids & need))
    if len(page.ids & need) < 2:
        break                  # cheaper one at a time from here
    buy(page)                  # one paid call, up to 20 places
    need -= page.ids
for pid in need:
    buy_details(pid)           # one paid call, one place

The real version keeps pages in a priority queue and recounts a page’s gain only when it reaches the top, so it never rescans every page after each pick. Once the best page would add fewer than two new places, the planner stops and looks up the rest one by one.

The page-token trick

Google serves pages two and three of a search only with a token from the page before. When the planner wants page three, it walks pages one and two again with the free IDs-only fields to collect the tokens, and pays only for page three. Chosen pages are grouped by search, so each chain is walked once.

Rank before you buy

Nationally I didn’t want every place. Before any purchase, a ranking step scored all 78,624 on signals from the Mumbai calibration: how many different searches found it, whether one of those searches covered a wide area, and whether anything other than “smart home” found it (that search mostly returns electronics shops). Places found by one search in a small square, and places only “smart home” found outside the widest searches, were dropped. 62,012 went forward in ranked order. The other 21% were never targeted for a paid lookup.

Guard rails

• Dry run first. The planner prints how many paid pages it would buy, how many places they cover and how many single lookups remain, then stops.
• Hard caps on paid pages and on single lookups. A page cap drops the pages that add the fewest places; a lookup cap drops the lowest-ranked places.
• Two levels of detail. Basic details and the dearer pass, with websites and phones, are separate runs. Each takes its own list of IDs, so the dearer one can be limited to the places the rules kept.
• A counter per billing tier, saved after every run and added across runs, so I always knew how many calls of each kind had been made.
• Never buy twice. Everything fetched merges into one store, and the planner skips any place that already has the fields it needs.

What I took from it

1. Find what’s free and do all the exploring there.
2. You pay per call, not per place, so make each call carry as much as possible of what you still need.
3. Rank before you buy, so caps cut from the bottom.
4. Dry-run every purchase, and count by tier as you go.

The planner is about 150 lines of Python, built with Claude Code.