When people search for information, they often run multiple queries to get at different aspects of the information need, to gain a better understanding of the collection, or to incorporate newly-found information into their searches. This too is not news.

The multiple queries that people run may well retrieve some of the same documents. In some cases, there may be little or no overlap between query results; at other times, the overlap may be considerable. Yet most search engines treat each query as an independent event, and leave it to the searcher to make sense of the results. This, to me, is an opportunity.

Design goal: Help people plan future actions by understanding the present in the context of the past.

While web search engines such as Bing make it easy for people to re-visit some recent queries, and early systems such as Dialog allowed Boolean queries to be constructed by combining results of previously-executed queries, these approaches do not help people make sense of the retrieval histories of specific documents with respect to a particular information need. There is nothing new under the sun, however: Mark Sanderson’s NRT system flagged documents as having been previously retrieved for a given search task, VOIR used retrieval histograms for each document, and of course a browser maintains a limited history of activity to indicate which links were followed.

Our recent work in Querium (see here and here) seeks to explore this space further by providing searchers with tools that reflect patterns of retrieval of specific documents within a search mission.

• Is a particular document central to a given information need?
• Is this the first time this document has been retrieved?
• Have I ever seen this document before?
• Is this query breaking new ground, or largely just re-ranking previously-retrieved documents?

Querium includes several visualizations to help answer these and related questions. These include histograms that display the retrieval history of each document, filters that allow documents to be selected based on whether they were previously retrieved, clicked on, etc., and a query-centric overview of search results.

Histograms

Querium keeps track of the top 100 documents retrieved by each query; a simple inversion associates each document with the queries that retrieved it. Whenever a search result is displayed, it is accompanied by a histogram that shows its retrieval history:

The histogram on left, for example, shows that the document in question was retrieved three times out of the four queries that were run, that it was ranked lower in query 2 than in queries 1 and 3, and that it was retrieved by more than one person (the colors represent different collaborators).

This histogram, on the other hand, shows that the document has only been retrieved once, and was highly ranked. Thus given a series of documents retrieved by a query, the searcher can quickly tell which documents are new, which ones have been seen before, etc.

Filtering

In addition to aggregating metadata from retrieved documents to generate filtering facets, we can aggregate process metadata derived from retrieval patterns within a search mission. We have decomposed process metadata in three facets: retrieval, viewing, and assessment. Retrieval counts how many times a document has been retrieved, viewing counts how many snippets were viewed and how many were clicked on to show the full document, and assessment counts documents that were explicitly bookmarked (positive assessment), or marked as not useful (negative assessment). We can also filter based on the identity of the person running the query.

These counts form the basis of filtering operations that can be used to surface as-yet-unexamined documents, to highlight documents that represent recurring themes in the searches, and to review key information that has been identified for a given information need. And of course they can be combined with document metadata for more precise explorations.

Query overview

Finally, we can display the overall retrieval history of a mission by looking at the queries as a whole. For each query, we show a symbolic representation of each retrieved document (a rectangle), decorated to reveal its history of interaction. The decorations indicate whether the document has been viewed (grey box), clicked on (grey lines), assessed positively (green lines), negatively (red lines), or used as part of a relevance feedback query (checkmark). The screenshot fragment below shows such a view:

As the searcher mouses over each document, all other retrieval instances are highlighted with a black border to show that a document may have been retrieved by other queries.

All of these techniques are designed to help people understand how a particular set of results relates to previous activity within the search task. We are in the process of evaluating the system to see which aspects we got right and which ones need more work. In particular, it will be interesting to see if making these patterns of retrieval visible will affect people’s perceptions of their search activity.

To this end, this year’s event has been expanded to two days to allow more time for presentations and for discussion. In addition to the position papers and challenge reports from previous years, we are introducing a new submission category, the archival paper. Archival papers will be peer-reviewed to a rigorous standard comparable to first-tier conference submissions, and the accepted papers will be published on arXiv.org and indexed in the ACM Digital Library.

The goal of this experiment is to grow a venue for publishing original, high-quality research results that otherwise fall into the cracks between the CHI and SIGIR communities. We are sensitive to the issues that cause good papers to be rejected from these venues, and will structure the review process accordingly. And as a bonus, you don’t have to go through ACM’s byzantine copyright and publication process!

Please contact any of the organizers with questions, start working on those papers, and we’ll see you in Cambridge in the fall!

It’s intern season again! I am looking for a PhD student well-versed in persuasive/affective computing/captology literature to participate in a research project related to improving the quality of interaction in information seeking environments. The goal of the project is to explore how to increase people’s engagement with systems while performing exploratory search. We would like to improve our current system to make it more usable and to explore some novel interaction techniques.

Applicants should be familiar with basic tactics of designing affective and engaging interfaces in a web-based environment. The internship will last three months, and will be structured to produce and evaluate research systems. As a further incentive, we expect to publish the results of this work at CHI 2013, which will be held in Paris. For more information on the intern process, please see the FXPAL web site, or contact me directly. I would like to fill this internship slot as soon as possible.

Now imagine that this data is being collected for private use by a company that then uses it for whatever purpose it wants, including giving it up to the government without a warrant. Not the kind of deal anyone would want to sign up for, I assume.

Now stop imagining, because this is happening now: Google, for example, is collecting location data from Android devices and using it against its mapped databases of malls and other public places. Given Google’s record on privacy with books, and email it seems unlikely that it will resist attempts by the government to turn over sensitive data, data that the government would not have had without Google having aggregated it in the first place.

Once the data are aggregated, there is no going back, no easy practical means to prevent it from being used for arbitrary purposes by anyone who can get their hands on it, whether it is our government, or someone else’s.

Today Google is selling your location to advertisers so that they can assault you with ads as you walk by a store. But that same data, properly mined, can be used to surveil you for kidnapping, for example. Seems far-fetch now, perhaps, unless you live in Mexico.

The best way to prevent this kind of information from being used is to prevent it from being collected in the first place.

Searcheeze (which might as well be pronounced Sear-cheeze) is essentially  a shared bookmark site organized around a bookmarklet UI. It lets you organize your snippets into topical categories, and lets you share these with your collaborators. The search part is not actually collaborative at all. In this way it resembles Coagmento much more than SearchTogether or more deeply-mediated tools. These guys went for a “low-hanging fruit” solution, which is a defensible strategy, particularly for new companies. What is much harder to understand is their stupid rhetoric that casts reference librarians as evil hags. (No, I am not making this up! Watch the video on their site!) Not only does it malign a well-respected profession and its practitioners, but, even more bizarrely, their presentation gains no rhetorical advantage from doing so! So I don’t know what these guys are smoking, but they are blowing a lot of it.

SearchTeam seems like a much more solid enterprise, one that actually provides some real support for collaborative search. It also implements UI-level mediation only, but it has a number of additional tools, including within-topic search history, the ability to save or hide search results, to add comments, chat, etc. These tools make it possible to work independently, but also to share your activity with your collaborators. SearchTeam has some nice awareness features that notify you of your collaborators’ activities such as saved documents.

There is still much interaction work remaining to be done:

• For example, the design of the folder view (where saved documents are found) wastes a lot of space, making it difficult to see a reasonable number of documents without a lot of paging. The view also doesn’t highlight newly-added documents, making it hard to recognize changes initiated by collaborators.
• It’s also a bit odd that when you save a document from the search results, its entry is removed from the list. While that does allow the user to focus on what’s left, it doesn’t make for a good sense of progress, and you cannot easily compare the next document snippet you’re examining to some of the ones you’ve just saved.
• Queries are not shared with collaborators until a document is saved, and even then, no notification is generated. Overall, I think the search history deserves more prominence in the UI.
• The chat window obscures a significant part of the workspace, and when put away pops up again immediately with an incoming message. While immediate notification of communication is typically a good thing, it should not interfere with what you’re doing until you’re ready for it.

SearchTeam does not maintain its own index (it probably uses the Bing API), focusing on the interaction instead. The advantage of this approach is that you don’t have to compete with Google and Bing; the disadvantage is that you’re limited by the API of the search provider. This may constrain your ability to do algorithmic mediation, to implement novel ranking or relevance feedback algorithms, etc. It does, however, make it relatively easy to deploy a usable and useful system quickly.

In short, there is more work to be done here, but the first steps are encouraging.

You can search Google Scholar as before, and as before, you get a list of articles that can be filtered by setting the earliest year of publication, and by selecting the kind of publication. The list is sorted by the number of citations, in descending order. You cannot change that.

You don’t get any links to the citations pages of the authors of the retrieved papers, even when the search is for the author’s last name. (I tried mine–it’s always good for these sorts of things.)

Neither do you get access to the metadata that was visible in the Citations page.

Only when you go to advanced search and fill in the ‘author’ field, do you get results that also include the author’s citation page. Filling in the form generates a fielded query (e.g., using the term ‘golovchinsky’ in the author field generates the query [author:golovchinsky]), which then returns a link to the author’s citations page,  in addition to the normal search results. But if you provide two names (e.g., [author:golovchinsky AND author:schilit]) no citation link is generated for either author, although both are present in the Google Scholar Citations database.

On that form, you can also restrict the publication year to a range, specify a subject area, specify more precise term occurrence patterns, including terms that describe the publication venue.

There are several usability problems with this approach:

1. Metadata facets are not discoverable from the initial search. You cannot start with a few keywords (as people often do) and transition smoothly to more elaborate queries.
2. Metadata facets are not available for interactive filtering and sorting of the results. There is no hint from the search results page about which topics, authors, date ranges, etc. are present in the results set, and no facility to filter on them. Hell, you cannot even change the sort order to be in chronological or reverse-chronological order!
3. The citation information is not linked into the results, and not all the authors’ names are shown in the snippet. So you cannot even know who some of the authors were, or find out what other papers they had written, despite the fact that the information is stored explicitly by Google!
4. The snippet doesn’t show the full name of the venue either, so conference names appear in such useful formulations as ‘Proceedings of the eighth ACM conference on…’ or ‘Proceedings of the 13th …’ Google’s attempt at keeping the citation metadata to one line makes the whole thing largely useless.

It’s amazing to me that Google’s matra of keeping the UI simple has actually made the user’s task more complicated! Rather than trying to understand what the users want to do with the tool (or looking at the last 30 years’ worth of publications on information seeking!), the designers of this tool tried to inject the bare minimum of extra query fields, and nothing else. While the minimalist approach might be useful for searching the general web, it is much less likely to be successful for this collection. After all, searching the academic literature is one of the canonical recall-oriented, exploratory search tasks, a veritable poster-child for HCIR!

Here is what I think they need to do to:

1. Read Marcia Bates‘ work on berry-picking.
2. Link the metadata from Citations to the search results. When you click on an author’s name, show that author’s papers, and make them sortable not only by the documents’ metadata (publication year, venue, etc.) but also by relevance to the query that brought the searcher there.
3. In addition to showing the search results, show a list of authors of the retrieved documents, ordered (at least) by the number of papers in the search results.
4. Add facets for the most frequent venues and for subject areas of the retrieved documents.
5. Make the results sortable and filterable by year, citation count, etc., without having to switch to any other page.
6. Make it possible to follow the citation graph in both directions: not only finding the documents that cite a give paper, but also using its references to move backward in time.
7. Integrate a query history into Google Scholar. Think about supporting session search in the interface.

In short, Google seems to have taken the lessons from general web search, and applied them to Google Scholar, with predictable results. Instead, they should look at Google Scholar as an opportunity to learn about HCIR, about exploratory search with long-running, evolving information needs, and to apply those lessons to the web search interface.

So how should we think about evaluating the kinds of searches that take more than one query, ones we might term session-based searches?

This session-oriented search suggests that we need to distinguish between queries and information needs when we talk about interactive search. Thus we have recall- and precision-oriented information needs. What about the queries? Wouldn’t you always want to have precision-oriented queries, giving the person the best information high in the results list?

In an exploratory search task that involves learning about the topic, not every query is intended to find a specific item; some queries are run to understand the field, to learn about the vocabulary, to test hypotheses, to get a sense for the scope of the collection, etc. While these queries may not retrieve any pertinent documents, they may help people understand which queries to run that will in fact find such documents. It might be better, therefore, to have these queries achieve high diversity rather than high precision.

Recall-oriented exploratory search shares the exploratory characteristics of learning and uncertainty with precision-oriented exploratory search, thereby requiring at least some high-diversity queries. In addition, it may benefit from both high-recall and high-precision queries for the various steps along the way.

In short, we have precision-oriented needs that might be satisfied by single high-precision queries (the head of the web search curve), precision-oriented needs that are satisfied through a combination of high-diversity and high-precision queries, and recall-oriented information needs that are satisfied through high-precision, high-diversity, and high-recall queries. Of course we also have straight recall-oriented info needs, which can be tackled one query at a time, or en masse.

We can summarize this as follows: the table shows two dimensions of information need (certainty and scope) and the third dimension of the type of query).

The design challenge for HCIR systems, then, is to diagnose or elicit the kind of information need a searcher has, and to bring to bear the appropriate ranking algorithms to identify results that help the person with the task.

The correlated challenge is how to evaluate session search in a way that doesn’t penalize queries that increase a searcher’s knowledge, but does reward continued progress toward the searcher’s goal. In terms of Marchionini’s keynote chart, we would like to have learning be represented by the green monotonic line, while we would be happy with marginal pertinence jumping around. Increased learning might come from high-precision queries in a known-item information need, but is more likely to result from high diversity and high recall queries.

This analysis suggests (to me!) that while NDCG@3 or precision @5 may be useful metrics for known-item, high-precision information needs, other metrics may be more appropriate for other scenarios.  In a multi-query session, the contribution of individual queries is not as important as the evolution of search process or the final outcome. We should avoid the temptation of computing a Mean Average Precision (where the mean is computed over the queries in the session) or some other similar metric to assess the quality of the interaction.

Instead, we should look to measures of learning (which, admittedly, may be hard to capture in the real world), and use set-based measures related to saved or bookmarked documents to assess the quantity of information that was retrieved. It’s possible that a system design that encourages people to mark useful or pertinent documents may yield log data that is more useful in assessing system (and user) performance compared to designs that only measure click-through rates. (For a nice discussion of one set of such possibilities, see Lad & Tunkelang (2011).)

We can then revisit the information needs described above, with an eye toward metrics:

These are by no means complete, but might be an interesting place to start unpacking recall and precision.

The case study of the Open Video introduced the notion of surrogates, which are representations of metadata designed for human consumption. One significant challenge, particularly for video objects, is to how to evaluate the effectiveness of surrogates. While most evaluations are done as laboratory studies, do these findings retain their validity in naturalistic settings?

The second case study focused on the Relation Browser, a faceted browsing tool. The Relation Browser is designed to reveal relationships across facets, and supports exploration through browsing rather than keyword search. This is a system that has undergone many revisions and redesigns over a decade. The lab’s experience with the project raised several important issues that are applicable much more broadly: how does one capture the design rationale that goes into evolving the system over time? How to show the benefits of HCIR interfaces when users prefer interfaces with which they are already familiar?

The third case study, based on the on-going Results Space project, explored HCIR issues related to surrogates (are there better ways to represent search results than lists of snippets), and touched on issues of awareness in collaborative search.

Having presented the case studies, Gary raised some broader issues for the HCIR field. While he admitted that most of the work that he has been involved with focused on lab studies, he recognized the need for field observations as well. In fact, he suggested that neither approach would be truly useful in isolation. A process that starts with qualitative observations to generate hypotheses that are then tested in the lab is one effective way to integrate the methods, but Gary also raised the possibility of proceeding in the opposite direction.

He also identified the following challenges:

1. Query quality: can we assess the quality of a query, which is often the first signal of user behavior? Can this be done pre-retrieval as well as post-retrieval? How can we elicit human judgments of query quality?

2. Behavior as evidence: what are the various ways in which searchers’ behavior can be converted into implicit relevance feedback? Can we match behaviors to queries to infer what people might be interested in?

3. How do we design and evaluate surrogates that help people perceive, recognize, gist, understand, interpret, analyze and evaluate search results?

4. How do the tools we build affect searchers’ cognitive load? As we add more tools, are we helping or hurting? Does collaboration simply increase the load further without offering tangible benefits, or is there a useful tradeoff?

5. How do we measure session quality and search quality? Recall and precision are point-based measures that don’t capture the process characteristic of session-based search. How do we adapt them to the session as a unit of interaction (as opposed to a query)? What other metrics are appropriate?

6. Finally, he touched on the tricky issue of recording and capturing experimental traces: annotated logs, video recordings, data sets, etc. Should researchers publish traces of system use to characterize participants’ search activities?

The talk also included an interactive interlude, in which Gary showed the audience the following graph:

Slide from Gary Marchionini's HCIR 2011 keynote

The vertical axis was some kind of performance metric, and the horizontal axis represented queries over time. The dashed green line shows steady progress from lower-left to upper-right, while the solid blue line takes a more erratic route between the same starting and ending point. Gary’s question to the audience was which line represented better, or perhaps more desirable, system performance. A number of suggestions were offered, including the benefits of steady progress, of relieving frustration though surprise (the aha! moment reflected in a sharp upward spike of the erratic curve), of achieving maximum performance if only for a short time, etc. There was some consensus that the line that went up and down reflected a learning process that is often characteristic of exploratory search. Which one represents more desirable performance, however, may well depend on the task and the measure selected.

In short, the talk gave a great summary of some accomplishments of HCIR research and of some of the challenges ahead. We expect that next year’s presentations will offer some insights into these thorny issues!

Querium is not a social search tool — you can either use it by yourself, or you can work on an information need with a small number of collaborators. Querium keeps track of the queries you ran, of the documents you found, and the notes you took, and helps you make sense of all that information.

To help us perfect the system, and to help us understand people’s behaviors when collaborating over complex information needs, we are soliciting participants for a beta deployment of about two weeks. We would like to find people who meet the following criteria:

• Who have real information needs with respect to the kinds of documents one might find on CiteSeer
• Who would be willing to use the system over the course of about two weeks, dividing their use into several sessions
• Who would be willing to talk to us on the phone or by Skype about their experiences with the system

We are looking for six to eight teams of two to three people, and also a few individuals working by themselves.

The results of this study will be used to improve the design of the system prior to a long-term deployment, and to write up the work for publication at an upcoming prestigious conference on Human-Computer Interaction. Participants will be able to continue using the system after the initial experiment ends.

Please let me know if you would like to participate or if you have any questions about this research by sending me email.

My co-author, Wolfgang Polak, and I recently received a book review of the sort that is the dream of every author. A dream review is, of course, positive. But more importantly, it praises the aspects of the book that were most important to the author – the reasons the author kept going after other books on the subject came out and the author had a more reasonable (but still too optimistic) estimate of the vast amount of  effort it would take to finish it. (The review appeared in Computing Reviews, but is behind a paywall. Excerpts appear on the book’s Amazon and MIT press web pages.)

In our case,  one of the things that kept us going was that we had specific ideas as to how we wanted to cover a number of topics. While we were writing, I worried each time a new book on quantum computation came  out, but then I’d see that the new book didn’t cover these topics or didn’t cover them in the way we had in mind. One of the thrills in reading the review was seeing the reviewer, Constantin Chassapis, recognize and highlight three of the most important of these topics: measurement, entanglement, the relation between the formal structures of  probability theory and quantum mechanics.

Quantum measurement is such old and well traveled territory that it still seems surprising to me that we saw a better, or at least usefully different, way  to develop it. It was a thrill to see that Chassapis thought it “one of the best introductions to the themes and concepts of quantum measurement that I have ever read.” Similarly, after reviewing papers that misunderstood entanglement, we wanted to drive home that “entanglement is not an absolute property of a quantum state, but that it depends on a specific decomposition of the system into subsystems.” Furthermore, it surprises me that the tensor product structure of probability theory is not discussed more often in probability texts and that “the relationship between the formal structures of probability theory and quantum mechanics” is not better known.

Another reason authors keep going is a deep love of the subject and the desire to share their  enjoyment of the subject with others. For this reason, my favorite sentence in the review is “I really devoured the book, rediscovering the joy of my student days.”

The biggest reason we kept going was that we had many supporters who believed in the project. We are particularly grateful to Michael Heaney and Paul McEvoy both of whom believed in the project enough to read drafts of all the chapters, often reading multiple versions of a chapter as we made revisions. Michael also co-organized a reading group that went through the book and gave us comments that enabled us to provide “a gradual and well-conceived escalation of difficulty in the themes it presents.”  Through that group we learned a lot about what did not work in an earlier draft of the book, without which it would never have had “an overall excellent rhythm” or become “an educational masterwork of a subject that is not easy.”

Many, many thanks to all of the people who helped us along the way.

And may all authors have such a perspicacious reviewer!