Mobility management schemes that reduce signaling traf®c load and connection setup time play a pivotal role in designing future personal communication services (PCS) network. It concerns users' Quality of Service (QoS) requirements and the ef®cient use of network resources. In recent years, many mobility management schemes have been proposed for the reduction of signaling traf®c and network load. Regardless of the speci®c protocol, all such technologies must support two fundamental mechanisms. One is location management (knowing where the users are) and the other is handover management (making the transition between cells smooth). In location management, a mobile user has to register when entering a new registration area (RA) and to deregister when leaving. To reduce the signaling cost in registration and deregistration, Lin and Noerpel proposed an implicit deregistration scheme. That is, a mobile will not perform deregistration when leaving a RA. As a result, there are two consequences. First, we need a large registration database. Second, even with a large database, it will become full eventually. Then we have to select a record to delete when a new mobile moves into the RA. In the original implicit deregistration scheme, the oldest record is deleted. In this paper, we propose two more reasonable and effective criteria to determine which record should be deleted from the database when a new mobile moves into an RA and the database is full. The purpose is to decrease the database size and ensure a low probability that a valid record will be replaced at the same time. The two parameters used are call-to-mobility ratio (CMR) and average call arrival interval. When the database is full, the proposed method will delete the record that has the lowest CMR or that will have to wait for the longest time for an expected call arrival. Simulation results show that the modi®ed approach has signi®cant improvements on the database sizes.