For each search result presented by a search engine, a user has a choice to click through for more information or to skip the result. We aim to improve the accuracy of this click process by introducing a color-coding scheme built upon our improved summary text selection approach called ReClose. Color-coding adds an additional level of context to the text without requiring additional screen space. Our results showed an improvement in click precision from 66% when using Google summaries to 80% when using colorcoded ReClose summaries. Improvements in user click precision will lead to better user experiences, the more e cient nding of search results and higher con dence levels in search engine usage.
Search engine usage has become a part of every day life for internet users. Every time a search is conducted on Google or Bing a list of search results is presented to the user. One of the major challenges that users face as they search for that needle of information in the Internet haystack is deciding which of the search results presented is relevant to their search needs and which are not. When conducting searches for facts and information the choices are not always obvious.
Each search result is composed of a title, a short text summary and an abbreviated URL. The title usually is revealing about the overall message of a web page. However, it is written by the web content creator and may be a slogan of a company or an advertising pitch, which can be misleading. The URL can be very helpful when one is familiar with the host contained in the URL, but many URLs encountered are not familiar to us.
The text summary is extracted from three possible
locations [
Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$10.00. tion of a web page or web site hand written by the content creator. 3) Lastly the text could come from the Open Directory Project (http://www.dmoz.org). The Open Directory Project is a community built directory of websites with a number of short, human-written website summaries.
When search results are presented to users, the user has
the task of deciding which results are relevant to their search
and which are not. Within information science it has been
found that as many as 80 factors contribute to the decision
of judge deciding which documents are relevant to a
particular search [
Users may incorrectly skip relevant content missing out on potentially important information, but it is the feeling of disappointment (possibility 1) that will most negatively a ect a search experience. We aim to improve the user's accuracy in click decisions for the purpose of decreasing occurrences of disappointment.
As an example of the kinds of disappointment that may be realized consider the search result to the query closeness centrality pictured in Figure 1. Closeness centrality is a graph theory measure used for ordering nodes. The search result shown in Figure 1 has a title of \Social Network Analysis". This page is dedicated to the analysis of social networks. Closeness centrality as is shown in the summary is clearly mentioned. One also nds an example description of closeness centrality in a social network. One may expect that this page contains a lengthy description of closeness centrality followed by this example. However, clicking through to the result page leads to Figure 2. The web page does discuss social network analysis as would be expected by the title, but there is only a single paragraph on closeness centrality. This single paragraph only describes a brief example barely longer than the text summary given by the search result. This web page did not meet the previously detailed expectations and would lead to disappointment on the part of the searcher.
The user in the previous search example would be aided by the two main features of color-coded ReClose summaries. First, keywords are highlighted with color depth to provide global context rather than just the local context of one or two sentences surrounding a keyword. This \global context" refers to the extent of discussion on a web page containing the query topic. In the previous example, the user would have been aware before clicking that there were very few occurrences of the terms \closeness" and \centrality" by visual clues of color enhanced query keyword highlighting.
Secondly, major departures from the main topics of a web search are agged. If the main subject of a web page is di erent from the intent of the search user, then a topic term is shown in red. This warns the user that the keywords may be peripheral to the main subject of the web page. Both color depth and topic word agging are shown in this paper to e ectively improve user click precision and decrease user disappointment. This in turn will improve the e ciency of the user and lead to better user experiences with the search engine.
The highlighting of keywords has been used in a number of
settings where users scan documents or lists of documents.
Highlighting attracts the user's attention to these keywords
using bolding, reverse video or coloring the background of
the text. In each case it has been shown to be useful to the
scanning and examination of documents and document lists
[
A number of useful approaches exist for highlighting
keywords. Baudisch et al. [
Veerasamy and Belkin [
Kaugars [
Hemmje et al. [
Keyword highlighting has improved information retrieval
result scanning for more than 25 years [
The goal of color-coded ReClose summaries is to increase
the accuracy (precision) with which users click on search
results to nd relevant documents. Increasing accuracy will in
turn lead to fewer disappointments and a better user
experience. Color-coded ReClose summaries aim to improve upon
current search result summaries using three main parts. First,
we build upon our previous work on text summary
generation approach called ReClose [
The ReClose approach [
Query-independent summarization is achieved using
closeness centrality [
The second part of the ReClose approach involves learning from the summary generation techniques of the top ranking search engines, namely Google, Yahoo and Bing. To improve upon the query-biased summaries of current search engines, we learn from the summaries generated by all three top search engines. We generated training data by observing which sentences were chosen by each of these search engines. We trained a linear regression model to score sentences to match the sentence selection of Google, Yahoo and Bing. After training, a new document is split into sentences and each sentence is ranked by the linear regression model. The top ranking sentences are chosen to represent the query-biased portion.
In this way we now have a two part summary taking advantage of both query-biased and query-independent approaches to summary generation. Each portion of the summary is labeled so that users of the summaries are aware of the di erent intentions with each of the two text spans. 3.2
We color-code keywords to provide additional context about the usage of keywords. The query-biased summaries of say Google or Bing will provide one or two text spans generally that show one or two usages of the keywords searched. In this way the context on a scale of say plus or minus ten words from the keywords are shown. Our color-coding of the keywords adds depth to each keyword just as colors can provide terrain depth on a topographical map. Many topographical maps will provide a key that shows the elevation range of the map and provide di erent colors for each subdivision of elevation. This \color-coding" provides users of these maps a more intuitive view than simply a set of contour lines to understand depth. Our depth refers to the frequency of query keywords on a web page. This gives a user a greater appreciation for how long discussions involving the keywords may be compared to other search results.
The key used in our surveys is shown in \Select Color" step of Figure 3. We count the frequency of each keyword on a web page after the removal of stop words and use of Porter stemming. Then for each possible frequency between zero and 63 a di erent shade of blue is used. (A keyword may be contained in a summary and not on a web page if it is contained in the meta description but not the web page's content). A diagram of color-coding query keywords is shown in Figure 3. Now summaries of web pages that talk at great lengths about say \canines" will be distinguishable from a web page that has very little text which mentions \canines".
The exact colors used are in Table 1. We chose to use a light blue (deep sky blue) for the smallest frequency value of zero. Then to make the range between 0 and 30 more pronounced we chose an intermediate, but fairly dark blue (Egyptian blue) at a frequency of 30. A dark blue (Duke blue) was used for a frequency of 63+ which was still distinguishable from regular text in black. To calculate the RGB values for frequencies in between these speci c values, one divides the di erence in color values by the number of di erent frequencies.
It is unlikely that most users will be able to know exactly what color represents which frequency, but it will be obvious which summaries contain more frequent keywords. For example in the summary in Figure 3 the keyword \database" is more frequent in the document than the keyword \building". It will also be obvious which end of the scale each keyword
Once we have determined the most frequent term in a document, we then consider all other top ranking documents returned for the search (step 2). In our case we used the top 28 documents (not including the current document), since this is the maximum number of documents returned through Google's Web Search API (http://code.google.com/apis/ websearch/).
The percentage of top ranking documents for the current search containing the most frequent term is then thresholded (step 3). We used a threshold of 60%. Terms that occur in more than half of the top documents for a search generally are highly related to the search terms. As an example consider the terms by percentage for the query algorithms. Terms above the 60% threshold include: \algorithms" at 100%, \computer" at 80% and \number" at 60% which are all related to algorithms. Examples of terms below the threshold are \privacy", \course", \heap" and \2007" with only \heap" being a term associated with algorithms. Terms found in 60% of documents are both rare and highly related.
Terms that do not meet the threshold will be displayed in the summary colored red. For example see the summary in Figure 4 where the term \JDBC" is agged. JDBC refers to one method in Java for connecting to databases. It is distantly related to the query building a database, but clearly shows that this particular document is less focused on the building of the database, and more focused on Java related issues.
After we have determined that a term should be agged for a particular summary, we must ensure that the agged term is included in the summary. To accomplish this we lter the query-independent sentence ranking to only include sentences including the agged terms. This ensures that the agged term will appear in at least one sentence included in the summary.
We hypothesize that color-coding ReClose generated summaries that users will have more accurate expectations of the web pages summarized. To test this we created a survey that allow us to compare the accuracy of user expectations based on summaries. We mainly compare color-coded ReClose summaries against Google summaries. We additionally compare ReClose summaries with and without colorcoding to ensure that the color-coding made a di erence, and that text selection alone was not the main cause for improvement. 4.1
For our survey we recruited 21 volunteers among undergraduate and graduate students in the Computer Engineering and Computer Science department at the University of Louisville. Surveys were conducted exclusively online.
The summary analysis was broken down into two parts and repeated for each of the three summary techniques under comparison. First a user would be shown 5 summaries for a randomly selected query. For each summary a user would mark if they would click on that summary. Then they would mark the amount of relevant content expected. The choices available were \None", \Sentences", \Paragraphs", \Pages" or \Book". Rather than just obtaining which results a user would click on, we obtain a ner grained understanding of the process through how much relevant content a user t n ouC 04 0 8 0 6 0 2 0
Relevant None
Sent. Para. Pages Relevance Expectations
Book expected.
Second, users were provided links to each destination page and viewed these pages one at a time. A user marked down the actual amount of relevant content using the same options presented for expectations. In this way rather than nding out if a user believes a page is relevant or not to their search, we can also monitor lesser disappointments, such as a user expecting to nd pages and pages of relevant content but in actuality only nding a couple of sentences. In this case the document is still relevant, but the user is likely not satis ed with the results.
Survey participants were shown 5 summaries per summary type for a total of 15 summaries. 4.2
Survey participants were randomly assigned three queries out of a pool of 15 queries. These queries were chapter titles and project titles from an introductory course in computer science so that all query topics were familiar to the survey participants. Some example queries were logic gates and creating a web page.
For each of the 15 queries, 28 search results were obtained from Google. We downloaded each linked web page in the search results resulting in 400 successfully downloaded and parsed web pages out of 420 possible. We only used 5 search results per query. To decide which search results to use, we randomly selected web pages from two pools. The rst pool was likely to have search results with agged summaries because when the frequencies of terms in a document was ranked the query keywords had a low rank. The second pool contained the top 5 search results as ranked by Google.
After determining the pool of search results most likely to be agged and the top Google search results, randomly we select 2-4 results from the pool of results likely to be agged. Then the remaining results are taken starting starting with the top ranked Google result from the second pool. 4.3
First we verify the relationship between user click behavior and the relevance markings. Figure 5 shows the distribution of expected relevance for search results clicked and skipped. This gure shows that no user would click on a result if they expected no relevant content. If a user expected only a sentence or two of relevant data, users were unlikely to click (72% or 64/89). A natural division emerges from the expectation results. Users expecting \Sentences" or \None" would skip the result 82% (116/141) of the time, leading us to call this section \irrelevant". The other half of the relevant spectrum we labeled \relevant". Users clicked through 84% (146/174) of the time when expecting \Paragraphs" or more of relevant information. Performing a 2 test on the count data revealed by this dividing line resulted in 2 value of 134.8 and a p-value < 0.001, clearly showing a signi cant di erence between these two groups. Click through and expectation have a lot in common, but expectations provide more insight into the mental process of the search users.
The expectations of survey participants was fairly inaccurate. Only 34% (108/315) of expectations matched exactly the actual relevant content of web pages. In another 34% (108/315) of expectations resulted in actual content being opposite of expectations in terms of the relevant/irrelevant split mentioned earlier. For example there were 16 occurrences where a survey participant marked a relevant expectation of \Paragraphs" or higher only to nd no relevant content.
In our survey color-coded ReClose summaries achieved a much lower percentage of disappointment at 23% than Google summaries achieved at 34% as shown in Table 2. Disappointment was recorded when the relevant content was lower than what their expectations. When we conduct a 2 test on the count data comparing Google and color-coded ReClose we obtain a 2 value of 2.8 and a p-value of 0.09. This p-value does not fall below the usual threshold value of 0.05. However, there still remains an obvious di erence between the results of Google summaries and color-coded ReClose summaries that would become more pronounced with the additional survey participants. We now look at the precision with which users chose to click on a result. Considering that a majority of users did not click when expectations were a couple sentences or less, we label all web page views with a few sentences or less of relevant content as \irrelevant." Survey participant marking more than a few sentences worth of relevant content are labeled as \relevant." Dividing clicks into relevant and irrelevant allows for us to calculate click precision. We dene click precision as the percentage of summary views with clicks that led to relevant web pages. Click recall is the percentage of relevant documents that were clicked. The results of these calculations for each summary technique can be seen in Table 3.
Table 3 shows that users clicked more often (61 times) and had a higher click precision (80%) when using colorcoded ReClose summaries than either Google (66%) or ReClose summaries highlighting with bold (75%). When users used Google summaries they clicked through to relevant web pages only about 2/3 of the time that they clicked. With more precise clicks, users using color-coded ReClose summaries also clicked on more of the relevant content having a click recall score of 70%. Individuals using Google and bolded ReClose summaries skipped more relevant content having recall scores of 60% and 64% respectively.
In practice a higher click precision will be more noticeable to users. Users are aware of clicks to irrelevant content, experiencing disappointment. However, there is no form of feedback for click recall. Users are not aware that they have skipped over a relevant document. One of the main objectives of color-coded ReClose summaries was to improve the click precision for users. From the numbers in Table 3 it is clear that color-coded ReClose summaries improve the precision of users, both over Google summaries and ReClose summaries without color-coding. This leads to fewer disappointments in practice. 4.4
We now consider the e ectiveness of the two color-coding features: color-coded keywords and agged words. In this section comparisons are only made between bolded and colorcoded ReClose summaries. You can be assured both outperformed Google summaries, but here the focus is just on the added color-coding features. We rst consider the colorcoded keywords. The scale we used allowed for usage count di erentiation from 0-63. Summaries were not evenly distributed across this range. Nearly half (49% or 37/75) of the summaries used had at most a keyword with 0-9 usages on the web page summarized. We would expect that users would have low expectations for summaries that at most contained keywords on the low end of the scale. Looking at the results, there was no perceived change in behavior for summaries containing low count query keywords (0-9) to medium count (10-59). Only in the case of high count query keywords (60+) was there a noticeable change in behavior.
There were 13 summaries (17%) with at least one query keyword with a usage count of 60+. For these 13 summaries, participants found the actual relevant content to be high. For example no matter the summary type, more than 50% of views led to actual relevant content in the \Pages" level. This was rarely expected when using bolded ReClose summaries, see Table 4. Bolded ReClose summaries led to 23% of pages views in the \Pages" level expectations. The color-coded ReClose summaries more often led to higher expectations in line with the actual content. In 44% of views, color-coded users identi ed an expectation in the \Pages" range. Color-coded ReClose summaries also led to the highest actual relevant content as well at 67%. In the case of high usage count keywords, color-coded ReClose summaries led to justi ably higher expectations.
First we compare the e ect that agging had on expectations which can be seen in Table 5 in the column marked \Expected Relevant". In this table documents were broken into two groups, documents that had terms agged by color-coded ReClose (rows marked \Flaggable") and documents that did not (rows marked \Not Flaggable"). When color-coded ReClose summaries had agged terms, the expectations were much lower (29% expected to be relevant) than those same summaries without color-coding (40% expected to be relevant). A similar pattern was found for color-coded summaries without agged terms having higher expectations. This shows that the agging of terms directly a ected the expectations of the user. There is a much lower percentage of documents found to be relevant that had agged terms. Even in the case where agged terms were not shown to users (bolded ReClose summaries), 45% of documents that could have been agged were found to be relevant compared to 71% of documents that would not have had agged terms. What is interesting is how agging a ects the click precision of users. Those that saw the agged terms had a click precision of 57% on agged summaries compared to 70% that did not see the agging for these same summaries. However, users expected more and were more precise when color-coding was available and no agged terms appeared in a summary achieving a click precision of 87% compared to 78% without color-coding. Overall with far fewer clicks among agged summaries, the overall click precision was higher for the color-coded version of ReClose (see Table 3).
In this paper we outline color-coded ReClose summaries. Web-based summaries were visually enhanced using two techniques. The rst technique was to provide global context for the query keywords, by using varying color to highlight these keywords. The second technique highlighted in red terms that topically di ered from the topics of a query. This provided a warning mechanism to aid users avoid clicking through to results less likely to be relevant. We hypothesized that color-coded ReClose summaries would increase the accuracy of user click decisions, thus reducing disappointments and improving user experiences.
Survey results showed that color-coded ReClose summaries (80%) led to an improvement in user click precision over Google summaries (66%). This in turn led to color-coded ReClose summaries resulting in fewer disappointments (24) compared to Google summaries (36). Improved precision and decreased disappointment will result in a better user experience.
A closer look at the survey results showed that both highlighting techniques of color-coding keywords and agging divergent topic terms both were e ective. Color-coding summaries is an e ective way to enhance the summary information to users without increasing the screen space. We plan on making further improvements to the selection algorithm for agged terms. We also plan to enhance summaries with the use of multimedia. 6.