Взять все точки и поделить нацело на длину ячейки масштабной сетки. Полученные точки занести в хеш-таблицу и закешировать. Для каждого масштаба хранить свою таблицу. При обновлении данные вносить изменения в каждую таблицу. При запросах доставать данные из таблицы в зависимости от масштаба. В качестве хранилища я бы использовал MongoDB (
Geospatial Indexing)
