Abstract: Upper bounds on the scalability of Client-Server Databases (CSDs) persist due to long delays experienced at the servers' queues. To this end, we have proposed a three-tier architecture that exploits similarities in object access behavior demonstrated by clients. Clients are statically grouped into logical clusters and object requests can be then served in an "internal to cluster" fashion. This is achieved with the introduction of an intermediate directory tier. Good client clustering yields more scalable CSD configurations as it minimizes the number of inter-cluster data accesses. In this paper, we introduce the problem of client realignment in light of changing client localities and propose an on-line reclustering framework to address it. On-line reclustering facilitates adaptive reconfiguration and redistribution of sites. The core of our proposal is a "change-detection" approach that uses meta-data extracted from observed clients' access patterns. We evaluate the impact of employing a multi-featured change detection scheme in the three-tier CSD architecture and experimentally investigate its performance and trade-offs involved.