SONGO (Search ON the GO) is a web search caching system for mobile devices that allows most of the submitted queries to be served locally without having to use the 3G link. Initially, a community-based search cache is generated by mining the most popular queries and links from the mobile search logs. This cache is updated daily making sure that the latest popular information is always available locally on the mobile device. Over time, the community-based cache is incrementally updated with the queries and links that the individual user submits and visits respectively. An analysis of 200 million queries shows that, on average, 66% of the search queries submitted by an individual user can be locally served by caching 2,500 links at the expense of 1MB of flash and 200KB of RAM space. A prototype implementation of SONGO in Windows Mobile demonstrates that a cache hit results into 16x faster responses and 23x energy savings when compared to querying through the 3G link.