GPS receivers are included in many mobile communications devices; however, there are circumstances where GPS is unavailable or undesirable to use. In an implementation, a device identifies nearby wireless signals, such as Wi-Fi access points and cell towers, and compares them to a database of known signals to determine an approximate location for the device. Because such a database can be large and change rapidly, it may not be appropriate to store the database entirely on a device. Instead, a server may store the database. In an implementation, to minimize the time required to determine a device's location, the device may first transmit location-related information to a server and receive a subset of the database corresponding to an area near the device so that future locations nearby can be determined without needing to communicate with the server.