Efficient top-k querying over social-tagging networks

ABSTRACT

Online communities have become popular for publishing and searching content, as well as for finding and connecting to other users. User-generated content includes, for example, personal blogs, bookmarks, and digital photos. These items can be annotated and rated by different users, and these social tags and derived user-specific scores can be leveraged for searching relevant content and discovering subjectively interesting items. Moreover, the relationships among users can also be taken into consideration for ranking search results, the intuition being that you trust the recommendations of your close friends more than those of your casual acquaintances.

Queries for tag or keyword combinations that compute and rank the top-k results thus face a large variety of options that complicate the query processing and pose efficiency challenges. This paper addresses these issues by developing an incremental top-k algorithm with two-dimensional expansions: social expansion considers the strength of relations among users, and semantic expansion considers the relatedness of different tags. It presents a new algorithm, based on principles of threshold algorithms, by folding friends and related tags into the search space in an incremental on-demand manner. The excellent performance of the method is demonstrated by an experimental evaluation on three real-world datasets, crawled from deli.cio.us, Flickr, and LibraryThing.

References

1. G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng., 17(6):734--749, 2005.
2. Y.-Y. Ahn et al. Analysis of topological characteristics of huge online social networking services. In WWW, 2007.
3. S. Amer-Yahia et al. Challenges in searching online communities. IEEE Data Eng. Bull., 30(2):23--31, 2007.
4. V. N. Anh and A. Moffat. Pruned query evaluation using pre-computed impacts. In SIGIR, 2006.
5. R. A. Baeza-Yates and A. Tiberi. Extracting semantic relations from query logs. In KDD, 2007.
6. S. Bao et al. Optimizing web search using social annotations. In WWW, 2007.
7. H. Bast et al. IO-Top-k: Index-access optimized top-k query processing. In VLDB, 2006.
8. M. Bender et al. Peer-to-peer information search: Semantic, social, or spiritual? IEEE Data Eng. Bull., 30(2):51--60, 2007.
9. B. Billerbeck and J. Zobel. Questioning query expansion: An examination of behaviour and parameters. In ADC, 2004.
10. S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks, 30(1-7):107--117, 1998.
11. A. Damian et al. Peer-sensitive objectrank - valuing contextual information in social networks. In WISE, 2005.
12. A. Das et al. Google news personalization: scalable online collaborative filtering. In WWW, 2007.
13. P. A. Dmitriev et al. Using annotations in enterprise search. In WWW, 2006.
14. M. Dubinko et al. Visualizing tags over time. ACM Transactions on the Web, 1(2), 2007.
15. R. Fagin et al. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci., 66(4):614--656, 2003.
16. S. Golder and B. A. Huberman. Usage patterns of collaborative tagging systems. Journal of Information Science, 32(2):198--208, April 2006.
17. H. Halpin et al. The complex dynamics of collaborative tagging. In WWW, 2007.
18. D. Heckerman et al. Dependency networks for inference, collaborative filtering, and data visualization. Journal of Machine Learning Research, 1:49--75, 2000.
19. J. L. Herlocker et al. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems, 22(1), 2004.
20. P. Heymann et al. Can social bookmarking improve web search? In WSDM, 2008.
21. P. Heymann and H. Garcia-Molina. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Technical Report 2006-10, Stanford University, April 2006.
22. A. Hotho et al. Information retrieval in folksonomies: Search and ranking. In The Semantic Web: Research and Applications, pages 411--426, 2006.
23. K. Järvelin and J. Kekäläinen. IR evaluation methods for retrieving highly relevant documents. In SIGIR, 2000.
24. R. Kumar et al. Structure and evolution of online social networks. In KDD, 2006.
25. G. Linden et al. Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internet Computing, 7(1), 2003.
26. A. Mislove et al. Exploiting social networks for internet search. In HotNets, 2006.
27. J. Pouwelse et al. Tribler: A social-based peer-to-peer system. In IPTPS, 2006.
28. S. E. Robertson and S. Walker. Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In SIGIR, 1994.
29. B. M. Sarwar et al. Item-based collaborative filtering recommendation algorithms. In WWW, 2001.
30. J. B. Schafer et al. Collaborative filtering recommender systems. In The Adaptive Web, 2007.
31. C. Schmitz et al. Mining association rules in folksonomies. In Data Science and Classification. Springer, 2006.
32. S. Sen et al. Tagging, communities, vocabulary, evolution. In CSCW, 2006.
33. C. Tantipathananandh et al. A framework for community identification in dynamic social networks. In KDD, 2007.
34. M. Theobald et al. Efficient and self-tuning incremental query expansion for top-k query processing. In SIGIR, 2005.
35. S. Xu et al. Using social annotations to improve language model for information retrieval. In CIKM, 2007.
36. J. Zhang et al. Expertise networks in online communities: structure and algorithms. In WWW, 2007.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing

  • Information systems applications