Project topics and materials
Get Complete Project Material File(s) Now! »
Social-Aware Search
An important class of social applications are the collaborative tagging applications, also known as social bookmarking applications, with popular examples including Delicious8, StumbleUpon or Flickr. Their general setting is the following:
• users form a social network, which may reflect proximity, similarity, friendship, closeness, etc,
• items from a public pool of items (e.g., document, URLs, photos, etc) are tagged by users with keywords, for purposes such as description and classification, or to facilitate later retrieval,
• users search for items having certain keywords (i.e., tags) or they are recommended items, e.g., based on proximity at the level of tags. Collaborative tagging – and social applications in general – can offer an entirely new perspective to how one searches and accesses information. The main reason for this is that users can (and often do) play a role at both ends of the information flow, as producers and also as seekers of information. Consequently, finding the most relevant items that are tagged with some keywords should be done in a network-aware manner.
In particular, items that are tagged by users who are “closer” to the seeker – where the term closer depends on model assumptions that will be clarified shortly – should be given more weight than items that are tagged by more distant users. We consider in this work the problem of top-k retrieval in collaborative tagging systems. While the focus on bookmarking applications may seem restrictive, these represent a good abstraction for other types of social applications, to which our techniques could directly apply.
We investigate this problem with a focus on efficiency, targeting techniques that have the potential to scale to current applications on the Web9, in an online context where the social network, the tagging data and even the seekers’ search preferences can change at any moment. In this context, a key sub-problem for top-k retrieval that we need to address is computing scores of top-k candidates by iterating not only through the most relevant items with respect to the query, but also (or mostly) by looking at the closest users and their tagged items.
Context-Aware Query Processing Using Views
Retrieving the k best data objects for a given query, under a certain scoring model, is one of the most common problems in database systems and on Web. In many applica- tions, and in particular in current Web search engines, tens of thousands of queries per second need to be answered over massive amounts of data. Significant research effort has been put into addressing the performance of top-k processing, towards optimal algorithms– such as TA and NRA [31, 43] – or highly-efficient data structures [84] (e.g., inverted lists). In recent research, the use of pre-computed results (also called views) has been identified as a promising avenue for improving efficiency [49, 23].
At the same time, with the advent of location-aware devices, geo-tagging, bookmarking applications, or online social applications in general, as a way to improve the result quality and the user experience, new kinds of top-k search applications are emerging, which can be simply described as context-aware. The context of a query may represent the geographic location where the query was issued or the identity – within a social network – of the user who issued it. Indeed, the setting described in the previous section, i.e. network-aware social search, is an example of a context-aware search application. More generally, a context could represent certain score parameters that can be defined or personalized at query time. For example, a query for top-class vegetarian restaurants should not give the same results if issued in Paris or in Berlin, as it should not give the same results if issued within a social community of culinary reviewers or within a student community.
Inferring Signed Social Networks
An important trend in social platforms aims at exploiting the already existing user relationships, links between users (e.g., social links), in order to improve core function- alities in the system.
This is especially the case when links can be viewed as being signed, indicating a positive or negative attitude; possible meanings for positive links could be trust, friendship or similarity, while negative links could stand for distrust, opposition or antagonism. In settings where explicit relationships do not exist, are sparse or are inadequate indicators of one’s attitude towards fellow members of the community, it becomes thus important to uncover implicit user inter-connections, positive or negative links, from relevant user activities and their interactions.
Table of contents :
1. Introduction
1.1. Social-Aware Search
1.2. Context-Aware Query Processing Using Views
1.3. Inferring Signed Social Networks
2. Efficient Social-Aware Search
2.1. Related Work
2.2. General Setting
2.2.1. Computing Extended Proximities
2.3. Top-k Algorithm for the Social Case
2.3.1. Instance Optimality
2.4. Algorithm for the General Case
2.4.1. Choosing Between the Social and Textual Branches
2.5. Efficiency by Approximation
2.5.1. Estimating Bounds using Mean and Variance
2.5.2. Estimating Bounds Using Histograms
2.5.3. Maintaining the Description of the Proximity Vector
2.6. Scaling and Performance
2.7. System Implementation
2.8. Experimental Results
2.9. Conclusions
3. Context-Aware Search Using Views
3.1. Related Work
3.2. Formal Setting and Problems
3.3. Threshold Algorithms
3.4. Extracting a Probable Top-k
3.5. View Selection
3.5.1. Retrieving (G, P) After View Selection
3.6. Formal Guarantees
3.7. Context Transposition
3.7.1. Location-Aware Search
3.7.2. Social-Aware Search
3.8. Putting It All Together
3.9. Experiments
3.10. Conclusions
4. Inferring Signed Networks
4.1. Related Work
4.2. Extracting Interactions from Wikipedia
4.3. Building The Signed Network
4.4. A Taxonomy of Delete and Replace Interactions in Wikipedia
4.5. Empirical Validation
4.6. Exploiting WikiSigned at the Application Level
4.7. Extracting WikiSigned from the Complete History of Wikipedia
4.8. Conclusion
5. Research Perspectives
5.1. Social Search
5.2. Context-Aware Search Using Views
5.3. Signed Networks
A. Other Collaborations
