New applications in the area of mobile computing make heavy use of knowledge about the application's run-time environment. Applications running on mobile devices in particular exploit knowledge about their current geographical position or query for the location of other interesting objects. To manage such queries some applications provide a location service specifically tailored for their needs. The efficient and application-independent handling of such queries calls for a global and universal location service. Considering a large number of users and queries to be handled, a distributed implementation of a location service is necessary. This paper analyses three schemes for the partitioning of location information and derives a performance model for these partitioning schemes. Finally, an example for the application of the analysis' results is presented for a universal location service within the Nexus system, an infrastructure for location aware mobile computing.