Exploiting Available Memory and Disk for Scalable Instant Overview Search

Abstract. Search-As-You-Type (or Instant Search) is a recently intro-duced functionality which shows predictive results while the user types a query letter by letter. In this paper we generalize and propose an ex-tension of this technique which apart from showing on-the-fly the first page of results, it shows various other kinds of information, e.g. the outcome of results clustering techniques, or metadata-based groupings of the results. Although this functionality is more informative than the classic search-as-you type, since it combines Autocompletion, Search-As-You-Type, and Results Clustering, the provision of real-time interaction is more challenging. To tackle this issue we propose an approach based on pre-computed information and we comparatively evaluate various in-dex structures for making real-time interaction feasible, even if the size of the available memory space is limited. This comparison reveals the mem-ory/performance trade-off and allows deciding which index structure to use according to the available main memory and desired performance. Furthermore we show that an incremental algorithm can be used to keep the index structure fresh.