Typically search engine results (SERs) are presented in a ranked list of decreasing estimated relevance to user queries. While familiar to users, ranked lists do not show inherent connections between SERs, e.g. whether SERs are hyperlinked or authored by the same source. Such potentially useful connections between SERs can be displayed as graphs. We present a preliminary comparative study of ranked lists vs graph visualisations of SERs. Experiments with TREC web search data and a small user study of 10 participants show that ranked lists result in more precise and also faster search sessions than graph visualisations.
Typically search engine results (SERs) are presented in a
ranked list of decreasing estimated relevance to user queries.
Drawbacks of ranked lists include showing only a limited
view of the information space, not showing how similar the
retrieved documents are and/or how the retrieved
documents relate to each other [
We present a user study comparing ranked list vs graphbased SER visualisation interfaces. We use a web crawl of ca. 50 million documents in English with associated hyperlink information and 10 participants. We nd that ranked lists result in overall more accurate and faster searches than graph displays, but that the latter result in slightly higher recall. We also nd overall higher inter-rater agreement about SER relevance when using ranked lists instead of graphs. 2.
While traditional IR systems successfully support
knownitem search [
Earlier work on graph-based SER displays includes Beale
et al.'s (1997) visualisation of sequences of queries and their
respective SERs, as well as the work of Shneiderman & Aris
(2006) on modelling semantic search aspects as networks
(both overviewed in [
This section presents the two di erent SER visualisations used in our study. Our goal is to study the e ect of displaying exactly the same information to the user in two di erent ways, using ranked list and graph visualisations, respectively. 1 docid 2 docid 3 docid 4 docid 5 docid 6 docid (A) 5 3 2 (B) 4 6 1
We use a standard ranked list SER display, where documents are presented in decreasing order of their estimated relevance to the user query. The list initially displays only the top-k retrieved document ids (docids) with their associated rank (see Figure 1 (A)). When clicked upon, each document expands to two mini windows, overlaid to the left and right of the list:
The left window shows a document snippet containing
the query terms. The snippet provides a brief
summary of the document contents that relate to the query
in order to aid the user to assess document relevance
prior to viewing the whole document [
The right window shows a graph of the top-k ranked SERs (see Section 4.2). The position of the clicked document in the graph is clearly indicated, so users can quickly overview its connections, if any, to other top-k retrieved documents.
Previously visited documents in the list are colour-marked. 4.2
We display a SER graph G = (V; E) as a directed graph whose vertices v 2 V correspond to the top-k retrieved documents, and edges e 2 E correspond to links (hyperlinks in our case of web documents) between two vertices. Each vertex is shown as a shaded circle that displays the rank of its associated document in the middle, see Figure 1 (B). The size of each vertex is scaled according to its out-degree, so that larger vertex size indicates more outlinks to the other top-k documents. Edge direction points towards the outlinked document. Previously visited documents are colourmarked.
When clicked upon, each vertex expands to two mini windows, overlaid to the left and right of the graph: The left window shows the same document snippet as in the RL display.
The right window shows the ranked list of the top-k SERs. The position of the clicked document in the list is clearly marked.
We display the SER graph in a standard force-directed
layout [
Both the RL and GR interfaces include short query-based summaries of the top-k SERs (snippets). We construct them as follows: We extract from each document a window of 25 terms surrounding the query terms on either side. Let a query consist of 3 terms q1; q2; q3. We extract snippets for all ordered but not necessarily contiguous sequences of query terms: (q1; q2; q3), (q1; q2), (q1; q3), (q2; q3), (q1), (q2), (q3). This way, we match all snippets containing query terms in the order they appear in the query (not as a bag of words), but we also allow other terms to occur in between query terms, for instance common modi ers.
Several snippets can be extracted per document, but only the snippet with the highest TF-IDF score is displayed to the user. The TF-IDF of each window is calculated as a normalised sum of the TF-IDF weights for each term: Ss(D) = 1 jwj
X tf (t; D) log
jwj t=0
jCj
jD 2 C : t 2 Dj
where jwj is the number of terms in the window extracted,
t 2 w is a term in the window, tf is the term frequency of t
in document D from which the snippet is extracted, C is the
collection of documents, and Ss(D) is the snippet score for
document D. Finally, as research has shown that query term
highlighting can be a useful feature for search interfaces [
We recruited 2 participants for a pilot study to calibrate the user interfaces; the results from the pilot study were not subsequently used. For the main study, we recruited 10 new participants (9 males, 1 female; average age: 33.05, all with a background in Computer Science) using convenience sampling. Each participant was introduced to the two interfaces. Their task was to nd and mark as many relevant documents as possible per query using either interface. For each new query, the SERs could be shown in either interface. Each experiment lasted 30 minutes.
Participants did not submit their own queries. The queries were taken from the TREC Web tracks of 2009-2012 (200 queries in total). This choice allowed us to provide very fast response times to participants (< two seconds, depending on disk speed), because search results and their associated graphs were pre-computed and cached. Alternatively, running new queries and plotting their SER graphs on the y would result in notably slower response times that would risk dissatisfying participants. However, a drawback in using TREC queries is that participants did not necessarily have enough context to fully understand the underlying information needs and correctly assess document relevance.
Ranked List 0.4195 0.4698 0.0067
To counter this, we allowed participants to skip queries they were not comfortable with. To avoid bias, skipping a query was allowed after query terms were displayed, but before the SERs were displayed.
We retrieved documents from the TREC ClueWeb09 cat. B dataset (ca. 50 million documents crawled from the web in 2009), using Indri, version 5.2. The experiments were carried out on a 14 inch monitor with a resolution of 1400 x 1050 pixels. We logged which SERs participants marked relevant, as well as the participants' click order and time spent per SER.
In total the 10 participants processed 162 queries (89 queries with the RL interface and 73 with the GR interface) with mean = 16.2, and standard deviation = 7.8. Four queries (two from each interface) were bypassed (2.5% of all processed queries).
Table 1 shows retrieval e ectiveness per interface, aggregated over all queries for the top k = 20 SERs. The ranked list is associated with higher, hence better scores than the graph display for MAP and MRR. MAP is +30.6% better with ranked lists that with graph displays, meaning that overall a higher amount of relevant SERs is found by the participants at higher ranks in the ranked list as opposed to the graph display. This nding is in agreement with the MRR scores, which indicate that the rst SER to be assessed relevant is likely to occur around rank position 2.13 (1=2:13 = 0:469 0:4698) with ranked lists, but around rank position 2.55 (1=2:55 = 0:392 0:3948) with graph displays. Conversely, recall is slightly higher with graph displays. In general, higher recall in this case would indicate that participants are more likely to nd a slightly larger amount of relevant documents when seeing them as a graph of their hyperlinks. However, the di erence in recall between ranked lists and graphs is very small and can hardly be seen as a reliable indication. 5.1.1
On average participants clicked on 9.46 entries per query in the ranked list (842 clicks for 89 queries) but only on 6.7 entries per query in the graph display (490 clicks for 73 queries). The lower number of clicks in the latter case could be due to the extra time it might have taken participants to understand or navigate the graph. This lower number of clicks also agrees with the lower MAP scores presented above (if fewer entries were clicked, fewer SERs were assessed, hence fewer relevant documents were found in the top ranks).
Figures 2a and 2b plot the order of clicks for the ranked list and graph interfaces respectively on the x-axis, against the frequency of clicks on the y-axis. We see that in the ranked list, the rst click of the participant is more often on a relevant document, but in the graph display, the rst click is more often on a non-relevant document (as already indicated by the MRR scores shown above). We also see 30 y c n ue20 q e r F 10
Relevant Not relevant Relevant
Not relevant 00 5 10 15 Click2o0rder 25 30 35 40
(a) 00 5 15
20 10 Click order (b) that for the graph display, the majority of participant clicks before the 5th click correspond to non-relevant documents. Even though the MRR scores of the graph display indicate that the rst relevant document occurs around rank position 2.5, we see that participants on average click four other documents before clicking the relevant document at rank position 2.5. This indicates that in the graph display, participants click documents not necessarily according to their rank position (indicated in the centre of each vertex), but rather according to their graph layout or connectivity.
To investigate how consistent participants were in their
assessments, we report the inter-rater agreement using
Krippendor 's [
The average inter-rater agreements between participants vary considerably. For the graph interface, = 0:04471, which suggests lack of agreement between raters. On a query basis, some queries (query 169 and 44) suggest a comparatively much higher agreement whereas others (e.g. query 104 and 184) show a comparatively higher level of disagreement. For the ranked list, inter-rater agreement is higher ( = 0:19813). On a per query basis, quite remarkably, query 92 had a perfect agreement between raters, while queries 175 and 129 also exhibited a moderate to high level of agreement. However, most queries show only a low to moderate level of agreement or disagreement.
Overall, the lack of agreement may indicate the participants' confusion in assessing the relevance of SERs to pretyped queries. This may be aggravated by problems in rendering the HTML snippets into text. Some HTML documents were ill-formed, hence their snippets sometimes included HTML tags or other not always coherent text.
Inter-rater agreements between our participants and the TREC preannotated relevance assessments show an almost complete lack of agreement. For both interfaces there is a weak level of disagreement on average ( = 0:0750 and = 0:0721 for the graph and ranked list respectively). On a per query basis there are only two queries (queries 169 & 110) exhibiting a moderate level of agreement. For most remaining queries our participants' assessments disagree with the TREC assessments.
Query 101 104 132 169 180 184 3 38 44 58 { { { { { { { {
Graph Raters 4 0.28696 2 -0.21875 2 -0.16071 2 0.48000 2 -0.10031 2 -0.25806 2 0.00000 2 -0.07519 2 0.49351 2 0.00000 { { { { { { { { { { { { { { { { Average : 0.04471
In a small user study, we compared ranked list versus graph-based search engine result (SER) visualisation. Our motivation was to conduct a preliminary experimental comparison of the two for the domain of web search, where document hyperlinks were used to display them as graphs. We found that overall more accurate and faster searches were done using ranked lists and that inter-user agreement was overall higher with ranked lists than with graph displays. Limitations of this study include: (1) using xed TREC queries, instead of allowing users to submit their own queries on the y; (2) having technical HTML to text rendering problems, resulting in sometimes incoherent document snippets; (3) using only 10 users exclusively from Computer Science, which makes for an overall small and rather biased user sample; (4) not using the wider context of the search session in the analysis (e.g. user task, behaviour, satisfaction). Future work includes addressing the above limitations and also testing whether and to what extent these results apply when scaling up to wall-sized displays with signi cantly larger screen real estate. 7.