In location-based services, the response time of location determination is critical, especially for real-time applications. This is especially true for pattern-matching localization methods, which rely on comparing an object's current signal strength pattern against a pre-established location database of signal strength patterns collected in the training phase. In this work, we propose some cluster-enhanced techniques to speed up the positioning process while avoiding the possible positioning errors caused by this accelerated mechanism. Through grouping training locations with similar signal strength patterns together and characterizing them by a single feature vector, we show how to reduce the associated comparison cost so as to accelerate the pattern-matching process. To deal with signal fluctuations, several clustering strategies allowing overlaps areproposed. Extensive simulation studies are conducted. Experimental results show that compared to the pattern-matching systems without clustering techniques, a reduction of more than 90% in computation cost can be obtained in average without degrading the positioning accuracy.