Wednesday, August 8, 2012

Crowdsourced line wait-time forecasting using smartphones

Have you ever been frustrated with the unpredictability of the coffee shop line waiting times? I have, and far too many times. (I am fast growing into a grumpy old man.) I frequent the Tim Hortons coffee shop at our Student Union at University at Buffalo. Sometimes I would walk there to grab a quick mocha only to find a long waiting line and I would have to walk all the way back with empty hands. One day it hit me that this is a perfect opportunity to put our research on crowdsourced coordination and collaboration using smartphones to good use. We proceeded to develop Android and iPhone apps that forecasts the current (and near future) line waiting times at this coffee shop.

In the first version of our app, we asked users to manually provide line wait-times when they are waiting in line and tried to serve other users with the data input by these. Our model was: "if you used our app 5 times to get wait-time forecasted, before you can use it again, we ask you to report the wait time from the coffee-shop". (We checked the accuracy of the report using the localization information from the phone to prevent users to makeup wait-times.) We quickly noticed that this is an extra work for the users and the data arriving from the volunteers is too sparse to serve satisfactory results to the queriers. In the later versions of our service, we automated the line wait-time detection by using the localization capabilities of the smartphones in an energy-efficient manner.

Here is how our service works now. When the user wants to learn the current wait-time for the coffee shop, she fires our app and our app contacts our AWS cloud backend to provide this information. Then our app takes this as a clue that the user is interested in going to the coffee shop and starts tracking the user in the background. (This is done in an energy-efficient manner, the app gets a localization on the user more frequently as the user gets closer to the coffee shop, or else the localization requests gets more spread out and eventually dropped. The phone localization module fuses information from GPS, wifi, and cell tower triangulation to this end.) When the user enters the coffee shop, the app records the arrival timestamp. After the user is served and leaves the coffee shop, the app records the departure timestamp, and transmits this information to the cloud backend as another data point.

The backend stores and processes all the reported data to obtain models for waiting times at the coffee shop. For this, we first devised a solution based on a constrained nearest-neighbor search in a multi-dimensional (week of the year, day of the week, time of the day) space. Later, we improved on this solution by adapting two statistical time-series forecasting methods, namely exponential smoothing and Holt Winters. This actually turned out to be an interesting modeling problem due to the sparseness and false-positives in the collected data. (Some users choose to sit at the coffee shop after being served and this creates false-positives that we need to weed-out.)

Our line wait time forecasting apps for Android and iPhone platforms are downloaded by more than 1000 users in our university, and are used on a daily basis by hundreds of users to monitor the line wait-times of the Tim Hortons coffee shop. (We have recently added Starbucks to our service as well.) And, the punchline is our service provides line wait-time estimates that has mean absolute error of less than 2 minutes!

The paper (to appear at MobiCase'12) is available at:
Link for the Android app:
Link for the IOS app:

Two-phase commit and beyond

In this post, we model and explore the two-phase commit protocol using TLA+. The two-phase commit protocol is practical and is used in man...