  Location based services (LBS) have become very popular in recent years. They
range from map services (e.g., Google Maps) that store geographic locations of
points of interests, to online social networks (e.g., WeChat, Sina Weibo,
FourSquare) that leverage user geographic locations to enable various
recommendation functions. The public query interfaces of these services may be
abstractly modeled as a kNN interface over a database of two dimensional points
on a plane: given an arbitrary query point, the system returns the k points in
the database that are nearest to the query point. In this paper we consider the
problem of obtaining approximate estimates of SUM and COUNT aggregates by only
querying such databases via their restrictive public interfaces. We distinguish
between interfaces that return location information of the returned tuples
(e.g., Google Maps), and interfaces that do not return location information
(e.g., Sina Weibo). For both types of interfaces, we develop aggregate
estimation algorithms that are based on novel techniques for precisely
computing or approximately estimating the Voronoi cell of tuples. We discuss a
comprehensive set of real-world experiments for testing our algorithms,
including experiments on Google Maps, WeChat, and Sina Weibo.
