Summary
Many popular smartphone apps, including web search, maps, yelp, and others, solely rely on the cloud for its operations. The apps fail completely during periods of no connectivity and suffer from poor performance even under good connectivity.
As a first step, we focus on improving the performance of web search by reducing its reliance on the cloud.
The question we ask in FindAll is: Can we trade-off local storage for connectivity to improve web search performance?
To this end, FindAll caches all web pages that a user visits on all of her devices. It then implements a powerful local search engine on the phone to effectively search through the cache. We implement FindAll on Android, and our evaluation shows that FindAll can halve search latency, while simultaneously improving energy consumption by 30%.
A full paper describing FindAll can be found here. Below we describe some high level details of the approach and results.
Approach
FindAll leverages the re-finding behavior of web search users. Users often search for web pages that they have previously visited. Our own user study shows that over 50% of the mobile searches are repeated at least once. If you include searches done by the user on all their devices, the percentage of at least one re-find goes up to 72%.
FindAll leverages re-finding by caching all past web searches.
FindAll then implements a hybrid search: for new requests, the search is performed in the cloud, but for re-find requests, the search is performed locally. The key to the effectiveness of FindAll is the implementation of a full-blown search engine on the phone; boolean or keyword search are simply not effective.
However, running a search engine on the phone is both memory- and an energy-intensive because of the cost of indexing.
FindAll uses a concept of partial indexing to adapt an off-the-shelf search engine to the memory-constrained phone environment. To reduce energy consumption, we designed an adaptive algorithm that indexes a web page only if the user is likely to request the web page.
The design is motivated by a user study we conducted, in which we collected the mobile search patterns of 23 real users for 30 days.
Our key finding from the user study is that there is a large diversity in how users search, but the search behavior of a single user is relatively consistent. This allows us to build an indexing algorithm that learns from a user's past search behavior. Below, we show the FindAll architecture.
Results
We implement FindAll on Android and adapt Galago, an open source search engine, to phones. The key results are as follows: By avoiding the cloud and searching locally when possible, FindAll reduces search latency by a factor of two. Because FindAll adapts to user behavior, its improvements does not come at an energy cost. In fact, FindAll reduced the overall energy consumption by 30%.
These improvements come because FindAll increases local availability of web pages by 40%.
As a side benefit, FindAll reduces expensive 3G data usage by up to 100 MB a month for users who re-find often.
We will soon release the code for FindAll. For questions or comments, contact
Aruna Balasubramanian at arunab@cs.washington.edu.
