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: J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic detection and tracking pilot study: Final report. DARPA Broadcast News Transcription and Understanding Workshop, 1998.
• 2: 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]
• 3: 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]
• 4: S. Golder and B. Huberman. The structure of collaborative tagging systems. Journal of Information Science, 2006.
• 5: 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
• 6: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient Indexing of Spatiotemporal Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.251-268, March 25-27, 2002
• 7: 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]
• 8: 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]
• 9: J. Kleinberg. Temporal dynamics of on-line information systems. In M. Garofalakis, J. Gehrke, and R. Rastogi, editors, Data Stream Management: Processing High-Speed Data Streams. Springer, 2006.
• 10: H F Korth, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986
• 11: 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]
• 12: J. Lin, E. J. Keogh, S. Lonardi, J. P. Lankford, and D. M. Nystrom. Viztree: a tool for visually mining and monitoring massive time series databases. In Proceedings of International Conference on Very Large Data Bases, pages 1269--1272, 2004.
• 13: 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]
• 14: David Millen , Jonathan Feinberg , Bernard Kerr, Social bookmarking in the enterprise, Queue, v.3 n.9, November 2005 [doi>10.1145/1105664.1105676]
• 15: S. Robertson and S. Walker. Okapi/Keenbow at Trec-8. In Proceedings of the 8th Text Retrieval Conference, pages 151--161, 2000.
• 16: 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
• 17: 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
• 18: 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]
• 19: 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]
• 20: I. Witten, A. Moffat, and T. Bell. Managing Gigabytes. Morgan Kaufmann Publishers, second edition, 1999.
• 21: 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, social media, tags, temporal evolution, visualization