104 LOCATION SYSTEMS
can be achieved, there is still a threat: a mugger, for example, may not know who is in the park late
at night, but they know someone is. Gruteser and Grunwald address this threat with a technique to
allow a group of users to combine their location estimates together for increased anonymity. Their
algorithm allows mobile users to achieve what they call k-anonymity in a location system by blur-
ring their location estimate until it includes the location of at least k users . The result is that in
a crowded plaza, you may disclose your identity with meter resolution, while on a late-night walk,
your estimates may automatically blur to neighborhood granularity.
9.2 “PLACE” TECHNOLOGIES
The most widely deployed location systems produce coordinate-based location estimates such as
latitude and longitude. These estimates are an excellent match to navigation and emergency re-
sponse applications that require either absolute locations or the ability to compute the geometric
relationship between locations. Other classes of applications, such as social networking, are less well
served by this type of location estimate. When did you last hear someone say something of the form:
“Gosh, you’ll never guess who I bumped into at 43.394 north, 79.233 west!”? For these applications,
place names such as “home,” “work,” or “the mall” carry more semantic meaning and are more valu-
able as location estimates than a set of coordinates.
Room-level location systems such as infrared and ultrasound beacons can support this type
of location estimate by simply augmenting their broadcasts with a place name. It requires more
work for wide-area systems like GPS and modeled GSM/802.11. Ashbrook and Starner developed
a technique for learning and recognizing the indoor places a GPS user goes by clustering the loca-
tions where GPS coverage is lost . Similarly, Hightower et al. have developed an algorithm for
using stable periods of observed 802.11 and GSM signals to learn a user’s important places .
These techniques solve part of the problem in that they can identify a set of discrete places relevant
to the user from streams of continuous location estimates. Automatically naming those places has
yet to be solved, and existing systems that have made use of learned places have relied on manual
user labeling .
Automatic place naming is a high value, but likely difﬁcult research challenge. Service such as
Microsoft’s Virtual Earth and Google Maps contain information about the commercial services at
or near a given set of coordinates. Cooperation schemes like those for collaborative image labeling
could allow any manual naming or corrections to be shared with others. Ultimately, the problem
remains difﬁcult though, because of the personal and multi-dimensional nature of a place. One
location can be, for example, pizza parlor, commercial building, work, restaurant, rental property, and
teen hangout all at the same time. Questions about how to represent and use place names and how
to build and use name ontologies still remain to be answered.