We describe a new paradigm for performing search in context. In the IntelliZap system we developed, search is initiated from a text query marked by the user in a document she views, and is guided by the text surrounding the marked query in that document (“the context”). The context-guided information retrieval process involves semantic keyword extraction and clustering to automatically generate new, augmented queries. The latter are submitted to a host of general and domain-specific search engines. The results are then semantically reranked, again, using context. It is our belief that letting context guide the search provides a better match to the user’s current needs than just relying on the user’s fixed personal profile. Our results show that using context to guide search effectively offers even inexperienced users an advanced search tool on the Web.

Categories and Subject Descriptors
H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval – clustering, query formulation, search process; H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing – dictionaries, linguistic processing, thesauruses; I.7.5 [Document and Text Processing]: Document Capture – document analysis.

General Terms
Algorithms, Performance.

Keywords
Search, Context, Semantic Processing, Invisible Web, Statistical Natural Language Processing.

Given the constantly increasing information overflow of the digital age, the importance of information retrieval has become critical. Web search is today one of the most challenging problems of the Internet, striving at providing users with search results most relevant to their information needs. Internet search engines evolved through several generations since their inception in 1994, progressing from simple keyword matching to techniques such as link analysis and relevance feedback (achieved through refinement questions or accumulated personalization information) [11]. Search engines have now entered their third generation, and current research efforts continue to be aimed at increasing coverage and relevance.

A large number of recently proposed search enhancement tools have utilized the notion of context, making it one of the most abused terms in the field, referring to a diverse range of ideas from domain-specific search engines to personalization. We present here a novel search approach that interprets context in its most natural setting, namely, a body of words surrounding a user-selected phrase. We postulate that a large fraction of searches originate while users are reading documents^[2] on their computers, and require further information about a particular word or phrase. Hence, the basic premise underlying our approach is that searches should be processed in the context of the information surrounding them, allowing more accurate search results that better reflect the user’s actual intensions. For example, a search for the word “Jaguar” should return car-related information if performed from a document on the motoring industry, and should return animal-related information if performed from an Internet website about endangered wildlife. Guiding user’s search by the context surrounding the text eliminates possible semantic ambiguity and vagueness.

Our system (named IntelliZap) is based on the client-server paradigm, where a client application running on user’s computer captures the context around the text highlighted by the user. The server-based algorithms analyze the context, selecting most important context words and performing word sense disambiguation, and then prepare a set of augmented queries for subsequent search. The technology also enables the user to modify the extent to which context guides a specific search, by modifying the amount of context considered. Queries resulting from context analysis are dispatched to a number of search engines, performing meta-searching. When the context can be reliably classified to a predefined set of domains (such as health, sport or finance), additional queries are dispatched to search engines specializing in this domain. This step can be viewed as referring to the Invisible Web, as some of the target domain-specific engines may constitute front-ends to databases that are not otherwise indexed by conventional search engines. A dedicated reranking module ultimately reorders the results received from all the engines, according to semantic proximity between their summaries and the original context. To this end we use a semantic metric that given a pair of words or phrases returns a (normalized) score reflecting the degree to which their meanings are related.

The significance of the new context-based approach lies in the greatly improved relevance of search results. We achieve this by applying natural language processing techniques to the captured context in order to guide the subsequent search for user-selected text. Existing approaches either analyze the entire document the user is working on, or ask the user to supply a category restriction along with search keywords. As opposed to these, the proposed method analyzes the context in the immediate vicinity of the focus text. This allows analyzing just the right amount of background information, without running over the more distant (and less related) topics in the source document. The method also allows collecting contextual information without conducting an explicit dialog with the user.

This paper is organized as follows. The next section reviews related work. Section 3 presents the various features of our context-based search system, explaining how several individual algorithms work in concert to improve the relevance of the search. Section 4 discusses the experimental results. Finally, Section 5 concludes the paper and suggests further research directions.

Using context for search is not a new idea. A number of existing information retrieval systems utilize the notion of context to some extent. The problem is, however, that everyone defines context a little differently.

Lawrence [8] contains an elaborate review of using context in Web search. Explicit context information can be supplied to a search engine in the form of a category restriction^[3]. Such a category may considerably disambiguate a query and thus focus the results. For instance, given the search term “jaguar”, possible categories are “fauna” or “cars”. Inquirus-2 project [7] specifically requests context information in this way.

In contrast to this approach, other tools infer context information automatically by analyzing whole documents displayed on users’ screens. The Watson project [2] attaches this background information to explicit user queries, while tools like Kenjin^[4] automatically suggest Web sites related^[5] to the document being worked upon. Such tools encounter difficulties when documents are long and discuss a variety of topics – as the data collected from the entire document reflects all the topics covered, it might not be particularly relevant to the user’s current focus (be it an explicit query in the former case, or simply the active part of the document in the latter). The main difference between such tools and our IntelliZap is that the latter analyzes the context in the immediate vicinity of the user-selected text, thus making the context coherent and focused around a single topic. In the other end of the spectrum, tools like GuruNet (now Atomica^[6]) offer database lookup directly from reference sources (dictionaries, encyclopedias etc.). Such tools offer only a limited usage of text, without deep semantic analysis of the enclosing context.

There is a family of tools that interpret the notion of context as a set of previous information requests originated by a user. Defined this way, context search becomes personalization, and tools in this category keep track of user’s previous queries and/or documents viewed. SearchPad [1] recognizes that many advanced users perform several searches concurrently, and tracks search process over time. This extension to search engines keeps track of “search context” by following the different search sessions and collecting “useful queries and promising results links” [1].

Other ways of incorporating context into search include the usage of domain-specific rather than general-purpose engines [8]. Databases which belong to the Invisible Web (i.e., whose contents are not indexed by conventional search engines) may be particularly useful as they might contain vast amounts of information within their narrow domain. IntelliZap pursues a similar approach by classifying the topic of the query context, and targeting search engines specializing in the corresponding domain. Note that this way the selection of specialized search engines is performed automatically.

Yet another interpretation of context belongs to the realm of link analysis [12, 13]. In the quest to expand the coverage, some engines intentionally limit the number of sites they index to make the retrieval efficient, but can still yield “unindexed” sites in search results. This is achieved by analyzing the context of links pointing at these sites, thus deducing information about the contents of the target. Google and Inktomi^[7], among others, employ this technique. Another context-related feature of Google shows up in its search-dependent result summaries. A typical Google summary contains an excerpt from the Web page where the search terms are shown highlighted in the context of this page [14].

In contradistinction to this variety of interpretations of context usage in search, our approach focuses on using the context in its most natural sense – that of the text surrounding the marked query, providing local semantic consistency for its interpretation.

Current approaches to information retrieval over the Web are based on a scenario in which the user enters a query to a search engine. The search engine then retrieves a set of ordered documents that best match the user's query. We propose an approach that changes the basic settings of the search scene by using the context of the query as an additional input. In this scenario, when a user marks a text in a document and submits it for search, the system captures the context surrounding the text, and utilizes it to yield more focused results. The context may include the sentence containing the query word or phrase, a few sentences surrounding the query term, the paragraph in which it resides, or even the whole document.

Using the context for superior search focus constitutes a considerable algorithmic challenge. One needs to find ways to extract the right amount of context which best optimizes the information retrieved, as well as devise adequate ways to use the context extracted for focusing the response to the original query.

Apparently, the simplest way to do so is to concatenate the selected text and the captured context into a uniform query, which can be sent to search engines. However, this approach does not perform satisfactorily. First, most search engines cannot handle large chunks of natural language text. Second, blindly concatenating long context with relatively short text might cause search results to become greatly unfocused.

In what follows, we describe two fundamental approaches to building augmented queries using contextual information. The next section outlines two relatively simple heuristic techniques. The section that follows presents more powerful query augmentation methods, which identify the most important context words to guide the subsequent information retrieval process.

We evaluated two classes of heuristics. Each of them receives as input the marked text and its context captured from some application.

We discovered that the context length should be commensurate with the text length, and with the relative frequencies of text words. That is, the more frequent a text word is, the less information it likely carries and the larger context should be supplied to focus the search.

Weighting is performed by word duplication, requiring certain words (estimated to carry substantial amount of information) to appear in titles of retrieved documents, as well as by using Boolean operators (AND, OR, NEAR etc.). In general, such operators emphasize the marked text phrase in the augmented query built, and make the weight of context words in the augmented query a monotonic function of their proximity to the text phrase.

Figure 1 shows an example of query augmentation using the heuristics. The heuristic approach yielded a certain improvement in the relevance of the information retrieved to the user's interests, and served as an encouraging example of the potential of utilizing context to guide information search. Yet, further significant improvement is possible by pursuing a more general approach, which utilizes background linguistic information and does not depend on the specific syntax of search engines input, i.e., does not require the knowledge of the specific operators recognized by each potential target search engine.

3.2 Linguistic CBS System

3.2.1 Overview

3.2.2 The Core Semantic Network

1. Extracting keywords from the captured text and context.
2. High-level classification of the query to a small set of predefined domains.

3.2.3 Keyword Extraction Algorithm

3.2.4 Search Engine Selection

3.2.5 Reranking

4. Experimental Results

4.1 Context vs. Keywords: A Quantitative Measure

4.2 IntelliZap vs. Other Search Engines: An Unconstrained Example

4.3 Response time

5. Discussion

References

Vitae

---