Classification of Instant Search
There are two types of instant search: multi-user-based instant search and single-user-based instant search.
(1) Multi-User-Based (e.g., Google Instant and the "Search" box on the Apple homepage): In such a setting, we have a server that can be queried from many users concurrently. Therefore, achieving high query throughput is extremely very important. Studies have shown that in order to achieve an "instant speed," from the time a user presses a keystroke to the time they see the final results, the total time should be within 100 milliseconds. In a client-server environment, the total time should include the round-trip network time between the client machine and the server, the search time on the server, and the time of executing Javascript functions, which tend to be slow. Therefore, each search on the server should be done very efficiently. Since many users can query the server at the same time, the server has to answer each of the concurrent queries within milliseconds in order to guarantee a high QPS (queries per second). To achieve such a high speed, the server typically uses in-memory data structures and algorithms. Since the data and index are queried by many users, it is worth having enough memory to store them.
At the same time, this setting has a big advantage that many users are querying the same server, which can keep track of query logs and the past queries of each user. Such information can be used by the server to do powerful query predictions and improve its ranking function.
(2) Single-User-Based (e.g., Microsoft Desktop Search and Google Desktop Search):
In this setting, a single user is searching on their own data such as email in Outlook and files on the disk. Since there is only one user of the search, the requirement on a high speed becomes less. In addition, the operating system can only allocate a limited amount of memory for the search process, so the search has to use disk-based index structures and algorithms, which can already achieve an acceptable performance for a single user.
There is a fundamental difference between Google Instant and other instant-search programs such as the people search system called PSearch for the UC Irvine directory.
(a) Google Instant heavily utilizes the user's personal search history and query logs of many users to first predict what the user is likely to query. For instance, suppose we type in a prefix "cal." Based on our past search history, the engine predicts five possible queries, such as "california," "california lottery," "california dmv," etc, and uses the first prediction to query the backend engine. Such a prediction is possible since millions of users are providing queries to the search engine, which can use the information to come up with accurate predictions. Clearly this approach will not be feasible if we don't have a lot of query logs and user profile information.
(b) The PSearch system does not assume any past query history. Instead, as a user types in a keyword query character by character, the engine will issue a search on the backend data "on the fly." Such a search engine can be built in many applications where query logs are not available apriori. In the case when query logs are indeed available, the engine can utilize the information to improve the ranking. Many other programs such as Microsoft Desktop Search follow into the same category.
(To be continued ...)
Miscellaneous:
