Indexing Strategies for Graceful Degradation of Search Quality

Large web search engines process billions of queries each day over tens of billions of documents with often very stringent requirements for a user’s search experience, in particular, low latency and highly relevant search results. Index generation and serving are key to satisfying both these requirements. For example, the load to search engines can vary drastically when popular events happen around the world. In the case when the load is exceeding what the search engine can serve, queries will get dropped. This results in an un-graceful degradation in search quality. Another example that could increase the query load and affect the user’s search experience are ambiguous queries which often result in the execution of multiple query alterations in the back end. In this paper, we look into the problem of designing robust index-ing strategies, i.e. strategies that allow for a graceful degradation of search quality in both the above scenarios. We study the prob-lems of index generation and serving using the notions of document allocation, server selection, and document replication. We explore the space of efficient algorithms for these problems and empirically corroborate with existing theory that it is hard to optimally solve the allocation and selection problems without any replication. We pro-pose a greedy replication algorithm and study its performance un-der different choices of allocation and selection. Further, we show that under random selection and allocation, our algorithm is opti-mal