We use Common Crawl's 25TB data set of web pages to construct a database of associated concepts using Hadoop. The database can be queried through a web application with two query interfaces. A textual interface allows searching for similarities and di erences between multiple concepts using a query language similar to set notation, and a graphical interface allows users to visualize similarity relationships of concepts in a force directed graph.
What do Apple and Samsung have in common? What does Java have that PHP does not have? Which terms could re ne the search query \lance armstrong"? What is the context of the sentence \Food, games and shelter are just as important as health"? You may know the answers to these questions or know where to look for them|but can a computer answer these questions for you too? This paper discusses Traitor, a tool that creates a database of associated concepts, and answers questions similar to our examples. Traitor was created for submission to the Norvig Web Data Science Award1, a research challenge organized by Common Crawl and SURFsara. We won the award.
have been used for similar purposes before. To do this mining, we have implemented a map-reduce program in Java with Hadoop. For simplicity, the program assumes that one word represents one concept (and vice versa), and for every pair of words that co-occur in a sentence, the concepts they represent are associated.
In a few steps our program transforms the raw HTML
responses from the Common Crawl data set to a list of key
value pairs (k; v), where the key k is a word pair (w1; w2)
that co-occurred in some sentence on the page, and the
count v denotes the number of pages on which this
cooccurrence has been found. We consider the count of
cooccurring word pairs a measure of the association's strength.
A more sophisticated approach such as a probabilistic[
We chose sentences as the semantic unit (rather than the
same paragraph, document or a sliding window[
In the mapping phase we extract distinct word pairs from documents. We extract \interesting" text from the raw HTML documents using the BoilerPipe library; i.e., text in navigation menus, headers and footers is omitted. We then split each sentence in the text into a set of words and normalize these words by converting them to lowercase ASCII characters (e.g., a and A become a). This reduces the number of generated word pairs and compensates for small notation di erences between words. Moreover, we discard words from non-English sentences2, words containing non-alphabetic characters, and stop-words such as \the" and \that". For each normalized and ltered sentence S, the mapper creates a word pair p for each3 pair of words (w1; w2) where w1; w2 2 S, w1 < w2 (lexicographically). Finally, for every web page, the mapper emits tuples (p; 1) for each distinct word pair p on that page.
In the reduction phase, we sum the counts of the word pairs produced by the mapper. Because the distribution of words follows a Zipf distribution, we nd that the majority of the resulting pairs have a very low count. To reduce 2Our heuristic is rather crude: we check if a sentence contains at least two English `stop-words'. 3We limit the number of pairs produced for excessively long sentences. storage costs of the nal output, we can discard pairs with a count less than some N ; e.g., if N = 2, we discard all pairs that only occur once. Essentially, this allows us to reduce the output to any size that is practical for use in the presentation layer. Unfortunately, pairs containing rare words are cut indiscriminately due to this policy, even if these co-occurring words are still usable associations. 3.
The resulting tuples from the map-reduce step are imported into a database which can be queried through a web application with two query interfaces. 3.1
Users of the textual interface can search for similarities and di erences between multiple concepts using a query language similar to set notation or boolean algebra. For each search term in the query, associated words and cooccurrence counts are fetched from the database, and a score is assigned to each associated word based on the structure of the query expression.
A sequence of words separated by whitespace denotes a conjunction and yields the words that are associated with all words in the sequence. A sequence of words separated by plus-symbols, denotes a disjunction and yields the words that are associated with any word in the sequence. A word preceded by a minus-symbol denotes the complement. To illustrate: the query (a + b) -c yields all words that are associated with a or b, and not with c. 3.2
A graphical interface allows users to visualize
similarity relationships of concepts in a force directed graph using
D3.js. Users can enter a list of words which become labeled
nodes in the graph. The graphical size of the nodes
indicates the number of associations a concept has; the more
associations a concept has, the bigger the node. For each
word in the query the system retrieves the 50 strongest
related concepts, which can be interpreted as an estimate of
the concept's context. For each word pair we apply the
RBO metric[
Using our map-reduce program, we populated an association database with over 43 million distinct word pairs. We attempted to assess the quality of the Traitor's query results by answering questions from this paper's introduction (and others). For the sake of brevity, table 1 shows a few query results produced by Traitor. Additionally, to illustrate the disjunctive operator, we could `deduce the context' of a sentence; the query \food + games + and + shelter + are + just + as + important + as + health" produces the union of each word's associations: care, insurance, information, play, good. The reader is encouraged to try Traitor on-line for more example queries (see the Aboutpage) and for a live demonstration of the visualization interface.
apple iphone ipod ipad store mac apple samsung phone
tv mobile battery iphone java -php applet(s) alden jvm co ee marketplace samsung phone galaxy mobile battery
tv lance armstrong tour cancer france foundation
team java coffee -php cup bean beans
tea espresso java code application(s) games software programming political party information parties policy third government wii -xbox balance
kart nunchuk
resort motionplus data to about 10 gigabytes of uncompressed word associations by aggressive ltering of the input, and dropping all pairs with a count less than 100. By means of a query language and a simple scoring algorithm, we can express and answer queries about the concepts and associations stored in this database. A visualization interface allows for comparison of concepts by the similarity of their associations.
Despite the simplistic methods used, Traitor can provide reasonable results thanks to the large data corpus. As discussed in Section 2, we expect that a probabilistic scoring model can further improve the quality of our results. Moreover, Traitor only supports `concepts' described by single words; one could extract n-grams from sentences to identify concepts described by multiple words. Future work can include further normalization of words; e.g., equating plural and singular words, or applying word stemming.