In this paper, conceptual frequency rate, a new frequency definition suitable for query stream mining, is introduced. An online single-pass algorithm called OFSD (Online Frequent Sequence Discovery) is given, to mine the set of all conceptual frequent sequences in a data stream whose conceptual frequency rates satisfy a minimum user defined frequency rate. Phrase recommender algorithm is then described based on the set of conceptual frequent phrases extracted by the OFSD algorithm. We have also designed a query recommender algorithm, OQD (Online Query Discovery). OQD is used for comparison purposes along side the proposed phrase recommender algorithm. Simulation results show the efficiency of the proposed Phrase recommender algorithm compared to OQD.