# Using a Kalman Filter to Predict Ticket Prices

Welcome back! In case you missed part one of this series, we’re opening up the hood on Deal Score, one of SeatGeek’s most popular features.

In part one we gave a brief overview of why we sort ticket listings by Deal Score rather than by price. We gave you our two main assumptions:

• Seat quality, within a given venue, has a consistent ordering.
• The relationship of seat price to seat quality follows a similar pattern across all events at a given venue.

In the last post we discussed how we take advantage of the first assumption. Today, we’ll explain the second assumption and how it leads to the accurate valuations of thousands of tickets on a daily basis.

This second assumption means that all we need to do in order to predict prices is find a function, unique to each event, that maps our seat score vector to a vector of expected prices. Since we’re working with limited data here and surely do not have enough data to induce the structure of this curve for each event, we make a further simplifying assumption: for each venue, the curve will look similar for every event at that venue, whether that curve is a straight line, polynomial, or otherwise.

This does not mean that we can assume that a premium seat will carry the same relative premium over a nosebleed for each game. For a game that will not sell out, for example, the value of a nosebleed should be negative–this ticket will not sell, and given the additional expenses involved in attending an event (gas, parking, food, etc.), someone would have to be paid in order to sit in that seat. In such a situation, box seats are infinitely more valuable than bleachers. For a premium game, on the other hand, such as a playoff game, opening day, or any game at Fenway Park, all seats will sell out, as there is significant value just getting through the gates to see the event. Perhaps the box seat is only worth two or three times as much as the nosebleed in these cases.

At this point, we break out a terrific tool for processing small amounts of noisy data, the Kalman filter. Heavily used in the guidance and control of spacecraft and aircraft as well as with time-series data in economic and financial spheres, the Kalman filter is an algorithm that uses state estimates of model parameters combined with estimates of their variance to make predictions about the output of a linear dynamic system. I’ll spare you the obligatory rocket science joke and jump straight into a tutorial on how to use a Kalman filter to make predictions in the face of noisy and limited ticket data.

Since every observed price is going to be the output of a noisy system at a point in time, we are most interested in the likely state of the system as of the last observation, making a recursive estimator such as the Kalman filter an excellent choice.

## Step one: model the system

In SeatGeek’s case, our assumption is that the underlying structure of price dynamics is similar across events, and we can therefore generate a curve mapping seat quality to expected prices using the same parameters on the curve each time. As an example, here is a plot with seat scores for Knicks games at Madison Square Garden on the x-axis and historical average sale price for those seats on the y-axis.

I’ve added a best-fit line, which shows that sale prices tend to grow exponentially with seat quality at this particular venue. As such, we will model our price predictions as log-linear with respect to seat quality. We’re about to do a lot of math here, so feel free to skip ahead.

The Kalman filter maintains the state of the filter at step k with two variables:

• $\mathbf{\hat{x}_{k}}$

: the parameters of the model given observations up to and including step k

• $\mathbf{P}_{k}$

: the covariance matrix of parameter errors, a measure of the confidence the model has in its parameters

In our simple case, $\mathbf{\hat{x}}$ represents the intercept $\hat{x_1}$ and slope $\hat{x_2}$ of our line. $\mathbf{P}$ represents the covariance of parameter errors. This covariance matrix will be used down the line to determine which parameters must change when we make a new observation. It will also determine the magnitude of the adjustment.

A general Kalman filter uses a state-transition matrix $\mathbf{F}$ in order to advance from one observation to predicting the value of the next.

Where: $\mathbf{x}_{k\|k-1}$ is our best estimate of $\mathbf{x}_k$ given observations up to and including $k-1$. $\mathbf{w}_{k}$ is white noise of the same dimension as the model, drawn from a multivariate normal distribution having covariance $\mathbf{Q}$, representing the process error. Many applications of the filter model physical systems that take velocity and acceleration into account (and behind the scenes, so does SeatGeek). In these cases, $\mathbf{F}$ can include time-varying parameters, but in our simple example, we set:

Assuming that in between observations the underlying model dynamics do not change according to any known physical system, we use the identity matrix.1

## Step two: model the output

Sharp eyes may have noticed that the preceding equation does not use our lovely seat scores quite yet. The reason is our observations do not come in the form of linear models, but rather in observed fair values for seats, i.e. when users express an intent to buy. We have to model our output as $\mathbf{z}_k = \mathbf{H}_k \mathbf{x}_k + \mathbf{v}_k$, where $\mathbf{H}_k$ is a 1x2 matrix $\begin{bmatrix} 1 & \theta_k \end{bmatrix}$, theta being the rating of the seat in question. Keeping with Kalman filter assumptions we model our residuals, the difference between our observations and predictions, as Gaussian white noise.2 In the single-output case, the observation noise can be thought of as the square of our standard estimation error, or how far we allow our predictions to be off before the model updates itself. This variance, $\mathbf{R}$, will be used later on when we update the model.

## Step three: predict

Now that we have a model of our system, we can start making predictions. Using historical data, we can generate $\mathbf{x}_0$, our default parameters, and start predicting prices. Our prediction, of course, is that our observations will lie on the line defined by $\mathbf{x}_0$, shown in the image above. In this case, $\mathbf{x}_0 = \begin{bmatrix} 7.2356 \ , \ .1428 \end{bmatrix}$.

We add those parameters to our listing feed, determine seat quality from the data provided to us by the market in question, and predict a price for each listing. We compare the predicted price to the listed price, assign a Deal Score to each listing, and sort your search results accordingly. We live to fight another day.

## Step four: observe

Market dynamics, however, are not so kind as to stay constant, and our models, alas, are unable to perfectly predict every price from the outset. The Kalman filter is thus useful for responding to changing tides. Since observations of changing tides can be few and far between and must inform our predictions on all other tickets, it behooves us to have a degree of certainty about our model, which we represent by $\mathbf{P}$, the 2x2 covariance matrix of our state estimate errors. A good design decision is to start off $\mathbf{P}_0$ with large numbers on the diagonals and zeroes elsewhere, assuming low certainty of model parameters and independence.2 The filtering process should be able to give you excellent color on their true relationship.

Many of the signals discussed in part one can be interpreted, directly or indirectly, as a fair ticket price, and when we observe a new price, $\mathbf{z}_k$, we model the residual as $y_k = \mathbf{z}_k - \mathbf{H}_k \mathbf{\hat{x}}_{k\|k-1}$ where $\mathbf{H}_k \mathbf{\hat{x}}_{k\|k-1}$ represents our predicted price for that seat. In the Kalman filter, the residual variance (variance of $y_k$) is modeled as $\mathbf{S}_k = \mathbf{H}_k \mathbf{P}_{k\|k-1} \mathbf{H}_{k}^{\mathbf{T}} + \mathbf{R}$. In the general case, these are covariance matrix. Since our model outputs only one value, a predicted price, $\mathbf{S}$ and $\mathbf{R}$ are variances. $\mathbf{R}$ we have seen before, this is the general model of our error variance. $\mathbf{S}_k$ is the variance of this particular observation, which varies depending on the seat score of this particular observation (see dotted lines in the slideshow below). Variance is higher on expensive tickets than it is on cheaper tickets. We will use the residual and its variance in the next step to order to update our parameters.

## Step five: update

We now come to the key element of the Kalman filter, the gain. The gain takes our a priori estimate covariance $\mathbf{P}_{k\|k-1}$, our observation model $\mathbf{H}_k$, and our residual variance $\mathbf{S}$ in order to decide how much we should change our model parameters before the next prediction. Our optimal gain is $\mathbf{K}_k = \mathbf{P}_{k\|k-1} \mathbf{H}_{k}^{\mathbf{T}} \mathbf{S}_{k}^{-1}$. Kalman gain is a bit of a tricky nut to crack. If you think of the new parameters $\mathbf{x}_{k+1}$ as a weighted average of the old estimate $\mathbf{x}_k$ and the new observation, $\mathbf{K}$ provides the optimal weight for the observed residual in the new average.

If you’ve been following along, you can see that the larger our a priori uncertainty, the higher this gain factor gets. Now that we have a gain factor, we can start making some updates.

For the model parameters, this is easy. We simply scale the Kalman gain by the measurement residual, yielding us a new estimate. You can see here that if we guessed the price exactly, the slope and intercept do not change (a good sanity check) and that if we were fairly sure about the estimate beforehand, it requires a major miss before we update it substantially:

Similarly, we also update our error covariance matrix,

The error covariance update is a bit of a headache as well; the easiest way to think about it is to remember that $\mathbf{P}$ represents the covariance of our parameter estimation errors $\mathbf{x}_k - \mathbf{\hat{x}_{k\|k-1} }$ and to play around with what makes the changes in $\mathbf{P}$ large or small. For example, if the observation noise, $\mathbf{S}_k$ is very large, our gain will be small and our certainty will remain mostly unchanged.

Now that we understand how the filter works, let’s rejoin our original programming and see it in action!

## Putting it all together

The slideshow below takes you on a visual tour through several steps of the dynamic linear model. In all slides, the dark red line represents our estimate of the mapping from seat quality to expected price and the and the dashed lines represent our 95% confidence interval for the price.

Before concluding, I’d like to note that a major motivation behind this series was the lack of real-world Kalman filter examples out here on the internet, which is disappointing given its usefulness as an estimator, especially for low-dimensional time-variant systems with small data. Here are some of the better articles I’ve found:

I gladly welcome thoughts on our usage of the filter or critiques of my explanation from those who have a better handle on things. Leave a comment or find me on twitter @steve_rit.

## Notes

• 1: If we wanted to add time-variance to our parameters, we could use something like:
• 2: To cut down on the amount of notation, I’ve removed some symbols representing noise that aren’t directly used in the predict-update process.

# The Math Behind Ticket Bargains

Greetings from SeatGeek Research & Development!

I’m here today to take you behind the curtain of one of SeatGeek’s major features, Deal Score. For the uninitiated, Deal Score is a 0-to-100 rating that reveals whether a ticket is a great bargain or a major rip-off. We humbly believe it’s the best way to find tickets. I’d like to quickly tell you why and then spend most of this post discussing some of the math behind Deal Score’s calculation. This is the first in a series of two blog posts, the second coming soon.

## Sorting vs. Searching

Why have Deal Score? The standard across ticket sites is, of course, sorting by price. On most ticket sites, a prospective buyer can select sections they want to sit in, filter tickets by price range, and spend a solid chunk of their day trying to figure out the best seats for the money. On most aggregators, listings from several ticketing websites are lumped together… and then sorted by price, whereupon the experience repeats itself with the added pleasure of more noisy data.

SeatGeek, however, is more than an aggregator, we’re a search engine. Using Deal Score, we sort tickets by value rather than price. As a quick example, let’s try to find some tickets for the Red Sox-Indians game May 12th at Fenway Park. If I sort the tickets by price, I need to wade through dozens of cheap listings for standing room only tickets and obstructed view seats. Cheap for sure, but anybody who’s been to Fenway Park can tell you there are some places you just don’t want to sit. I need to be vigilant in order to notice a listing for two tickets in the grandstand behind home plate for $53, the same price level as a listing in the back of the bleachers and in two neck-straining outfield grandstand seats. How good of a deal is this? Sorting by price these three listings look the same, but behind the scenes SeatGeek’s proprietary price prediction has pegged these bleacher seats as being worth$29, the outfield grandstand seats at $34, and the infield seats at$69. Deal Score compares every ticket’s expected price to its listed price and takes the mental leg work out of ticket shopping.

The basic principle behind Deal Score is simple and intuitive: by searching rather than sorting, we can intelligently filter secondary market ticket listings, saving consumers large amounts of time and money.

## How does it work?

The most important element of our Deal Score algorithm is to accurately estimate the current market value of a ticket listed on the secondary market. Most marketplaces have large amounts of transactional data on their products, often with supply and demand-side pricing signals. SeatGeek is in the undesirable position of trying to predict, on a daily basis, the price of millions of event tickets that have, by definition, never sold. Each seat at every event is a unique product; while its eventual price is informed by many other signals, the secondary market is both opaque and noisy.

Given our data constraints and the precision necessary, we made two assumptions about seats:

• Seat quality, within a given venue, has a consistent ordering. This means that for any given Red Sox game, we expect that Infield Grandstand 18, Row 12 is a better place to sit than Center Field Bleachers 37, Row 37.
• The relationship of seat price to seat quality follows a similar pattern across all events at a given venue. This means that a curve plotting sale price against seat quality for a weekend Red Sox-Yankees game at Fenway Park should look similar to a curve for a midweek Red Sox-Royals game, even though the market dynamics would be quite different.1

The first assumption allows us to use signals from many contexts to inform our predictions. The second assumption allows us to make confident predictions about prices after seeing as few as five or ten prices for each event.  In today’s installment, I’m going to show you the math we use to derive a key metric called “Seat Rank,” the ordinal quality rank of all seats within a venue.

## Seat Rank

In order to make the most of our first assumption, we determine the intrinsic “seat quality” of each seat relative to all others. Teams and promoters deal with this every day; they have to set face values for tens of thousands of seats in a stadium, but they have the advantage of only needing to compute a few dozen price levels, at most. In contrast, secondary markets have row-level pricing granularity, and thus require us to understand how much each row is going to sell for on the open market. Fenway Park, for example, has 4,022 distinct section/row pairs, and we must understand how they all rank on a relative basis. Using a little bit of cleverness along with vector coordinate data from SeatGeek’s venue maps, we reduce the problem slightly: we divide each venue into clusters of seats (we call them “seat groups”) whose physical locations and sale prices tend to be close enough to each other that they can be modeled together. These seat groups allow us to make use of less data to predict more prices.   Some venues have as few as twenty groups; others, well into the thousands. Fenway Park has 993.

To understand Seat Scores, consider a simple example where the set of listings $\mathcal{S}$ consists of three seats indexed by $i$:

.

Suppose these seats are equally priced, despite the fact that their quality $\theta_{i}$ varies. In fact, $s_1$ is twice as good as $s_2$, which is twice as good as $s_3$. Without loss of generality, we arbitrarily set $\theta_{1} = 1$ and can define a vector $\Theta$ of relative seat qualities:

Unfortunately, while SeatGeek has a lot of data, we cannot directly observe the relative true quality $\Theta$ of these seats.  However, we use a group of  different signals, including clicks on “buy” buttons and the physical location of a seat within a venue, to arrive at an estimated quality $\hat{\Theta}$.  One of these signals is pairwise comparison.  Shoppers constantly make pairwise comparisons among seats. We use this tendency to our advantage.  In particular, we obtain our estimate of $\Theta$ by assuming that users’ historical choices are proportional to the true relative quality of seats, revealing information about the true $\Theta$. For simplicity’s sake, assume that:

For example, when faced with a choice between $s_1$ and $s_3$, users will pick $s_1$ with probability $= \tfrac{1}{1+ 1/4} = 80\%$. In reality, the data will be much noisier. Each data point is a random realization of their perception of relative seat values. Some pick the first listing they see, others have disparate opinions about what makes for a quality seat, etc.2

Continuing with the Fenway Park example, after processing our input signals, we have a square matrix $\mathbf{R}$ where each cell represents the processed results of pairwise comparisons between seat groups. In this matrix, $\mathbf{R}$, we define each cell $r_{i,j}$ as the observed relative quality $s_i$ as compared to $s_j$.

The rough values for $\mathbf{R}$ are fairly noisy, as shown in the matrix below. The matrix below is sorted left-to-right, top-to-bottom by the raw “winning percentage” of each seat in pairwise comparisons. Each cell represents, roughly, the fraction of the time that a user clicked on the seat in the row (y-axis) when the seat in the column (x-axis) was available at an equal or lesser price. A row with mostly red is a seat that “wins” many comparisons, a row with mostly green tends to lose.

The initial $\Theta$’s implied by these raw winning percentages are a good start, but these data are far too noisy to be used as reliable estimates. This is a visual representation of what Fenway Park looks like with these raw seat scores:

To estimate $\hat{\Theta}$ in the presence of noisy data, we use a method called maximum likelihood estimation, which iterates over candidate values for $\hat{\Theta}$ to maximize the probability of observing the real data. We start with rough parameter values, $\hat{\Theta}$ and follow the steps: (1) calculate the probability of observing the data conditional on these values3:

(2) adjusting the parameter values to increase this likelihood

Watch below as the seat scores converge from our initial values to the maximum likelihood (use the controls below to navigate):

Presto! Once we’re finished, we end up with something that looks very similar Fenway’s actual seating chart, only with much more granular distinctions on price levels. With these seatscores, we would expect $\mathbf{R}$ to look like this filled-in matrix instead of the noisy, sparse mess from above.

With these powerful seat scores in hand, we’re halfway to our goal of predicting accurate prices for live events at any venue in the country. Come back for our next post to see how we go from our seat scores to market value predictions for thousands of events every day. UPDATE: View part 2: Using a Kalman Filter to Predict Ticket Prices

## Credits

In case you’re wondering what technology we use for these projects, here’s a sampling:

• pandas: a python data analysis library, for signal processing
• R: for statistical analysis and postprocessing
• ggplot2: to make the heatmaps seen above

## Notes

• 1: If you read this far and wondered whether we were ever going to get around to this, then you’ll want to come back for part 2, when we explain how price predictions are derived from these seat scores.
• 2: Fenway park is actually a good example of this phenomenon, Green Monster seats in particular are heavily disagreed upon by our signals.
• 3: $r_{ij} = 0$ whenever $i = j$, so we need not exclude these cases.

# The SeatGeek Platform

Over the past two and a half years, we’ve poured countless time into building a canonical database of live events in the US. Not only have we cataloged when and where each event is happening, but we also built a system that attaches copious metadata to each event–e.g., the latitude/longitude of the venue, the number of tickets currently listed, etc. Thus far, that database has been used exclusively to power the pages on SeatGeek.com. But we musn’t be selfish! Thus, we recently announced The SeatGeek Platform. Developers can use the Platform to add live event info to existing apps or as a foundation for entirely new apps that deal with live events.

The SeatGeek Platform is composed of our event, performer, and venue data, a REST API, our Partner Program, and a developer support community. The API exposes a mother lode of live event info—nearly all of the data you see available on SeatGeek.com, plus a lot more. Full documentation is here. The Partner Program gives Platform users an easy way to monetize. Anyone who signs up earns a 50/50 rev share whenever a user buys tickets using one of their links. For current partners, that has worked out to about $11 every time one of your users buys a ticket. A few of us on the SeatGeek dev team are closely tracking posts on the support forum, so if you have any questions about the API, just post there and you will get a prompt, thorough response. How might someone use this thing? A quick example: Let’s say that Sarah runs a site for her indie record label, SBeats, which gets a lot of traffic from fans. Since the record business isn’t massively lucrative these days (shocking, I know!) Sarah is looking for new ways to monetize. She’d also like to add a bit more content to her label’s site. She uses the SeatGeek API to pull in data about which of her artists are touring. She displays that info in a module on each artist’s page. To give users a bit of context, she pulls the “low price” field from the API to show the cost of the cheapest ticket for each show. Whenever a user clicks on a link for a show and buys a ticket, Sarah earns$11, on average.

We’re pumped about this launch. For the first time, we’re exposing our data to developers everywhere. I can’t wait to see what people build.

# Removing Price Forecasts

When we launched SeatGeek back in the fall of 2009, we positioned ourselves as a site that forecasts how ticket prices move on the secondary market. That was our “one thing”: forecasts. Russ had spent months building scrapers to collect ticket data. I’d spent months messing with that data in STATA, building models that could accurately forecast prices. We figured we could get traction by helping consumers time their ticket purchases optimally.

Much has changed. The past two years have been all about expanding the vision (trite but true) of what SeatGeek can be. Four months after we launched, we moved from being a price forecaster to a price forecaster that also had pretty good ticket search. The ticket search was getting a better response from users than the forecasts, so we continued to focus on that. Five months after that, we launched our own interactive mapping platform. That really opened the doors on how we could approach ticket search. We created something called Deal Score, which allowed us to use a lot of the data and analytical tools we’d built for forecasts, and that got a great response. In 2011, we added dozens more ticket sellers to our search results. Near the end of the year, we’ve begun to make the leap into being a full-fledged one-stop site for live entertainment.

Through all of this, the forecasting feature has been lost in the shuffle. We’ve continued to support it, but it became a hassle rather than a cause for excitement. Most users stopped paying attention to it; the site had other things that were more compelling. We stopped mentioning it when we described what SeatGeek does. Forecasts ceased to be relevant to our core mission–making ticket buying elegant and simple. Optimally timing a ticket purchase is a complicated, tricky value prop and holds us back in our pursuit of removing complication from ticket buying.

Thus, within the next week or two, we’ll be removing price forecasts from our site. We want to avoid feature bloat. We need to maintain clarity of purpose, for both our users and ourselves. Drop us a line at hi@seatgeek.com if you think this is a terrible idea and if we get enough emails we’ll reconsider. Otherwise, we will begin 2012 without forecasts, which will help us focus on the things that matter most as we try to upend the way people attend live events.

# Performance Monitoring With Tracelytics

We’ve had great success at SeatGeek moving more and more of our software into independent services. Clear service boundaries have allowed us to improve our code quality, increase programmer productivity/happiness, open source a few things, and in some cases, drastically improve performance.

The flip-side is that with 3 or 4 different languages connecting to 3 or 4 different data stores, with the network between them, and all writing to different log files, it has become a lot more difficult to reason about performance. When you can render a page with a single (albeit complex) SQL query, it’s easy to know where to look when you want to improve response times. If rendering that same page means a simpler SQL query, plus an HTTP call to an external service which may in turn communicate with Redis, it’s a little bit tougher to figure out where you’re spending most of your time.

## StatsD and Graphite

Our first solution to this problem was a combination of StatsD and Graphite. Etsy has an interesting post about their usage of this combo. In short, StatsD + Graphite gives you a very simple way to time and count things, and then graph the results in realtime. Here’s an example chart of our tickets feed load times over the past 2 months or so. You can see the result of some performance improvements we made in mid September.

This is a pretty powerful setup. We’re measuring a ton of stuff using StatsD and Graphite, and it’s a great tool for letting you know where to start looking when investigating performance issues.

## Tracelytics

Recently we were lucky enough to take part in the beta of a new product called Tracelytics. While StatsD + Graphite can help you figure out where to look, Tracelytics comes right out and tells you exactly what’s wrong. Tracelytics is organized around the concept of a “trace”, which is a detailed snapshot of a specific request. A trace contains details about every layer of software involved in handling a request, even when those layers are separated by the network.

I can’t open Tracelytics without stumbling across a glaring performance issue, and I mean that literally. I just popped Tracelytics open to grab some screenshots for this post and realized that we were requesting the same object from s3 multiple times in a single request – not only did we have some bad logic which was grabbing the object over and over again, but because of incorrectly configured permissions, our per-server file cache for s3 objects wasn’t writable and so wasn’t working at all. Check it out (click to enlarge):

What you’re seeing here is the details view for a single trace. The timeline at the top shows timing information for various request layers. The bottom left is showing details about the currently selected layer (the darkest blue rectangle on the timeline), which happens to be an HTTP request to s3. I clicked on each of the other blue rectangles, and saw that they too were requests to s3. Not good. Now as if that weren’t enough information to get started on a fix, I can scroll down and get an exact stack trace for each call:

Remember the “performance improvements” from mid September that were illustrated in the Graphite screenshot above? Well that problem was actually uncovered and diagnosed with Tracelytics. I apologize for the crappy screenshot, but I took it just to throw in an email back in September (you can’t view historical data past a week in the Tracelytics interface yet – the data is retained, it’s just not exposed in the interface yet). Here is a heatmap view of the performance of a specific SQL query (click to enlarge):

This a very simple query pulling tickets out of a single table. We had indexes in the right places, but the query pulls a lot of data and the table has grown a lot, and probably wasn’t residing completely in memory anymore. We ended up upgrading our DB server to the next instance size and tuning some MySQL config parameters and were able to knock the average time for that query down from ~500ms to ~5ms.

Access to good data is integral to everything we do at SeatGeek, and Tracelytics gives us a ton of it, all in a very digestible way.

# The Minutiae of Web Interfaces: Realism

We recently embarked on a complete redesign of the core page on our site, our ticket listings interface. After weeks of iterating with the other guys on the SeatGeek dev team, I marched off to an interview with a reporter from a major tech publication to show off the new UI for an upcoming story. His reaction: “Well, that doesn’t really look very different.” Oof.

But he was right. The two versions looked quite similar:

Before (click to enlarge):

After (click to enlarge):

Yet, even though it looks damn similar, I would argue this was a big step forward for us. In isolation, the elements that distinguish outstanding UIs from good UIs often go unnoticed by users.

A frequent 1am scenario in my apartment: I’ve just spent 15 mins fooling around in Photoshop, trying to improve the design of a button.  I turn to my roommate and ask her which version she prefers.  She say she can’t even tell the difference!  Have I wasted my time? No. Holistically, this shit matters. A user can feel the difference.

We had four goals for this redesign: increasing the realism, usable real estate, simplicity, and unity among elements. But rather than discussing the rationale behind those, I’d like to cover some of the tiny, specific changes we made to accomplish them. The minutiae is important.

Here I’ll tackle how we attempted to improve the realism of the UI. I’ll save the rest for future posts.

## Enhancing realism

Great UIs are real, tactile things that make you forget your computer screen is a screen at all. They evoke real-world sets of objects, like a panel of elevator buttons sitting in front of you. We made a number of small changes to enhance realism…

### Texture

Few surfaces in the real world are truly monochromatic. The background of our old map (see above) was completely white; it felt artificial. We added a striped pattern that made it feel more organic. And few surfaces in the real world are devoid of imperfections, so we added noise to the pattern. Check out the random variations in pixel color in the closeup below:

**Pattern at normal zoom:**
**Pattern closeup:**

When asked “Do you notice any noise or imperfections in that pattern?” most users say no (I know, I’ve polled a bunch). But it subconsciously improves the verisimilitude of the UI. We also added noise to the ticket quantity selector background. Again, it’s difficult to consciously detect unless you zoom in:

**Quantity selector:**
**Background closeup:**

### Depth

The perception of depth is critical for creating a UI that feels like a real-world control panel rather than a computer screen. The real world isn’t 2D. Our old map felt flat, whereas the new version has more dimension.

**Old map** (flat):
**New map** (depth!):

We did a few things to give the illusion of depth. First, we added a drop shadow around the edge of the map. The shadow is positioned as if there is a 90° light source, meaning light is shining down on the interface from directly above. This has become the standard across mobile and web interfaces. The shadow is bigger and darker than most shadows we use, but still sufficiently subtle that most users won’t look at the interface and think “Oh, there’s a shadow.”

We also added a stronger gradient to the markers on the map:

**Old marker:**
**New marker:**

The stronger gradient evokes a marker that is spherically shaped rather than flat. If the marker were a flat disc, then light hitting the disc from above would look the same on all places of the disc. But if the marker was protruding off of the map, light from above would strike more of the upper half of the marker than the lower half. The stronger gradient conveys this.

We worked to give every element on the page a z-index relationship to the elements surrounding it. For text, that means deciding if it is sitting on top of its background element or if it will be embossed into that element. We tried to always select one or the other and avoid text that casts no shadow. As an example, check out the label in the upper-left part of the ticket listing element:

**Old version:**
**New version:**

The text in the old version had no shadow. In the new version, we used a white drop shadow on the bottom to convey that the text is embossed into the background. It gives the perception that light shining from above is passing over much of the label–since it’s sunken into the background–but that the light catches it at the bottom.

### Active/hover states

In the real world, an object tends to change its appearance when you interact with it. As you move your hand over a button in an elevator, the way light strikes that button will change. And when you press that button, the light will change yet again. Thus, to create a UI that feels real, we tried to make it consistently but subtly responsive to user actions. As a bonus, this gives users consistent feedback about when their actions are being recognized by the app.

Perhaps the most obvious way to enhance responsiveness is with hover and active states. We’re trying to give every clickable element in the SeatGeek app its own hover and active state (we aren’t quite there yet). As an example, consider the email alert button on the top bar of the ticket listings UI (refer to the screenshots above for a refresher):

The old button is on the left; the new button is on the right. You’ll see that while the old button had a hover state (underlining the text) it didn’t have a unique active state, so we created that for the new version. In the new version, the button color and shading changes in all three states. We’re also trying to get away from using text underlining for hover states. Buttons in the real world don’t underline themselves when you put your hand over them. An underline hover state is often unavoidable for links in body copy, but we got rid of it for buttons, like in the example above.

### Animation

Things in the real world do not instantly appear or disappear from sight; they move in and out of view with a certain velocity and acceleration. Thus, we added animations to the interface whenever it seemed suitable. We actively tried to avoid gaudy animations reminiscent of ‘90’s PowerPoint presentations; we wanted each animation to be on the brink of noticeable. As an example. when a user signs up for an email alert, the modal window fades and zooms in very quickly. This screenshot catches it mid-animation:

There has been much ado recently about how Steve Jobs cared about the aesthetics of computer parts users would never see. I’m not sure how I feel about that. (Where did it end? Did he he care about the beauty of chip internals?!). In any case, I’m talking about something very different here–changes that will be visible to users, but only when part of a cohesive whole. I think those details are the key to outstanding interfaces.

# What the SeatGeek R&B Star Devs Listen to While Programming

Devs are gonna dev. Coders gonna code. But they aren’t going to write blog posts, which is why I am here…except here, here, here, and here. Aight so they do some content work, but I can’t complain at all because they MAKE SeatGeek what it is. I just monkey market.

Programmers tend to prefer house, techo, electro, dub, metal, but let’s take a look at what music our actual developers are listening to on a day-to-day basis. In addition, I have aggregated some of the top threads from around the web at Reddit, HackerNews and other programmer hot spots and provided links to those at the bottom.

## Best Music to Code to - SeatGeek Edition

### Adam Cohen - of Bitcoin discussion fame and other musings

Who: Jamiroquai Genre: Funk/acid jazz Why: Driving beats, fast tempo, keeps you awake. All songs kind of sound the same. Want a soundtrack that blends together. Best Song to Program to:

### Michael D’Auria of homemade brew fame

Who: all hip hop Genre: Rap/Hip-Hop Why: 1. High energy 2. Bobbing heads = mad lines of code 3. 5 Milkshakes Best Song to Program to (explicit):

### Jose Diaz-Gonzalez, of Cake PHP fame

Who: The Mars Volta Genre: Psychedelic rock/free jazz (not sure what that means) Why: Many, many, many loud and obnoxious drums that I use to set the pace. Pisses off everyone around me, thereby making me a happier person as I suck the fun out of the air. Also, lots of variety, so I can work to various tempos and beats Best Song to Program to:

And…

### Eric Waller, The Fame

Who: fratmusic.com Genre: various Why: You’re not gonna not Best Song to Program to:

## Best Music to Program To - Answers Around the Web

### BONUS:This is what we partied to at the last SeatGeek party

Which you can find on Grooveshark here.

What do you listen to while programming? Does our dev team have it all wrong? Let us know on Twitter.

# What an Earthquake Does to Page Response Times

You might have heard – there was an earthquake in Virginia which was felt in New York City. Twitter is exploding with east-coasters experiencing their first earthquake.

Over here at SeatGeek, we were excitedly discussing the tremor when Mike, our trusty sysadmin, realized that our Amazon AWS servers were all in Virginia, right near the epicenter. Did it impact the service at all?

It turns, out, it did. For about six months, we’ve been using a combination of StatsD, Graphite, and GeckoBoard to power a real-time dashboard of some of our system stats. We walked to the front to of the office to take a look, and sure enough, we saw a pretty nasty looking page response spike.

## Lessons Learned

1. Earthquakes make Web Servers sad
2. Real time system monitoring is awesome

# FuzzyWuzzy: Fuzzy String Matching in Python

We’ve made it our mission to pull in event tickets from every corner of the internet, showing you them all on the same screen so you can compare them and get to your game/concert/show as quickly as possible.

Of course, a big problem with most corners of the internet is labeling. One of our most consistently frustrating issues is trying to figure out whether two ticket listings are for the same real-life event (that is, without enlisting the help of our army of interns).

To pick an example completely at random, Cirque du Soleil has a show running in New York called “Zarkana”. When we scour the web to find tickets for sale, mostly those tickets are identified by a title, date, time, and venue. Here is a selection of some titles we’ve actually seen for this show:

Cirque du Soleil Zarkana New York
Cirque du Soleil-Zarkana
Cirque du Soleil: Zarkanna
Cirque Du Soleil - Zarkana Tickets 8/31/11 (New York)
Cirque Du Soleil - ZARKANA (Matinee) (New York)
Cirque du Soleil - New York


As far as the internet goes, this is not too bad. An normal human intern would have no trouble picking up that all of these listings are for the same show. And a normal human intern would have no trouble picking up that those listings are different than the ones below:

Cirque du Soleil Kooza New York
Cirque du Soleil: KA
Cirque du Soleil Zarkana Las Vegas


But as you might imagine, we have far too many events (over 60,000) to be able to just throw interns at the problem. So we want to do this programmatically, but we also want our programmatic results to pass the “intern” test, and make sense to normal users.

To achieve this, we’ve built up a library of “fuzzy” string matching routines to help us along. And good news! We’re open sourcing it. The library is called “Fuzzywuzzy”, the code is pure python, and it depends only on the (excellent) difflib python library. It is available on Github right now.

### String Similarity

The simplest way to compare two strings is with a measurement of edit distance. For example, the following two strings are quite similar:

NEW YORK METS
NEW YORK MEATS


Looks like a harmless misspelling. Can we quantify it? Using python’s difflib, that’s pretty easy

from difflib import SequenceMatcher
m = SequenceMatcher(None, "NEW YORK METS", "NEW YORK MEATS")
m.ratio() ⇒ 0.962962962963


So it looks like these two strings are about 96% the same. Pretty good! We use this pattern so frequently, we wrote a helper method to encapsulate it

fuzz.ratio("NEW YORK METS", "NEW YORK MEATS") ⇒ 96


Great, so we’re done! Not quite. It turns out that the standard “string closeness” measurement works fine for very short strings (such as a single word) and very long strings (such as a full book), but not so much for 3-10 word labels. The naive approach is far too sensitive to minor differences in word order, missing or extra words, and other such issues.

### Partial String Similarity

Here’s a good illustration:

fuzz.ratio("YANKEES", "NEW YORK YANKEES") ⇒ 60
fuzz.ratio("NEW YORK METS", "NEW YORK YANKEES") ⇒ 75


This doesn’t pass the intern test. The first two strings are clearly referring to the same team, but the second two are clearly referring to different ones. Yet, the score of the “bad” match is higher than the “right” one.

Inconsistent substrings are a common problem for us. To get around it, we use a heuristic we call “best partial” when two strings are of noticeably different lengths (such as the case above). If the shorter string is length m, and the longer string is length n, we’re basically interested in the score of the best matching length-m substring.

In this case, we’d look at the following combinations

fuzz.ratio("YANKEES", "NEW YOR") ⇒ 14
fuzz.ratio("YANKEES", "EW YORK") ⇒ 28
fuzz.ratio("YANKEES", "W YORK ") ⇒ 28
fuzz.ratio("YANKEES", " YORK Y") ⇒ 28
...
fuzz.ratio("YANKEES", "YANKEES") ⇒ 100


and conclude that the last one is clearly the best. It turns out that “Yankees” and “New York Yankees” are a perfect partial match…the shorter string is a substring of the longer. We have a helper function for this too (and it’s far more efficient than the simplified algorithm I just laid out)

fuzz.partial_ratio("YANKEES", "NEW YORK YANKEES") ⇒ 100
fuzz.partial_ratio("NEW YORK METS", "NEW YORK YANKEES") ⇒ 69


That’s more like it.

### Out Of Order

Substrings aren’t our only problem. We also have to deal with differences in string construction. Here is an extremely common pattern, where one seller constructs strings as “<HOME_TEAM> vs <AWAY_TEAM>” and another constructs strings as “<AWAY_TEAM> vs <HOME_TEAM>”

fuzz.ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets") ⇒ 45
fuzz.partial_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets") ⇒ 45


Again, these low scores don’t pass the intern test. If these listings are for the same day, they’re certainly referring to the same baseball game. We need a way to control for string construction.

To solve this, we’ve developed two different heuristics: The “token_sort” approach and the “token_set” approach. I’ll explain both.

### Token Sort

The token sort approach involves tokenizing the string in question, sorting the tokens alphabetically, and then joining them back into a string. For example:

"new york mets vs atlanta braves"   →→  "atlanta braves mets new vs york"


We then compare the transformed strings with a simple ratio(). That nicely solves our ordering problem, as our helper function below indicates:

fuzz.token_sort_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets") ⇒ 100


### Token Set

The token set approach is similar, but a little bit more flexible. Here, we tokenize both strings, but instead of immediately sorting and comparing, we split the tokens into two groups: intersection and remainder. We use those sets to build up a comparison string.

Here is an illustrative example:

s1 = "mariners vs angels"
s2 = "los angeles angels of anaheim at seattle mariners"


Using the token sort method isn’t that helpful, because the second (longer) string has too many extra tokens that get interleaved with the sort. We’d end up comparing:

t1 = "angels mariners vs"
t2 = "anaheim angeles angels los mariners of seattle vs"


Not very useful. Instead, the set method allows us to detect that “angels” and “mariners” are common to both strings, and separate those out (the set intersection). Now we construct and compare strings of the following form

t0 = [SORTED_INTERSECTION]
t1 = [SORTED_INTERSECTION] + [SORTED_REST_OF_STRING1]
t2 = [SORTED_INTERSECTION] + [SORTED_REST_OF_STRING2]


And then compare each pair.

The intuition here is that because the SORTED_INTERSECTION component is always exactly the same, the scores increase when (a) that makes up a larger percentage of the full string, and (b) the string remainders are more similar. In our example

t0 = "angels mariners"
t1 = "angels mariners vs"
t2 = "angels mariners anaheim angeles at los of seattle"
fuzz.ratio(t0, t1) ⇒ 90
fuzz.ratio(t0, t2) ⇒ 46
fuzz.ratio(t1, t2) ⇒ 50
fuzz.token_set_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners") ⇒ 90


There are other ways to combine these values. For example, we could have taken an average, or a min. But in our experience, a “best match possible” approach seems to provide the best real life outcomes. And of course, using a set means that duplicate tokens get lost in the transformation.

fuzz.token_set_ratio("Sirhan, Sirhan", "Sirhan") ⇒ 100


### Conclusion

So there you have it. One of the secrets of SeatGeek revealed. There are more tidbits in the library (available on Github), including convenience methods for matching values into a list of options. Happy hunting.

# Announcing Soulmate

Have you ever felt so close to someone that it seemed like the two of you were finishing each other’s sentences? Well, as a Valentine’s Day gift to the community, we at SeatGeek have distilled some of Cupid’s magic into a Redis-backed service for doing exactly that: Soulmate is a tool for building fast autocompleters.

Give it a try right now on SeatGeek.

Inspired by Auto Complete with Redis, Soulmate uses sorted sets to build an index of partially completed words and the corresponding top matching items, and provides a simple sinatra app to query them.

Here’s a quick overview of what the initial version of Soulmate supports:

• Provide suggestions for multiple types of items in a single query (at SeatGeek we’re autocompleting for performers, events, and venues)
• Results are ordered by a user-specified score<
• Arbitrary metadata for each item (at SeatGeek we’re storing both a url and a subtitle)

Checkout the github repo for instructions on how to use it, or if you’re feeling saucy, just gem install soulmate.