Along with the increased convenience of our daily life thanks to the proliferation of location-based service (LBS), such as finding restaurants and booking taxi, concerns on privacy disclosure risks in sharing our locations with LBS have also increased and become a major bottleneck that obstacles the widespread of adoption of LBS . To preserve privacy in LBS, k-anonymity was applied to conceal people's sensitive information against re-identification attacks . Unfortunately, the k-anonymity technique relies on predefined background knowledge of an adversary. Once the adversary has different auxiliary information, we cannot guarantee any privacy preservation against such an adversary. To address the privacy leakage problem of the naive k-anonymity, a combination of k-anonymity and location's query frequency algorithm, the Caching-aware Dummy Selection Algorithm (CaDSA), were proposed . CaDSA anonymises locations in a given area by grouping them with similar query frequency during a fixed time period, say one day. However, considering in the real-life situation location's query frequency often varies in different time slots even in a single day, privacy will clearly lose if we roughly group locations according to a fixed time period as CaDSA. Consequently, in this paper, we propose a Temporal Caching-aware Dummy Location Selection Algorithm (T-CaDLSA) that considers the differences among location's query frequencies over different time slots within a given time period (day). Both mathematical and experimental evaluations show that to achieve the same data utility, our method outperforms the existing work in privacy guarantee.