The increasing availability of location aware mobile devices has given rise to a flurry of Location-Based Services (LBS). Due to the nature of spatial queries, an LBS needs the user position in order to process the requests. On the other hand, revealing exact user locations to (potentially untrusted) LBS may pinpoint their identities and breach their privacy. To address this issue, spatial anonymity techniques obfuscate user locations, forwarding to the LBS a sufficiently large region instead. Existing methods explicitly target processing in the Euclidean space, and do not apply when proximity to the users is defined according to network distance (e.g., driving time through the roads of a city).