The list on the server could be classified by region and time period (certainly this reduces privacy, but would still prevent tracking individual movements with

The list on the server could be classified by region and time period (certainly this reduces privacy, but would still prevent tracking individual movements with precission). This way the phone would need to download just the lists for those regions and periods of the places it has been through.