In the last few years, Twitter has become a powerful tool for publishing and discussing information. Yet, content exploration in Twitter requires substantial e orts and users often have to scan information streams by hand. In this paper, we approach this problem by means of faceted search. We propose strategies for inferring facets and facet values on Twitter by enriching the semantics of individual Twitter messages and present di erent methods, including personalized and context-adaptive methods, for making faceted search on Twitter more e ective. We conduct a preliminary analysis that shows that semantic enrichment of tweets is essential for faceted search on Twitter and that there is essential need for adaptive faceted search on Twitter. Furthermore, we propose an evaluation methodology that allows us to automatically evaluate the quality of adaptive faceted search on Twitter without requiring expensive user studies.
With the growing information space on the Web and the increasing popularity of Social Media, Social Web applications became part of daily activities as well as the source of information for millions of people. The dynamic nature of the Web and the diversity of the users along with the heavy information load demanded some form of adaptation or personalization in many Web-based applications in various domains. Nowadays, many Social Web applications are su ering from similar information overload problems, where the users of these applications nd it di cult to read, nd and follow the relevant and interesting information shared by a large network of other users. Our research focuses on tackling information overload in one of the most popular of these applications, Twitter.
Twitter is the most popular micro-blogging site and a growing Social Web
phenomenon that is attracting interest from di erent types of people all around
the world for a variety of di erent purposes, such as fast communication, work,
status updates, following news, sports, events, opinions, hot topics, and so on [1{
8]. With millions of Twitter messages (tweets) per day, highly active users are
estimated to receive hundreds of tweets every day3. Due to the lack of any
adaptive or personalized navigation support in Twitter, users may get lost, become
de-motivated and frustrated in this network of information overload [
Searching and browsing are, indeed, somewhat limited in Twitter. For
example, one can search for tweets by a keyword or by a user in a timeline that would
return the most recent posts. So, if a user wants to see the di erent tweets about
a eld of sports, and were to search for \sports" in Twitter, only the recent tweets
that contain the word \sports" would be listed to the user. Many tweets that
do not contain the search keyword, but are about di erent sport events, sport
games and sport news in general, would not be returned. Moreover, the Twitter
keyword search di ers from the general Web search due to the restricted message
size of 140 characters in Twitter [
Semantic Enrichment We present methods for enriching the semantics of tweets by extracting facets (entities and topics) from tweets and related external Web resources.
User and Context Modeling Given the semantically enriched tweets, we propose user and context modeling strategies that identify (current) interests of a given Twitter user and allow for contextualizing the demands of this user. 3 http://techcrunch.com/2010/06/08/twitter-190-million-users/ 4 http://ebay.com/ 5 http://amazon.com/ Adaptive Faceted Search We introduce faceted search strategies for content exploration on Twitter and propose methods that adapt to the interests and context of a user.
Evaluation Framework We present an evaluation environment based on simulated users to evaluate di erent strategies in our adaptive faceted search engine on Twitter. 2
The exponential growth of Twitter has attracted signi cant amount of research from various perspectives and elds recently. In this section, we focus on the related work that motivates and inspires our work, as well as relating our work to the existing literature.
A prototype for topic-based browsing in Twitter was proposed after observing
how the users manage the incoming ood of updates [
The main problem in searching microblogging platforms is the size of the
messages. For example, the Twitter messages, with 140 characters limit, are too
short to extract meaningful semantics on their own. Furthermore users tend to
use abbreviations and short-form for words to save space, as well as colloquial
expressions, which make it even harder to infer semantics from tweets. Rowe
et al. mapped tweets to conference talks and exploited metadata of the
corresponding research papers to enrich the semantics of tweets to better understand
the semantics of the tweets published in conferences [
We also try to discover the relations between the extracted entities by studying
di erent strategies in order to determine relatedness relations between entities
such as persons related to an event and identify any temporal constraints on
such relations. These learnt relations between entities can be utilized to ease
the search by grouping together the related facets and recommending the most
relevant facets that the user is looking for. Marinho et al. proposed a method for
collabulary learning which takes a folksonomy and domain-expert ontology as
input and performs semantic mapping to generate an enriched folksonomy [
In addition to adapting the facets to the current search, we aim at
adapting the facet values to the current state of the users in order to personalize the
search and content exploration. Liu et al. analyzed content-based recommenders
for Google News and showed that interests in news topics such as technology,
politics, et cetera change over time [
On Twitter, facets describe properties of a Twitter message. For example,
persons that are mentioned in a tweet or events a tweet refers to. Oren et al. [
#$4J6'&62#1'#5"%1'6;<*==P2&/-)=:/ /' V/ 8$#$')5"',"#<#2,$1'96$%'
0$1$#$#'-5,&'&6$'W/C/'@<$%X*Y$,/ /' Z/ 02#,&'M4U5#'&5"#%4M$%&'4[$#'&6$'
@H'5<$%/'0$1$#$#'4%1'TU5E532J'/ /' \/ 865'&62%E,'&64&'+5>$#'0$1$#$#'2,' (a) Faceted search interface !"#$%&'() *+""*#) ,-./)*0") !"#$% 1$--"'*) 2$"-3) -.#/,/0)) 12/$3)
Faceted Search Engine
Semantic Enrichment facet extraction linkage User and Context Modeling profile generation relation learning Adaptive Faceted Search facet ranking query suggestion !"#$%&'%()*%+,+) (b) Faceted search architecture the type of the entity is considered as facet type (predicate) and the actual identi er of the entity is considered as facet value (object). For example, given a tweet t that refers to the tennis player \Federer", the corresponding URI of the entity (U RIfederer) and the URI of the entity type (U RIperson) are used to describe the tweet by means of an RDF statement: (t; U RIperson; U RIfederer).
Figure 1(a) illustrates how we envision the corresponding faceted search
interface that allows users to formulate faceted queries. Given a list of facet
values which are grouped around facet types such as locations, persons and events,
users can select facet-value pairs such as (U RIevent; U RIwimbeldon) to re ne their
current query ((U RIperson; U RIfederer), (U RIsportsgame; U RItennis)). A faceted
query thus may consist of several facet-value pairs. Only those tweets that match
all facet-value constraints will be returned to the user. The ranking of the tweets
that match a faceted query is a research problem of its own and could be solved
by exploiting the popularity of tweets { e.g. measured via the number of
retweets or via the popularity of the user who published the tweet (cf. [
The e ort, which u has to invest to narrow down the search result list H, can be measured by click and scroll operations. Strategies for facet ranking are discussed in Section 3.2.
Semantic Enrichment The semantic enrichment layer aims to extract facets
from tweets and generate RDF statements that describe the facet-value pairs
which are associated with a Twitter message. In particular, each tweet is
processed to identify entities (facet values) that are mentioned in the message. We
therefore make use of the OpenCalais API6, which allows for the extraction of
39 di erent types of entities (facet types) including persons, organizations,
countries, cities and events. As Twitter messages are limited to 140 characters, the
extraction of entities from tweets is a non-trivial problem. Thus, we introduced a
set of strategies that link tweets with external Web resources (news articles) and
propagate the semantics extracted from these resources to the related tweets
in [
User and Context Modeling In order to adapt the facet ranking to the
people who are using the faceted search engine, we propose user modeling and
context modeling strategies. The user modeling strategies model the interests
of the users in certain facet values (entities and topics). We therefore exploit
the tweets that have been published (including re-tweets) by a user. In future
work, we also plan to consider click-through data from the faceted search
engine. Context modeling covers mining of new knowledge from the Twitter data.
We therefore propose relation learning strategies that exploit co-occurrence of
entities in Twitter messages to infer typed relationships between entities [
Non-Personalized Facet Ranking A lightweight approach is to rank the facet-value pairs (p; e) 2 F based on their occurrence frequency in the current hit list H, the set of tweets that match the current query (cf. De nition 1): rankfrequency((p; e); H) = jH(p;e)j (1) jH(p;e)j is the number of (remaining) tweets that contain the facet-value pair (p; e) that can be applied to further lter the given hit list H. By ranking those facets that appear in most of the tweets, rankfrequency minimizes the risk of ltering out relevant tweets but might increase the e ort a user has to invest to narrow down search results.
Context-adaptive Facet Ranking The context-adaptive strategy exploits relationships between entities (facet values) to produce the facet ranking. A relationship is therefore de ned as follows:
tween these entities is described via a tuple rel(e1; e2; type; tstart; tend; w), where type labels the relationship, tstart and tend specify the temporal validity of the relationship and w 2 [0::1] is a weighting score that allows for specifying the strength of the relationship.
The higher the weighting score w the stronger the relationship between e1 and e2. We use co-occurrence frequency as weighting scheme. Hence, given the enriched tweets, we count the number of tweets both entities (e1 and e2) are associated with. The context-adaptive facet ranking strategy ranks the facetvalue pairs (p; e) 2 F according to w(ei; e), where ei is a facet value that is already part of the given query: (pi; ei) 2 Fquery (cf. De nition 1): rankrelation((p; e); Fquery) =
X w(ei; e)j(p; ei) 2 Fquery i (2)
Hence, the context-sensitive strategy can only be applied in situations where the user has already made one selection, so that jFqueryj > 0.
Personalized Facet Ranking The personalized facet ranking strategy adapts the facet ranking to a given user pro le that is generated by the user modeling layer depicted in Figure 1(b). User pro les conform to the following model and specify a user's interest into a speci c facet value (entity).
De nition 3 (User Pro le). The pro le of a user u 2 U is a set of weighted entities where with respect to the given user u for an entity e 2 E its weight w(u; e) is computed by a certain function w.
P (u) = f(e; w(u; e))je 2 E; u 2 U g
Here, E and U denote the set of entities and users respectively. s1x106 e u l a 1tv00000 e c a ttfx10000 o e lae 1000 tr a tsh 100 t e e tfow 10 r ubem 1 n 3.6 twee3t.-4based3.2 3 2.81111....824621 tweet-based + exploitation of news relations
Given the set of facet-value pairs (p; e) 2 F (see De nition 1), the personalized facet ranking strategy utilizes the weight w(u; e) in P (u) to rank the facet-value pairs: rankpersonalized((p; e); P (u)) = w(u; e) if w(u; e) 2 P (u) 0 otherwise (3)
By combining the above three strategies it is possible to generate further facet ranking methods. A combination of two strategies can be realized by building the weighted average computed for a given facet-value pair (p; e) (e.g. rankcombined = rank ((p; e)) + rank ((p; e))). 4
In our analysis, we study the characteristics of facets on Twitter. As described above, tweets do not feature many facets by nature. Therefore, strategies that enrich the semantic of tweets are required in order to derive facet-value pairs for tweets. In this section, we examine how the semantic enrichment supports the derivation of facets. Furthermore, we analyze the feasibility of the user and context modeling strategies for making faceted search on Twitter adaptive. 4.1
As tweets do not provide facets related to the topic, our faceted search framework provides the functionality to enrich the semantics of tweets. To analyze the feasibility of our semantic enrichment component (see Section 3), we monitored the Twitter activities of more than 20,000 users over a period of more than two months and processed the data that we collected (1,671,389 tweets in total) to extract facet values from the tweets. For 62.91% of the tweets, we succeeded in extracting at least one entity that we can use as facet value. By making use of the semantic enrichment functionality that exploits links to external Web resources (and news articles in particular), we increased the coverage so that 66.77% of
Tweet-only
Tweet+News-based enrichment 1 10 100
1000
the tweets which are enriched with facet values obtained from related news have
at least one facet value. In the context of the news-based enrichment, we
connected 458,566 Twitter messages with news articles of which 98,189 relations
were explicitly given in the tweets by URLs that pointed to the corresponding
news article. The remaining 360,377 relations were obtained by comparing the
entities that were mentioned in both news articles and tweets as well as
comparing the timestamps. In previous work we showed that this method correlates
news and tweets with an accuracy of more than 70% [
Figure 2(a) reveals that the number of facet values increases clearly when tweets are enriched with entities of related news articles. For example, less than 20 tweets exhibit more than 10 facet values in the case of semantic enrichment that is merely based on tweets . Given that tweets are limited to 140 characters, this observation is expected. Moreover, the number of di erent facet types per tweet also increases when linkage to news articles is exploited (see Figure 2(b)). In our current implementation, we di erentiate between 39 di erent facet types, where persons, countries and organizations are the most popular types of facets. In Figure 2(b), we see that the tweet-based enrichment does not allow for more than 10 di erent types of facet types per tweets while the exploitation of news relations features more than 10,000 tweets that can be discovered via more than 10 di erent facet types, i.e. users can choose between various facets to narrow down the actual hit list (cf. Figure 1(a)). 4.2
The adaptation of the faceted search interface to the preferences of the user and therefore the personalized facet ranking strategy (see Equation 3) requires entitybased user pro les (see De nition 3). To analyze to what extent this method can succeed, we show the pro le size of 1500 randomly selected user pro les in Figure 3. We see that the news-based enrichment results in pro les that provide more entities than the tweet-only based enrichment. For example, semantic enrichment based merely on tweets fails for three users as the size of the pro le is zero for these users. In contrast, the news-based enrichment successfully generates pro les for all users. For more than 98% of the users, the number of distinct entities per pro le is even higher than 100. This indicates that news-based enrichment prevents from sparsity problems and thus allows for supporting the personalized facet ranking better than the tweets-only-based enrichment. 5
Evaluating the performance of faceted search is challenging. It usually requires
query logs and click-through data, which is di cult to get for researchers, or
calls for user studies, which are expensive if they are conducted on a large scale.
In this section, we propose a novel technique for automatically evaluating the
performance of faceted search on Twitter. Our evaluation methodology follows
an idea introduced by Koren et al. [
General Setup. The general setup used for the evaluation process contains parameters describing the user interface itself and algorithms characterizing the simulated user behavior. In general, all faceted search user interfaces share some common characteristics and contains at least two parts: an area displaying the facets and a part showing the search results. For our evaluation process, the number of documents to be presented at a time, the number of di erent facets to be displayed and the number of elements which can be shown for each di erent facet need to be de ned. We setup a basic framework for a search interface by de ning these three parameters. Based on this interface, a user can perform di erent actions, where the goal is to nd a relevant document. For every action we can de ne a cost, where the cost is related to the time a real user would need to accomplish this action. In our scenario a user can perform the following actions: Select facet-value pair Basic action a user performs every time a facet-value pair is clicked, where the displayed search results are automatically updated after the selection (costs: 1).
View more facet-value pairs This action indicates that none of the currently displayed facet-value pairs are relevant for the user. By performing this action the user gets an additional amount of facet-value pairs related to one facet (costs: 2).
Show more documents This action allows the user to see more documents (tweets) matching the currently selected facet-values (costs: 2).
Select relevant tweet This action ends the current search (costs: 0).
Beside the actions mentioned above one could also consider the act of deselecting previously marked facet-values. In our search scenario, this action is not included as we assume that the users have perfect knowledge about the tweet they are looking for, and therefore a wrong selection will not take place. Selection Strategies. The simulated users select facet-value pairs based on di erent strategies. The strategies we use for our evaluation are: Random user This user randomly selects one of the displayed facet-values which matches the tweet he is looking for. If none of the displayed facetvalue pairs matches the tweet, he randomly chooses one facet to see more facet-value pairs.
First-match user This user selects the rst matching facet-value pair displayed by the interface. The basic idea behind this strategy is based on a user who directly clicks on a matching facet-value pair suggestion and do not look at all displayed facet value pairs to nd the best matching one. Greedy user This strategy tries to reduce the number of matching documents as fast as possible. This user selects the facet-value pair which occurs in the least number of remaining documents. This can be motivated by a user who selects the facet-value pair which is particularly important for the targeted tweet, in comparison to facet-value pairs which are related to many tweets.
Based on these facet selection strategies, the simulated user searches for a relevant document. The cost of this search is measured by the costs and number of actions a user needs to perform to nd a relevant document.
Evaluation process. To measure the bene t of the proposed methods for faceted search, we evaluate the cost for a user to nd relevant documents. Here, a tweet is relevant to a user, if the user re-tweeted this tweet. Re-tweeting a tweet indicates that the user has read the tweet and is to some extend interested in the content of the tweet. The proposed method is used to compare the costs of nding a relevant document when using the baseline ranking strategy based on frequency (non-personalized facet ranking) in comparison with context-adaptive facet ranking and personalized facet ranking. 6
In this paper, we presented an adaptive and personalized faceted search engine
for Twitter, where we explained approaches for enriching the semantics of tweets,
extracting facets, discovering relatedness information between entities and
observing user activities to learn their behavior and interests in order to support
users in their search for speci c information or tweets. We proposed di erent
strategies based on learnt relations together with user action history for
adapting the search behavior as well as improving content exploration in Twitter.
Furthermore, we introduced a generic evaluation environment based on Koren
et al. [
Acknowledgements The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no ICT 257831 (ImREAL project7).