A location service tracks and locates objects. Such a service should provide efficient means for updating and looking up an object's address, especially for those that are mobile. However, current location services have limited scalability due to poor exploitation of locality and ineffective caching. An important aspect of efficient caching in the presence of mobility is to identify boundaries of the region within which a mobile object usually remains. Caching a reference to such a region rather than to the object itself ensures that the cached entry remains stable. Identifying a region requires dynamically taking migration patterns into account. This paper describes a scalable location service that efficiently supports tracking mobile objects, partly by dynamically adapting to the mobile behavior of each object separately.