Select Lab Publications

Trains of Thought: Generating Information Maps (2012)

By: Dafna Shahaf, Carlos Guestrin, and Eric Horvitz

Abstract: When information is abundant, it becomes increasingly difficult to fit nuggets of knowledge into a sigle coherent picture. Complex stories spaghetti into branches, side stories, and intertwining narratives. In order to explore these stories, one needs a map to navigate unfamiliar territory.

We propose a methodology for creating structured summaries of information, which we call metro maps. Our proposed algorithm generates a concise structured set of documents which maximizes coverage of salient pieces of information. Most importantly, metro maps explicitly show the relations among retrieved pieces in a way that captures story development.

We first formalize characteristics of good maps and formulate their construction as an optimization problem. Then we provide efficient methods with theoretical guarantees for generating maps. Finally, we integrate user interaction into our framework, allowing users to alter the maps to better reflect their interests. Pilot user studies with a real-world dataset demonstrate that the method is able to produce maps which help users acquire knowledge efficiently.

Download Information
Dafna Shahaf, Carlos Guestrin, and Eric Horvitz (2012). "Trains of Thought: Generating Information Maps." International World Wide Web Conference (WWW). pdf   talk      
BibTeX citation

title = {Trains of Thought: Generating Information Maps},
author = {Dafna Shahaf and Carlos Guestrin and Eric Horvitz},
booktitle = {International World Wide Web Conference (WWW)},
year = 2012,
wwwfilebase = {www2012-shahaf-guestrin-horvitz},
wwwtopic = {Data Mining}

full list