Formulating and processing of multimedia queries using mobile devices presents many challenges. This is due to the limitations of the devices themselves and the cost of the bandwidth involved in transmitting multimedia data between servers and devices. In this paper we propose a novel approach: “query streaming” which uses Reverse Polish Notation to perform multimedia query-by-example on a mobile device and server. An important advantage of query streaming is the ability to perform a query within the previous result set. To solve the problem of limited resources, the concept of result set examination using Fragment Request Units and Fragment Update Units is also explored. MPEG BiM compression is performed on the communication messages to further minimize transmission requirements.