In recent years, considerable concern has arisen over the security of the data stored in the cloud. A number of studies have suggested the use of cryptographic primitives to protect the data. As these tools transform the data into an unintelligible form, secure and efficient retrieval of the encrypted data from the cloud becomes a major challenge. The public-key encryption with keyword search (PEKS) scheme and many of its variants have been proposed to respond to this challenge. However, given a large number of data (or searchable keywords) would be tested sequentially in these PEKS schemes, previous search results should be employed to improve the efficiency of future searches. In this paper, we present an interactive construction named iPEKS where the search time is linear to the total number of distinct searched keywords instead of the total number of the searchable keywords. The more the keywords have been searched previously, the better the efficiency can be improved. We provide theoretical analysis to show the security and privacy. In addition, implementation and performance experiments exhibit a great improvement in efficiency compared with the previous schemes.