The search completion as the user types the keywords is relatively easy to implement and Google Suggest has API for auto-completion.
If you are working on the finite set of keywords, such as categories or lists of products I would suggest to load it once on-install to the mobile SQLite database and update the changes periodically to achieve ultra-fast experience without the network lag.
