Fast searching a particular subset in a large number of products attached with radio frequency identification (RFID) tags is of practical importance for a variety of applications, but not yet thoroughly investigated. Since the cardinality of the products can be extremely large, collecting the tag information directly from each of those tags could be highly inefficient. To address the tag searching efficiency in large-scale RFID systems, this paper proposes several algorithms to meet the stringent delay requirement in developing fast tag searching protocols. We formally formulate the tag searching problem in large-scale RFID systems. We propose utilizing compact approximators to efficiently aggregate a large volume of RFID tag information and exchange such information with a two-phase approximation protocol. By estimating the intersection of two compact approximators, the proposed two-phase compact approximator-based tag searching protocol significantly reduces the searching time compared to all possible solutions we can directly borrow from existing studies. We further introduce a scalable cardinality range estimation method that provides inexpensive input for our tag searching protocol. We conduct comprehensive simulations to validate our design. The results demonstrate that the proposed tag searching protocol is highly efficient in terms of both time efficiency and transmission overhead, leading to good applicability and scalability for large-scale RFID systems.