Improving the effectiveness and efficiency of text search has been a central issue in the field of information retrieval. A better algorithm that ranks relevant documents higher out of the huge volume of irrelevant ones is required, especially for improving the effectiveness of Web search. Furthermore, as the target information can rarely be obtained through single-shot queries, a better way of displaying search results is desired to improve the efficiency of Web search, because it would help the user to assess the relevance of the returned documents. This paper demonstrates how the newly introduced Graph-based Text Representation can improve both the effectiveness and efficiency of Web search.
We proposed a graph-based text representation model[1], that can represent both documents and queries. Such a graph is called "Subject Graph"; an instance is given in Figure-1. In the graph, a node represents a term in the text, while a link denotes an association between the linked terms. Significance of the terms and the term-term associations are represented as weights assigned to them. The model does not restrict the weighting scheme employed, and we can adopt conventional term-statistics-based weighting schemes. However, it should be remarked here that the Graph-based model is possibly richer than the conventionally utilized Vector Space Model (VSM)[2] in which term-term associations are not incorporated.
VSM represents both queries and documents as term vectors, and calculates the similarity based on the inner product or cosine measure. While VSM has been excessively used in many search engines, it is reported that the model is problematic in handling documents with several topics[3]. Such documents are frequently seen on the Web these days. In contrast to VSM, our Graph-based model calculates the similarity based on Subject Graph Matching. The similarity from the Graph-based model is more correct than that from VSM, because the term-term association is adequately incorporated into the similarity calculations. Details of the weighting scheme, the matching algorithm and the evaluation results are shown in [1].
The output of search engines is usually formatted as page titles and mechanically generated excerpts. Such representation fails to well support user in assessing relevance. Textual summaries adequately generated in response to the query would be more preferable, however this approach has not been fully established. A better display could also be achieved via graphical representation. We applied our Graph-based model for generating a graphical digest representation of a searched document. The resulting graph, called "Digest Graph" is a subgraph of the Subject Graph for the entire document. The subgraph is generated on the fly in response to the current query. A search results page from our Web search engine based on the proposed method is depicted in Figure-2. A user can intuitively and immediately understand the subject of each document from the terms and the term-term associations in the graph.
In this paper, we showed that our Graph-based text representation model could improve the effectiveness of Web search by Subject Graph Matching. This model also improves the efficiency of Web search by providing Digest Graphs to the user; the graphs are generated on the fly in response to the user query. The Digest Graph can be further utilized for relevance feedback by extracting feedback terms from it. To further enhance the performance of the model, a scheme to assign weights to terms and term-term associations is crucially important, and will be investigated.