Gary Benattar
email: g.benattar@gmail.com

Philippe Trebuchet
email: philippe.trebuchet@lip6.fr

Trend Analysis in Polls, Topics, Opinions and Answers

Toluna.com is a Web community site focusing on polls and opinions of people.

Our mission is to allow anyone to know what the world thinks on any issue and foster a community of insight through the use of Web2.0 technology. Each poll created has value in itself; it is a snapshot of the world's opinions and as a result has tremendous value for community members interested in a particular topic.

According to Merriam-Webster, a trend can be dened as the general movement over time of a statistically detectable change. In our specic case, we want to observe variations of occurrences of words or topics so as to identify interesting events. Trends are easily observed on the graphical representations of time series distribution as they appear as peaks.

As you can see gure 1 the frequency for the word 'bin' on the 5Th may 2011 rised sharply and on the 7th may 2011 this word came back to its normal frequency. This is the example of a perfect trends, short and volcanic.

An other example is shown in gure 2 for Prince William and Kate Middleton's wedding. The biggest diculty on trend detection is to know when exaclty the trend started and when it will stop, it can be less than one day or one hour depending on the website activity and the power of the trend.

Before introducing all the statistical methods used in this project and all the common problems for the implementation of a scalable architecture, we will introduce Toluna objects and data used in the system. 4 As explained later, we use a stemmer in order to keep one canonical representation of morphological variations. As a result, 'favorite' as well as 'favorites' are mapped into the same stem "favorit", whose frequency over time we observe here. A Topic can also contains other elements like videos or images, but they will be not used in this project.

An opinion internal structure can be dened as follow:

{TEXT, O p i n i o n * , Date } -> { ' Yes I l o v e s u s h i w i t h w a s a b i ' , ' R e a l l y you l i k e w a s a b i ? ' , 2008 -02-02}

All the elements in the topic schema is all the elements used for the analysis. In fact most of the trend detection will be done on the topic title and not on the opinions. The opinions will be used to detect collocations for a specic topic in order to specify an elected trend.

A poll internal structure can be dened as follow:

{ Q u e s t i o n , Answer * , Date } -> { ' Do you l i k e s u s h i ? ' , { ' Yes ' , ' No ' , ' N e v e r t r y ' } ,

-12-12}

A poll can be described as a short survey with only one question and multiple answers which can be 'single choice' answers ('Yes','No') or 'multiple choice' answers ('Love sushi','and also grilled chicken'). In this project poll question will be used for single word trend detection.

Events and Timeline

In our project we will consider the following events:

• Topic creation: In this case we will simply consider the topic title as a new document added at the specic creation time of the topic. Words in the topic will be analyzed and their frequencies will be updated.

• Opinion on a topic: In this case we will in fact ignore the text of the opinion but simply repeat the topic title.

• Poll creation: We will add the text of the poll and the answers, we will analyze it and update the frequencies of the words.

• Vote on a poll: Similar to what we do for opinions, we will simply consider the text of the poll one more time for each vote.

The sum of the events for a given interval is all the activity on the Toluna.com website. Everytime someone is doing something on the website will produce an event and will be added to the trend analysis.

Toluna Data Size

In this project we used the Toluna.com database from the beginning of 2008 up to May 2011. The data is anonymized and contains the following data:

• In the next section we describe how the data is modelized in this project.

3 Language Model

Denitions

In our language model we will use single words and bigrams as our basic units.

A bigram is a pair of words that appear at least once on the same sentence within a distance of 5 other words.

For example, in the sentence above the following bigrams can be extracted:

' l a n g u a g e -model ' ' l a n g u a g e -use ' ' s i n g l e -word ' ' s i n g l e -bigram ' ' word-b i g r a m ' ' b a s i c -bigram ' ' b a s i c -u n i t ' ' b i g r a m-p a i r ' ' b i g r a m-word ' ' p a i r -word ' ' word-a p p e a r ' e t c . . . Note that in our denition, the words in a bigram do not have to be adjacent but can be separated by other words and they can appear in any order. We use 5 as the maximum bigram distance, as Most of the lexical relations involving a word w can be retrieved by examining the neighborhood of w, wherever it occurs whitin a span of ve [START_REF] Smadja | Retrieving collocations from text: Xtract[END_REF] (-5 and +5 around w) . This will allow us to discover collocations, where a collocation is dened as a recurrent combinations of words that co-occur more often than expected by chance and that correspond to aribtrary word usage [START_REF] Smadja | Retrieving collocations from text: Xtract[END_REF]. We decided to show collocations only for trends, because the collocation always provides additional information because it occurs many times in the corpus. For example, in the collocation 'Mark Zuckerberg' it could be argued that 'Zuckerberg' is good enough and that 'Mark' is adding too litle information. However, we chose to use the collocation anyways because in the more general case it can help disambiguate.

• Stop words

A stop word is a common word which give us no information about the current topic or the current trend but that are mostly grammatical words such as articles, prepositions, etc. The most common stop words in English are: 'the', 'a', 'an', 'do','you','I','about',... Generally a list of stop words is used in text analysis which is not related to the actual context of the analysis and are language dependent. In processing of natural language data, stop words will be ltered out. The sentence above after ltering out the stop words will look like: 'Generally list stop words text analysis related actual context analysis language dependent'.

For example in the snowball 5 project or lucene 6 it is necessary to populate or create the stop word list for each additional language. In this work, we propose to not use a xed stop words list but rather to use statistics to be able to ignore words that appear too frequently or with a frequency too at. For example recurring topics on Toluna should not be considered as trends. (gures 4). Natural language processing systems often use stemmers in order to reduce the word forms of a single word. For example, 'shing', and 'sh' belong to the same stem 'sh', so the output of the stemming process for these 2 words will be 'sh'. For example in the sentence 'I love shing because I love sh', the single words 'shing' and 'sh' will be count like the same word due to the stemming process [START_REF] Porter | An algorithm for sux stripping[END_REF]. Real words will be used only in the user interface in order to display understandable trends.

The model

Each event as dened in the previous section, will be represented by a tuple containing the following information: (event data, date). In order to classify our data, we will need to split the data in two part, on one hand, polls and topics and on the other hand opinions and answers.

• Topic and Opinion

Upon receiving a topic creation event, the software will analyze the topic title, split the title into words and increment the word count of each word at the current date.

As an opinion is linked to a topic, we propose a simple model in order to be not dependent to the topic creation date but to the opinion creation date, we simply re -publish the parent topic at the current date. As we can see, everytime a new opinion appears on a topic, the topic is re-published at the current date, because we assume that if a user let an opinion on a topic, it means that the topic itself as a trend is reinforced.

This allows us to in fact, as a rst draft, completely ignore the text of the opinion and simply strengthen the topic. The text of the opinion will be used in a second stage as shown below.

• Poll and Answer

For polls and answers the process is very similar to the one we just described in the previous section. However we wanted to introduce a dierence that would reect that it is much easier to vote on a poll (single click) than to give an opinion of more than 20 words (over 100 clicks). So we decided to republish the text of the poll for each number of votes. Some testing on our data allowed us to set the number to 10. In the following section we will propose a statistical method in order to detect trend and collocation trend.

4

Trend detection

Notations

• Word frequency

The frequency for a word f (w) d is equal to the number of occurrence of w in d.

• Word proportion

The proportion for a word w in d is equals to: f • Mean

The mean for a word is the average proportion for the word w on the overall period.

N : Total number of days p(w) d : proportion at the date d

x = 1 N p(w) d • Standard deviation
The standard deviation show how much variation there is from the average.

A low standard deviation indicates that the data is very close to the mean.

σ = 1 N (x d -x) 2

Zscore

• What is a Zscore A zscore indicates how many standard deviation an observation is above or below the mean. That's what we usually called standardizing data.

Z(w) d = x d - x σ
The following subset contains zscore at each date for w = 'sushi' (zscore = value) d a t e : 2 0 0 9 -11 -06 , v a l u e = 0 . 8 9 d a t e : 2 0 0 9 -11 -11 , v a l u e = 2 . 6 1 d a t e : 2 0 0 9 -11 -12 , v a l u e = 0 . 5 4 d a t e : 2 0 0 9 -11 -21 , v a l u e = 1 . 0 4 d a t e : 2 0 0 9 -12 -07 , v a l u e = 1 . 9 0 d a t e : 2 0 0 9 -12 -08 , v a l u e = 0 . 8 7 d a t e : 2 0 0 9 -12 -31 , v a l u e = 0 . 8 6 d a t e : 2 0 1 0 -01 -19 , v a l u e = 1 . 4 2 d a t e : 2 0 1 0 -02 -02 , v a l u e = 0 . 4 5 d a t e : 2 0 1 0 -02 -07 , v a l u e = 0 . 5 4 d a t e : 2 0 1 0 -02 -13 , v a l u e = 0 . 5 5

The z-score is a measure commonly used in nance and dened as:

The Z-Score is a multivariate formula for a measurement of the nancial health of a company and a powerful diagnostic tool that forecasts the probability of a company entering bankruptcy within a 2 year period [START_REF] Edward | Financial ratios, discriminant analysis and the prediction of corporate bankruptcy[END_REF].

As a z-score detects large variations from the normal, in our context it will be used to detect large and uncommon variations of a word proportion at a given date. In the following section, we explain how we use the z-score to identify a trend.

• Bracketing

In order to interpret this value we put our raw data into brackets and set a threshold for each bracket.

The proportion can be expressed as:

P o(w) = nbD(w) c d
where nbD(w) stands for the number of days during which w appears, c d stands for the number of days covering the entire period.

The bracketing is done as follows: We can see that the interval for the two rst brackets are dierent. This is because these brackets will contain very uncommon words which will need a special analyse due to the zero frequency problem (see section 5).

[ 0 -5 [ , [ 5 -1 0 [ , [ 1 0 -2 0 [ , [ 2 0 -3 0 [ , [ 3 0 -4 0 [ , [ 4 0 -5 0 [ , [ 5
As explained, each bracket contains a z-score threshold. These 11 thresholds are the results of various training sessions among dierent set of data.

First of all, these thresholds were tuned on a training data, and then were connected to another set of data. Trend extraction was a success in both case. More P o(w) is low, more the result of a small frequency variation will be high for the z-score.

The closer we are to 100, more the threshold should be low. Keep in mind that each day we have 0 occurrences for a word, the proportion will be equal to zero.

The zero frequency problem

What will happen if a word which belongs to the rst bracket suddenly happens to be used inside a topic title or poll title? In the best case, 95 percents of frequencies will be equal to zero. If this word is used suddenly, even if the variation is not signicant, the z-score value will jump and be greater than the current threshold.

The example below shows the current distribution for w=`aar', as we see a single occurrence, for all the other dates, the proportion is equal to zero. end for return mean(averageList) We propose here to tackle this issue in a dierent manner: we take all the words within these brackets and calculate the average proportion for each word, and nally calculate the average of the list of averages for all words (See Algorithm 1).

We nally verify whether a word within these brackets has a large frequency variation as compared to the value calculated on the training data (see Table 4).

Trend detection algorithm

The z-score is calculated for each single word in the titles of topics and polls and compared to a given threshold. The key steps of the algorithm are outlined below.

Algorithm 2 Here there is one single top collocation, which is 'laden bin' with a number of occurrences equal to 3582, so the trends 'bin' will be replace by 'laden bin'. In this specic case, we see that the collocation brings most value. Indeed 'bin', which is the volcanic single trend is not understandable without context. Collocation is the magic recipe to transform a 'statistical trend' into an 'interpretable' trend.

The bigram 'bin laden' was detected as a collocation trend on 1, 2, 3, 4, 5

May 2011.

If we compare ourselves to Google trends, we see that by displaying only collocation trends rather than single words as Google Trends does from time to time,

we avoid pitfalls such as showing empty words such as `why' as might happen with Google Trends as shown below.

5 Results

• Recurring trends 7

Halloween Detected as a trend on 2008-09-13, 2009-10-31 As described, we have more than 20 millions events in our data, which needs to be split by words and count. Moreover, we have millions of events every day, which need to be parsed and classied in real time. Given the size of this data, we decided to use an appropriate large scale system for processing and analyzing the data. We explain below why we went for Hadoop and HBase. We will conclude by sharing our (failed) experience in a preliminary implemetation based on MySQL. The most important characteristic of HBase is its capability of splitting a table into regions. In fact, one can dene the start and end row for each region. Each region belongs to a region server, and the content of each region server is indexed on a master, which redirects the client to a good node. Data transfer between region server and clients is done directly without the help of the master.

Scalability

The Apache foundation also provides a library in order to communicate with hbase through the sofware. We list below a partial list of all the • Base component: We implemented in this component the objects used in our system. • Test component: This component should also never be used in production mode, it contains some basics test.

• Web component: This component contains web servlets and it is linked to WebContent which contains all the JSP les. Training even with a very small data set would take way too long. This was worrisome as intuitively we believed that no good results could be obtained without a minimum of 1 million documents. So we investigated other technologies and the answer was brutal: MySQL would not scale to the level we needed and the literature pointed is to 3 Google-originated technologies: MapReduce [START_REF] Dean | Mapreduce: simplied data processing on large clusters[END_REF],

BigTable [START_REF] Chang | Bigtable: a distributed storage system for structured data[END_REF] and GFS [START_REF] Ghemawat | The google le system[END_REF]. After much reading, we decided to re-design the entire system, move to a Hadoop environment (the Yahoo!-initiated open-source equivalent of MapReduce) and adopt HBase, We also decided to reimplement everything in Java as this is the native language of Hadoop (even if one can interface with Hadoop in Python or C++, Java is still the language of choice when working in Hadoop).

The rst results were not that good, many strange words and misspellings appeared. This led us to investigate our settings and especially the z-score threshold. It seems that a single z-score threshold could not be used for all the proportion computations. We started to build all the brackets and ran lot of ve percent) we had 90% of bad words, most of us was miss-spelling words.

We were confronted to the zero-frequency. After more investigation, We found an article where the authors solved the zero frequency problem with a Laplace estimator.

Inspired by this article, We decided to search for a dedicated threshold for these problematic words, and we experimented with the mean of the mean.

Results were satisfactory. In order to validate everything we asked Toluna's database team to provide us a clean and up to date database. we connected the new database to the software. Results were also satisfactory.

At this stage, the system extracted decent trends, yet they were not easy to interpret for users not familar with the dataset. As we followed the news, we knew that Bin Laden was dead so when we extracted the word 'bin', we did the connection, but our goal were to understand without any background the displayed trends and for us 'bin' was really not a good trend for the user.

We had the chance to talk to ToLuna SVP, Frank Smadja, an ex-computational linguistics researcher, who happens to be one of the pioneers of collocation extraction and analysis. After a short brainstorm, we realized that collocations were the key to this interpretatibility problem. At this moment we took the decision to nd single words trends in polls and topics only and to specify trends found with collocations inside opinions and answers, and 'bin' became 'bin laden', 'royal' became 'royal wedding', 'patrick' became 'patrick swayze'.

The last step was to design a user interface. Fortunately HBase provided already some very convenient utilities, We just had to add some export tools and devise some charts and timeline plug-ins.

Data visualization is always a key components in any data-mining eort especially when the output needs to be displayed to the user. As an example Google trends while being very sophisticated with its rich dashboard, might be a bit too complex for casual users. Yahoo! Clues that was just launched in the US targets more naive users (as Yahoo! typical users are) and in our opinion with its simplicity and attractive facets might attract less sophisticated users if it reaches them.

Finally, we have not included any evaluation in this report. However we do plan to conduct thorough comparisons between our approach, Yahoo! clues and Google trends in order to validate our contributions.

7

1

 1 ndCollocationCandidate . . . . . . . . . . . . . . . . . . . . . . List of Figures 1 p( bin ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 p( f avorit ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 p( royal ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 p( is ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 p( aar ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 p( bin ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 p( halloween ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 p( valentin ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 p( thanksgiv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 p( japan ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Japan top collocations timeline . . . . . . . . . . . . . . . . . . . 12 Bin Laden and Royal Wedding top collocations timeLine . . . . . 13 Top collocations on timeline . . . . . . . . . . . . . . . . . . . . . 14 p( swine ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p( swayze ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 p( lebron ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . What is a trend? This work focuses on analyzing trends on a popular market research Web site, toluna.com. Toluna, is the world's largest online market research panel and online survey software provider to the global market research industry. Providing online market research sample and online research panel building expertise to over 1,500 of the world's leading market research agencies.

Figure 1 : 5 Figure 3 :

 153 Figure 1: p( bin )

Figure 2 :

 2 Figure 2: p( royal )

Figure 4 :

 4 Figure 4: p( is )

  For example: { E v e n t : T o p i c , I d : 1 , T i t l e : ' What do you t h i n k a b o u t g l a d i a t o r ? ' , Date : 2008 -01-01 } { E v e n t : T o p i c , I d : 2 , T i t l e : ' S h o u l d I buy t h e new e p s o n c a m e r a ? ' , Date : 2008 -01-01 } { E v e n t : T o p i c , I d : 3 , T i t l e : ' I l o v e f i s h i n g b e c a u s e I l o v e f i s h ' , Date : 2008 -01-03 } { E v e n t : O p i n i o n , I d : 8 , Text : ' I l o v e t h i s m o v i e and I c a n r e -watch a g a i n a g a i n and a g a i n , I want t o become a g l a d i a t o r ' , P a r e n t : 1 , Date : 2008 -01-03 } { E v e n t : O p i n i o n , I d : 9 , Text : ' Very g o o d f i l m ! ' , P a r e n t : 1 , Date : 2008 -01-03 } { E v e n t : O p i n i o n , I d : 1 5 , Text : ' T h i s i s t h e l o n g e s t m o v i e e v e r s e e n i n H o l l y w o o d ' , P a r e n t : 1 , Date : 2008 -01-04 } { E v e n t : O p i n i o n , I d : 1 0 0 , Text : ' No ' , P a r e n t : 2 , Date : 2009 -01-04 } Classication by date (stop words were removed): (w,count) 2008 -01-01 ( ' g l a d i a t o r ' , 1 ) ( ' movie ' , 1 ) ( ' e p s o n ' , 1 ) ( ' camera ' , 1 ) 2008 -01-03 ( ' g l a d i a t o r ' , 2 ) ( ' movie ' , 2 ) ( ' f i s h ' , 2 ) ( ' l o v e ' , 2 ) 2008 -01-04 ( ' g l a d i a t o r ' , 1 ) ( ' movie ' , 1 ) 2009 -01-04 ( ' e p s o n ' , 1 ) ( ' camera ' , 1 )

  For example: { E v e n t : P o l l , I d : 7 , T i t l e : ' Do you l i k e f r e n c h f r i e s ' , Date : 2008 -01-01} { E v e n t : P o l l , I d : 8 , T i t l e : ' Do you l i k e f r e n c h p o t a t o e s ' , Date : 2008 -01-01} { E v e n t : Answer , I d : 1 2 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 1 8 , Text : no , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 1 9 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 2 2 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 2 9 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 3 2 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 3 3 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 3 4 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 3 7 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} { E v e n t : Answer , I d : 4 0 , Text : ' y e s ' , P a r e n t : 7 , Date : 2008 -03-03} Classication by date (stop words were removed): (w,count) 2008 -01-01 ( ' f r e n c h ' , 2 ) ( ' f r i e s ' , 1 ) ( ' p o t a t o e s ' , 1 ) 2008 -03-03 ( ' f r e n c h ' , 1 ) ( ' f r i e s ' , 1 )

  w) d : the frequency for w in d t d : number of words in d p(w) d = f (w) d t d Example: in the list, we list the proportion of the word sushi (value=frequency) d a t e : 2 0 0 9 -11 -06 , v a l u e = 5 . 7 2E-4 d a t e : 2 0 0 9 -11 -11 , v a l u e =0 d a t e : 2 0 0 9 -11 -12 , v a l u e = 3 . 9 7E-4 d a t e : 2 0 0 9 -11 -21 , v a l u e = 6 . 4 8E-4 d a t e : 2 0 0 9 -12 -07 , v a l u e =0 d a t e : 2 0 0 9 -12 -08 , v a l u e = 5 . 6 2E-4 d a t e : 2 0 0 9 -12 -31 , v a l u e = 5 . 4 6E-4 d a t e : 2 0 1 0 -01 -19 , v a l u e = 8 . 1 0E-4 d a t e : 2 0 1 0 -02 -02 , v a l u e = 3 . 3 4E-4 d a t e : 2 0 1 0 -02 -07 , v a l u e = 3 . 7 5E-4

d a t e : 2 0 1 0 4 Table 3 :Figure 5 :

 1435 Figure 5: p( aar )

For

  illustration, let us consider the following example with the word 'bin' on 2011-05-02, which is the day of Bin Laden's death. For w=`bin' we obtain: d a t e : 2 0 1 1 -04 -27 , v a l u e =0 d a t e : 2 0 1 1 -04 -30 , v a l u e = 3 . 4 2 4E-4 d a t e : 2 0 1 1 -05 -01 , v a l u e = 0 . 0 1 d a t e : 2 0 1 1 -05 -02 , v a l u e = 0 . 0 6 d a t e : 2 0 1 1 -05 -03 , v a l u e = 0 . 0 4 d a t e : 2 0 1 1 -05 -04 , v a l u e = 0 . 0 3 d a t e : 2 0 1 1 -05 -05 , v a l u e = 0 . 0 3 d a t e : 2 0 1 1 -05 -06 , v a l u e = 0 . 0 3 d a t e : 2 0 1 1 -05 -07 , v a l u e = 0 . 0 2 d a t e : 2 0 1 1 -05 -08 , v a l u e = 0 . 0 2 d a t e : 2 0 1 1 -05 -09 , v a l u e = 0 . 0 1 P o(w) = 47.84 x(w) = 6.63E -4 σ(w) d = 0.0021 Z(w) d = 30.25As we can see w belongs to [40-50 [ and the threshold for this bracket is equal to 10, Z(w) 2011-05-02 is more than 3 times the threshold. On the 2011-05-02, the word 'bin' has been detected as a volcanic trend. Now let's try to investigate inside opinions. First of all, the list below contains some topics created on 2011-05-02 containinig 'bin':

Figure 6 :

 6 Figure 6: p( bin )

Figure 7 :

 7 Figure 7: p( halloween )

Figure 8 :

 8 Figure 8: p( valentin )

Figure 11 :

 11 Figure 10: p( japan )

Figure 15 :

 15 Figure 15: p( swayze )

  value = 'laden' and family = date and qualier = 2011-05-02, the standard notation for this data is 'laden',date:2011-05-02 d a t e :2011 -05 -02 t i m e s t a m p = 1

R e s u l t s r e

  s = z-s c o r e A l l E v e n t . g e t ( r G e t ) ; get all families for a given row Get r G e t = new Get ( B y t e s . ToBytes ( ' rowValue ' ) f o r ( KeyValue kv : z-s c o r e A l l E v e n t . g e t ( r G e t ) . l i s t ) { b y t e [ ] q u a l i f i e r = kv . g e t Q u a l i f i e r ( ) ; b y t e [ ] f a m i l y = kv . g e t F a m i l y ( ) ; b y t e [ ] v a l u e = kv . g e t V a l u e ( ) ; } get all the rows and scan the entire table R e s u l t S c a n n e r s c a n n e r = t a b l e O p i n i o n s . g e t S c a n n e r ( new S c a n ( ) ) ; • Training component: We implemented this component to support all the statistical training methods, and address issues like the zero-frequency problem thresholds. This component accesses the data-set oine and is never used in production mode.

Figure 17 :

 17 Figure 17: Overall system architecture

Table 1

 1

	Table 1: Bracketing content
	[0-5[ ∪ [5-10[	[40-50[	[90-100[
	aaarghhhhh	absolut	age
	aand	appreci	agre
	aandolan	besid	allow
	aang	cheer	anim
	aani	common	anyon
	aap	confus	anth
	aapent	coupon	babi
	aapko	delet	bad
	aar	dirti	ban
	aaramerican	disappear	befor
	aarcheri	disast	believ
	aardvark	employe	book
	aargghhhhh	especi	brand
	aargh	exact	buy
	aaron	expert	call
	badtast	avor	car

shows a subset of the words within the rst, second and the last brackets. Many of these words are misspelled or are not proper words per se (they can be names or parts of names). Yet even these are interesting because they come from new events that are suddenly occurring, examples include:'DSK','bin','laden','osama','swayze'.

Table 4 :

 4 Zero frequency threshold

	Value
	8.91E-4
	You can see that on 2010-08-02 this word can be elected as a trend.

The common way to solve this problem is to eliminate zero values and to consider that this word appeared like others (Laplace estimator).

  As per this algorithm, once w is identied as a trend, we try to nd the best collocation that involves it.

	Algorithm 3 ndCollocationCandidate
	w, window, candidatesList;
	for event ∈ topic(w) ∨ poll(w) do
	for i = 0 → event.text.size do
	for j = i + 1 → min(event.text.size, window) do
	col ← event.text[i] ∪ event.text[j]
	if col ∈ candidatesList then
	candidatesList(col) + +
	else
	candidatesList ← col
	end if
	end for
	end for
	end for
	if candidatesList = ∅ then
	return max(candidatesList)
	end if
	return w
	w is a trend
	return f indCollocationCandidate(w, 5)
	end if
	end if
	else
	if Z(w) d ≥ threshold(P o(w)) then
	w is a trend
	return f indCollocationCandidate(w, 5)
	end if
	end if

Trends detection d, nbD(w), c(d), P o(w), Z(w) d , f (w) d , t d , p(w) d ; zeroF req ← 8.91E -4 if P o(w) ∈ [0 -5[ then if p(w) ≥ zeroF req * 10 then if Z(w) d ≥ threshold(P o(w)) then

Table 5 :

 5 Interesting Trends

	w	d	top collocations
	swayze	2009-09-15	dirty patrick -dancing patrick -patrick cancer
	kanye	2009-09-15	beyonce opinion
	joanna	2009-05-07	war lumley -ex lumley -gurkha lumley
	lockerbie	2009-08-20	crime believe -people crime -released crime
	swine	2009-04-30	phase u -u die
	japan	2011-03-11	japan people -earthquake japan -tsunami japan
	vat	2008-11-26	spend money -spend reduction -spend vat
	sachin	2010-10-11	surely overs -current overs -player overs
	veterans	2010-11-11	thank day -veterans day
	lebron	2010-07-09	lebron cleveland -miami cleveland -fans cleveland
	anna	2011-04-08	hazare anna -anna hazare -anna corruption

Table 6 :

 6 Japan earthquake

•

  Trend Detection component: This component is one of the critical part of the system, it reads data from the database, and extract trends. It interacts with the Stemming, Utils (described later) and Base Components.• Utils component: This component contains all the utilities used during the analysis stage as well as the formatting utilities needed for displaying the results in the user interface. Examples include export to CVS,XML,TXT, export into log le, ArrayList, HashTable (increment element, sort, ...),

	String util methods (cleaning a String, date to String format, ...), common
	database operations (set a connection, queries, ...), math utils (mean,
	standard deviation, number of day between two dates, ...). It interacts
	with the Trend Detection, Web (described later) Components.

http://snowball.tartarus.org/

http://lucene.apache.org/

ACKNOWLEDGEMENTS 29 training, it was better but for the rst bracket (greater than zero and less than Acknowledgements I am thankful to the Department of Computer Science at Paris 6 University for providing me with a rich environment and giving me the opportunity to graduate in one of the best institutions in the world. Many thanks to my advisor, Philippe Trebuchet for his advice on my research and this work, Philippe has been an inspiration for me both professionally and personally and it was a real pleasure to work with him. I would like to also thank Frank Smadja for his insights on text analysis and collocations, and Yoelle Maarek for having the patience to proofread this report and make dozens of useful comments. Many thanks to my brother Jeremy for sharing my passion with trends and for challenging me with common sense questions.

f o r ( R e s u l t r e s = s c a n n e r . n e x t ( ) ; r e s != n u l l ; r e s = s c a n n e r . n e x t ( ) ) { } When we started this project, as were coming from the MySQL world, the transition to HBase was not trivial. The issue was not in exporting the data from MySQL tables to HBase but rather in re-designing the architecture. We started with four MySql tables Polls, Opinions, Topic and Answers and we designed our HBase architecture (Table 7) in order to be able to answer to this kind of questions:

How much topics was created at a given date? What are the opinions linked to a specic topic? Hbase is based on HDFS (Hadoop Distributed File System) which is a portable le system written in Java for the Hadoop framework. While

HBase is the open-source equivalent to Google's proprietary BigTable, HDFS [START_REF] Radia | Yahoo! hdfs under the hood[END_REF] was initiated by Yahoo! as an open-source answer to Google File System (GFS) [START_REF] Ghemawat | The google le system[END_REF].

Finally, we needed a last piece in order to handle additional tasks inherent to distributed needs such as conguration, naming and synchronization tasks. All these are critical when running on a large cluster, with constantly failing disks, failing servers, replication and shifting roles between nodes.

• Zookeeper

We chose to use Zookeper [START_REF] Junqueira | Zookeeper: Wait-free coordination for internet-scale systems[END_REF] for this purpose. Zookeeper is used here to synchronize the HBase database and allow clients to locate the adequate region server. It ensures that only one master is active and also improves eciency by preventing inactivity after opening a table.

Software architecture

This system comprises the following components:

• Stemming component: Rather than re-implementing for instance the Porter's algorithm for our own stemming component, we used the Snowball opensource package, which provides the most commonly used English stemmer.

Note that we reduced our analysis to English content only at this stage.