| Abstract |
There is an increasing interest on recommending to the user instantly (during
typing characters) queries and query results. This is evidenced by the emergence
of several systems that offer such functionalities (e.g. Google Instant Search,
Facebook for social searching, IMDB for movie searching, etc). In this thesis we
consider more informative recommendations based on various precomputed aggregated
information. Such recommendations can accommodate the products of
various services like autocompletion, search-as-you-type, results clustering, faceted
search, entity mining, etc. The instant presentation of these recommendations
helps the user (a) to discover fast what is popular among other users, (b) to decide
fast which (of the suggested) query completions to use, and (c) to decide what
hits of the returned answer to inspect. In this thesis we focus on making this
feasible (scalable) and flexible. Regarding scalability we elaborate on an approach
based on precomputed information and we comparatively evaluate various triebased
index structures for making real-time interaction feasible, even if the size
of the available memory space is limited. For improving the throughput that can
be served we analyze and experimentally evaluate various caching policies. We
report performance results over a server running on a modest personal computer
(with 3 GB main memory) that provides instant services (in less than 140 ms) for
millions of distinct queries and terabytes of precomputed information. As regards
flexibility, in order to reduce user’s effort and to increase the exploitation of the
precomputed information, we elaborate on how the recommendations can tolerate
different word orders and spelling errors, assuming the proposed trie-based index
structures. The experimental results revealed that such functionality significantly
increases the number of recommendations especially for queries that contain several
words.
|
Indexes and Algorithms for Scalable and Flexible Instant Overview Search
