Proactive Visualization of Search Queries in Hierarchical Document Collections

Abstract

Given a large collection of documents, a normal search interface only helps the user when the desired information is among the top 10 results. Although there is often a hierarchical structure which is an organization paradigm, it is rarely used. Here we propose an extension to the normal search interface which places search results in a hierarchical document structure to provide the user with a sense of context. Our search extension is implemented as follows. First, in a preprocessing step, we create mental map positions of the document hierarchy according to document similarities. Next, we use Multidimensional Scaling to ensure that similar documents are close together. By combining Voronoi Treemaps with Stress Majorization we elaborate a visualization which can proactively show the user the important parts of the hierarchy according to a search query. The similarity is considered and by using the mental map positions as initial layout the overall structure is mostly maintained, as measures show. The available space is used efficiently and the context of the result documents is shown by drawing them as nodes and their dependencies as hierarchically bundled edges. Our approach is scalable and widely applicable. The Voronoi Treemap is ana- lytically computed in O(k · n log n) where k is the number of iterations and n the number of nodes in the hierarchy; previous approaches used Monte Carlo based methods and needed O(k · n² + n² log n). The combination of Voronoi Treemaps and Stress Majorization might be used in any field where hierarchy, size and location of elements play an important role.