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. We present a scoring framework and a corresponding incremental top-k algorithm that addresses these issues with two-dimensional aggregations: social expansion considers the strength of relations among users, and semantic expansion considers the relatedness of different tags. Based on principles of threshold algorithms, it folds friends and related tags into the search space in an incremental on-demand manner. We additionally discuss ideas for meaningful evaluation in such dynamic environments.