Elasticsearch

How nice it is to decide that I need to either amateurishly build
or find an implementation of some advanced data structure for TechM
that I would need to then amateurishly build on top of to fully support this project,
a problem which caused forward motion to cease entirely
due to initial dev designing and general confusion and lazy reluctance,
only to serendipitous-ly discover that a comprehensive guide -
on a powerful service using that same advanced data structure at its core (and then some)
that I had discovered a month ago but hadn't figured out what to make of at the time -
has been released today and should guide me on how to solve my problem entirely
(and then some).

How nice - levering technology to solve an existing problem,
rather than some premature optimization.

v0.1

Here is a screenshot of the first version of TechM (shown on the 'Technology' section tab). The client has been implemented in Ruby on Rails and HTML/CSS, with intentional avoidance of JS for now (ending my philosophical tech debate temporarily). A few things you can't tell from the screenshot:

• An asterisk (*) next to an entity indicates that the entity represents an entire cluster of similar entities. Hovering over the entity will display the rest of the cluster in a tooltip.
• Hovering over any entity will display related article titles, also in the same tooltip (this 'feature' is only for creative purposes - it allows me to visualize the importance of article titles with respect to the context of each entity and trending topic, moving forward. I have no intention of showing article titles in a tooltip in a released version of the product, however.)

The second bullet point above really hints at the major advantage of this UI: allowing me to visualize the data in a more sophisticated way than I could previously. This is a nice step up from staring at the data in JSON format.

This version is not good enough for release for several reasons:

• Obviously, the color scheme is fairly horrendous. I have yet to settle on a good one.
• Many of these entities aren't useful without more context. Seeing a pile of entities related to each trending topic doesn't inspire me to continue clicking around and exploring the trending topic. This is a huge problem that I clearly need to improve upon.

Here are some thoughts for improvement:

• Assign weights to clusters based on # of entities in cluster & entity frequencies and show only information related to weightiest cluster, a combination of entities + related articles
• Only collect the named entities that occur *directly after* the trending topic in an article title... ('meh' on this idea)
• Use a POS tagger so that instead of showing entire article titles after showing important entities, just show verb phrases

I'm also going to start using git branch to explore these options for how to display the data.

Overall though, it's exciting to have a working prototype of some sort! Even though it is very rough and needs more work.

Structure of the data layer

Section, Ttopic, Cluster, Entity, Article - these terms are mirrored as classes in my Python code. The image above is a visual representation the structure of my code at this time.

As one can see, the structure is tree-like, except for two exceptions noted along the right-hand side - trending topics (ttopics) and articles should probably not be restricted to belonging to a single section and entity respectively. I am still working on implementing this behavior, and it is not represented in the image above, but it would mean that leaf nodes on the ttopic and article levels would branch upwards as well.

Below is a quick description of the utility of each class:

Section
pulled directly from Google News, these are the available news sections: Top Stories, World, U.S., Business, Technology, Entertainment, Sports, Health, Science.

Trending topic (Ttopic)
also pulled directly from Google News but dynamically changing, these are the most popular news topics for each section at any given time (similar to Twitter's trending topics which show keywords 'tweeters' are using more or growing fastest)

Article
news articles pulled directly from the Google News RSS feed for each ttopic. instead of associating articles with a ttopic directly, they are first associated with the entities (discussed below) that were extracted from them (this is what causes repetitive use of a single article between entities).

Entity
short for the concept of a 'named entity' from the information extraction world. words from article titles categorized as the names of persons, organizations, and locations with the help of Stanford NER from The Stanford NLP Group (there are other predefined categories that are not currently used in this project). once identified, entities are tallied by frequency per ttopic using PrefixSpan.

Cluster
a wrapper for entities. groups similar entities for a ttopic to mute redundancy in information displayed on future client.

Technology soup

From Medium:

In comes node.js, it seemed cool and would achieve what I wanted so I decided to start again...
I decided to have a client-side app and render the views in the browser as it was the “in thing” to do. I used all the goodies available to me such as Backbone, jQuery, Bootstrap and component. This tied to a node server running express.js and mongodb. To top it all off I wanted to be cool so I wrote the whole darn thing in CoffeeScript.

Now that TechM's data layer is solid enough for prototyping purposes (ahem, sans testing...), I'm trying to figure out how the heck I should connect to and develop for the client application. My mind, my Google searches, and my Trello board are all starting to reflect the chaos quoted above, scarily enough. I'm kinda getting lost in the sauce.

The thing is, I want to strike a balance. I want to learn new web technologies this summer, but I also want a working prototype by the end of the week... and between CouchDB + Node.js + Express.js + Mustache + jQuery + Flat UI Kit + ???, none of which I really know, it's looking pretty bad.

What I do know is Ruby on Rails... but I've already developed extensively with it. I also think it's too heavy for what I want to accomplish. But I'm missing the comprehensiveness of Rails, I think. With node.js, every component is customizable and needs to be installed individually via npm, and I haven't yet found a recommended, standard configuration of tools. I haven't found any ridiculously thorough tutorials for node.js yet either (like Michael Hartl's exceptional Rails tutorial).

PrefixSpan to the rescue!

Just when I had buckled down to concoct some crazy algorithm from my own head.

Just when I had written off my internship experience in Kyoto as wholly irrelevant to my life beyond that summer of 2012.

As it turns out, I have already spent extensive time "combining entities" (as I clumsily put it on my Trello board), only back then it was defined in much more elegant and precise terms.

My Problem Space

So since last night, my Python code 1) gathers the trending topics of each major news section on the Google News aggregator, 2) using these topics as queries, executes a search via the GN RSS feed for each query, 3) parses the RSS feed of each topic for all associated article titles, 4) uses named entity recognition (NER) to extract significant words in the article titles, and 5) computes the occurrence frequency of each unique named entity over a single topic.

The problem was that there was a lot of redundancy in each entity list. For example, my sample topic for testing was "Kim Kardashian," and (in honor of Kim and Kanye West's new baby) entities included:
- "North West" (6)
- "North" (3)
- "Baby North West" (2)
- "Baby North" (1)
- "North West Updates" (1)
- "Might Introduce Baby North West" (1)
- "Released Fake Pictures of Baby North West" (1)
- "Kanye West Explains Meaning Behind North" (1)

Wouldn't it be nice if we could get a more pronounced, less scattered sense of the buzz surrounding this new baby girl?

Enter: PrefixSpan

"PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth"
by Jian Pei, et al. (2001)

I honestly can't remember much about how the PrefixSpan algorithm works, and so I plan on revisiting this paper tonight. But let it be known: this is not a trivial algorithm - to think about or to implement.

Seriously, who knows how much time I might have spent (wasted?) rolling my own algorithm, or searching Google with all the wrong keywords, had I not recognized that I've seen this problem before.

Anyway, the tl;dr for the algorithm is as follows:
... [TODO] ...

Here's a diagram I created for my project's final presentation that represents the fundamental structure of the code:

And here is an illustrated example of how the algorithm works (courtesy of a slide from a previous intern working on the project I temporarily took over):

With a naive, out-of-the-box implementation of PrefixSpan that I found online, the example problem above is condensed to:
- "West" (24) *
- "North" (16)
- "North West" (11)
- "Baby" (6) *
- "Baby North" (5)
- "Baby North West" (4)
- "Baby West" (4) **
* includes other occurrences not listed above
** an unexpected result [UPDATE 7/2/13: modified algorithm to prevent this]

Yes, this list is nearly as long - but it is clearly more focused, and the counts provide sharper demarcations.

Lesson Learned

The value of gathering exposure to all kinds of algorithms.

I am a robot

...sigh. How does newsmap do it..? Hmm. I don't think it's my use of the RSS feed but rather the rate of my use of the RSS feed today. I was doing a lot of iterating and testing.

UPDATE: yay, the block was released by morning! so...

Lesson Learned

Impose a rate limit on myself before a rate limit is imposed on me.
Iterate and test on local copies.

Trello

I grew fond of Trello for organizing workload and assigning responsibility within my five-person team during CS 210, and so I have returned to it for my current project, despite being a team of one this time around.

New board started today!