Visualizing tags over time

ABSTRACT

We consider the problem of visualizing the evolution of tags within the Flickr (flickr.com) online image sharing community. Any user of the Flickr service may append a tag to any photo in the system. Over the past year, users have on average added over a million tags each week. Understanding the evolution of these tags over time is therefore a challenging task. We present a new approach based on a characterization of the most interesting tags associated with a sliding interval of time. An animation provided via Flash in a Web browser allows the user to observe and interact with the interesting tags as they evolve over time.

New algorithms and data structures are required to support the efficient generation of this visualization. We combine a novel solution to an interval covering problem with extensions to previous work on score aggregation in order to create an efficient backend system capable of producing visualizations at arbitrary scales on this large dataset in real time.

REFERENCES

• 1: 15th International World Wide Web Conference. 2006. Proceedings of the Collaborative Web Tagging Workshop. Available online at http://www.rawsugar.com/www2006/taggingworkshopschedule.html.
• 2: Allan, J., Carbonell, J., Doddington, G., Yamron, J., and Yang, Y. 1998. Topic detection and tracking pilot study: Final report. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop. Defence Advanced Research Projects Agency, Arlington, VA.
• 3: Steve Chien , Nicole Immorlica, Semantic similarity between search engine queries using temporal correlation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060752]
• 4: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 5: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Marios Hadjieleftheriou , George Kollios , J. Tsotras , Dimitrios Gunopulos, Indexing spatiotemporal archives, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.143-164, June 2006 [doi>10.1007/s00778-004-0151-3]
• 8: Susan Havre , Elizabeth Hetzler , Paul Whitney , Lucy Nowell, ThemeRiver: Visualizing Thematic Changes in Large Document Collections, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.9-20, January 2002 [doi>10.1109/2945.981848]
• 9: Jon Kleinberg, Bursty and Hierarchical Structure in Streams, Data Mining and Knowledge Discovery, v.7 n.4, p.373-397, October 2003 [doi>10.1023/A:1024940629314]
• 10: Kleinberg, J. 2006. Temporal dynamics of on-line information systems. In Data Stream Management: Processing High-Speed Data Streams, M. Garofalakis, J. Gehrke, and R. Rastogi, Eds. Springer-Verlag, New York, NY.
• 11: H F Korth, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986
• 12: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the Bursty Evolution of Blogspace, World Wide Web, v.8 n.2, p.159-178, June 2005 [doi>10.1007/s11280-004-4872-4]
• 13: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Jeffrey P. Lankford , Daonna M. Nystrom, VizTree: a tool for visually mining and monitoring massive time series databases, Proceedings of the Thirtieth international conference on Very large data bases, p.1269-1272, August 31-September 03, 2004, Toronto, Canada
• 14: Brett Milash , Catherine Plaisant , Anne Rose, LifeLines: visualizing personal histories, Conference companion on Human factors in computing systems: common ground, p.392-393, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/257089.257391]
• 15: David Millen , Jonathan Feinberg , Bernard Kerr, Social bookmarking in the enterprise, Queue, v.3 n.9, November 2005 [doi>10.1145/1105664.1105676]
• 16: Robertson, S. and Walker, S. 2000. Okapi/Keenbow at Trec-8. In Proceedings of the 8th Text Retrieval Conference. National Institute of Standards and Technology, Gaithersburg, MD, 151--161.
• 17: M. Tork Roth , M. Arya , L. Haas , M. Carey , W. Cody , R. Fagin , P. Schwarz , J. Thomas , E. Wimmers, The Garlic project, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.557, June 04-06, 1996, Montreal, Quebec, Canada
• 18: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 19: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 20: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 21: Wattenberg, M. 1998. A map of the market. Available online at http://www.smartmoney.com/marketmap.
• 22: Wattenberg, M. 2001. Shape of song. Available online at http://turbulence.org/works/song.
• 23: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 24: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
Flickr, interval covering, tags, temporal evolution, visualization