Efficient computation of personal aggregate queries on blogs

ABSTRACT

There is an exploding amount of user-generated content on theWeb due to the emergence of "Web 2.0" services, such as Blogger,MySpace, Flickr, and del.icio.us. The participation of a large number of users in sharing their opinion on the Web has inspired researchers to build an effective "information filter" by aggregating these independent opinions. However, given the diverse groups of users on the Web nowadays, the global aggregation of the information may not be of much interest to different groups of users. In this paper, we explore the possibility of computing personalized aggregation over the opinions expressed on the Web based on a user's indication of trust over the information sources. The hope is that by employing such "personalized" aggregation, we can make the recommendation more likely to be interesting to the users. We address the challenging scalability issues by proposing an efficient method, that utilizes two core techniques: Non-Negative Matrix Factorization and Threshold Algorithm, to compute personalized aggregations when there are potentially millions of users and millions of sources within a system. We show that, through experiments on real-life dataset, our personalized aggregation approach indeed makes a significant difference in the items that are recommended and it reduces the query computational cost significantly, often more than 75%, while the result of personalized aggregation is kept accurate enough.

REFERENCES

• 1: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 2: Akshay Java, Pranam Kolari, Tim Finin, Anupam Joshi, and Tim Oates. Feeds That Matters: A Study of Bloglines Subscriptions. In ICWSM, Boulder, Colorado, USA, March 2007.
• 3: Bloglines. http://www.bloglines.com.
• 4: Natalie S. Glance, Matthew Hurst, and Takashi Tomokiyo. BlogPulse: Automated Trend Discovery for Weblogs. In WWW Conference, 2004.
• 5: Daniel Gruhl , R. Guha , David Liben-Nowell , Andrew Tomkins, Information diffusion through blogspace, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988739]
• 6: Qiaozhu Mei , Chao Liu , Hang Su , ChengXiang Zhai, A probabilistic approach to spatiotemporal theme pattern mining on weblogs, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135857]
• 7: Xuanhui Wang , ChengXiang Zhai , Xiao Hu , Richard Sproat, Mining correlated bursty topic patterns from coordinated text streams, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281276]
• 8: Feng Qiu , Junghoo Cho, Automatic identification of user interest for personalized search, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135883]
• 9: Seung-Taek Park , David M. Pennock, Applying collaborative filtering techniques to movie search for better ranking and browsing, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281252]
• 10: Georgia Koutrika , Yannis Ioannidis, Constrained optimalities in query personalization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066167]
• 11: Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242610]
• 12: Chengkai Li , Min Wang , Lipyeow Lim , Haixun Wang , Kevin Chen-Chuan Chang, Supporting ranking and clustering as generalized order-by and group-by, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247496]
• 13: Huiming Qu and Alexandros Labrinidis. Preference-Aware Query and Update Scheduling in Web-databases. In ICDE Conference, 2007.
• 14: Shouke Qin , Weining Qian , Aoying Zhou, Approximately Processing Multi-granularity Aggregate Queries over Data Streams, Proceedings of the 22nd International Conference on Data Engineering, p.67, April 03-07, 2006 [doi>10.1109/ICDE.2006.22]
• 15: Sailesh Krishnamurthy , Chung Wu , Michael Franklin, On-the-fly sharing for streamed aggregation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142543]
• 16: Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas, Supporting ad-hoc ranking aggregates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142481]
• 17: Chih-Jen Lin, Projected Gradient Methods for Nonnegative Matrix Factorization, Neural Computation, v.19 n.10, p.2756-2779, October 2007 [doi>10.1162/neco.2007.19.10.2756]
• 18: Patrik O. Hoyer, Non-negative Matrix Factorization with Sparseness Constraints, The Journal of Machine Learning Research, 5, p.1457-1469, 12/1/2004
• 19: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]
• 20: Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150420]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Experimentation

Keywords:
aggregate queries, matrix factorization, personalized recommendation, web-mining