Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
StarTrack

Overview

Tracks play a prominent role in a variety of emerging mobile applications from trip planning to online games to fitness monitoring. Consider a ride sharing application, for example. By recording and comparing the tracks of commuters driving to and from work, this application suggests co-workers that can potentially drive together, thereby reducing pollution, gas consumption, and traffic congestion. Similarly, tracks left by others might help someone new to an area discover interesting biking trails, determine safe places to walk, or indirectly share experiences with friends and family.

StarTrack is a system that enables extensive operations on tracks. A track is a discrete and sampled representation of a continuous route. Mobile devices collect tracks and opportunistically upload them to a centralized service. StarTrack includes facilities for storing, comparing, clustering,  and retrieving tracks. It serves as the foundation for building large-scale track-based services.

StarTrack Architecture

The StarTrack system is based on a client-server architecture. The figure below depicts a system with a cell phone, desktop PC, and the StarTrack service.  This figure also shows the software components that run on both mobile and fixed devices as well as on the servers in the data center.

 

 

 

 

 

 

 

 

StarTrack is implemented by a set of StarTrack server machines that connect to another set of SQL Server database server machines.  The StarTrack client implements the StarTrack API (shown on the table at right) and makes RPCs to the StarTrack servers as necessary. 

Dealing with large collections of tracks is surprisingly difficult and we had to devise techniques to overcome several challenges. In some cases, we were able to apply well-known techniques, such as vertical data partitioning and chained declustering. However, most of the observed improvements come from innovative data structures like track trees, new representations for canonicalized tracks, and novel uses of delayed execution and caching. Our experience to date is described in our OSDI paper (see the link below in the Publications section).

Sample Application: Ride-sharing

Ride-sharing has long held the promise of reducing energy consumption. Transit departments in many major metropolitan areas now offer on-line ride-sharing services or portals (for example, King County Metro Ride). One challenge in building an effective ridesharing service is to discover ride-share partners who travel on similar routes.

With StarTrack, these ride-matching services are easily built. The service can build a TrackCollection for the employees of the same company or for a person’s social network, or for a group of people who have subscribed to a transit service. The code segment below constructs a track collection for a community of users.

TrackCollxn getCommunityTracks(SearchCriteria sc, int count)
{
        TrackCollxn tc = MakeCollection(sc, true);
         return Take(SortTracks(tc, FREQ), count);
}

 

The code fragment below dentifies potential ride-sharing partners based on the similarity of their travel patterns. findOwners is a client-side functionthat takes a set of tracks and returns the list of users who own them.

 

List getRideShareCandidates(TrackCollxn communityTC, string username)

{

UserCriteria uc = new UserCriteria();

uc.Username = username;

 

TrackCollxn userTC = MakeCollection(uc, true);

Track[] popularTracks = GetTracks(SortTracks(userTC, FREQ),

0, 10);

List<TrackCollxn> similarTC;

foreach(Track track in popularTracks) {

TrackCollxn tc = GetSimilarTracks(communityTC, track,

0.7);

similarTC.Add(tc);

}

Track[] similarTracks = GetTracks(

JoinTrackCollections(similarTC), 0, 100);

return findOwners(similarTracks);

}

 

Publications

Ganesh Ananthanarayanan, Maya Haridasan, Iqbal Mohomed, Doug Terry, and Chandramohan A. Thekkath. StarTrack: A Framework for Enabling Track-Based Applications. In Proceedings of ACM/USENIX MobiSys, Krakow, Poland. June 2009. Pages 207-220

Maya Haridasan, Iqbal Mohomed, Doug Terry, Chandramohan A. Thekkath, and Li Zhang. StarTrack Next Generation: A Scalable Infrastructure for Track-Based Applications. To Appear  In Proceedings of the 9th Symposium on Operating Systems Design and Implementation (OSDI), Vancouver, Canada. Oct 2010.

Interns

  • Ganesh Ananthanarayanan, UC Berkeley, Summer 2008
  • Erich Stuntebeck, Georgia Tech, Summer 2009

Postdocs

  • Iqbal Mohomed (Now at IBM Research - TJ Watson)
People
Maya Haridasan
Maya Haridasan

Iqbal Mohomed
Iqbal Mohomed

Doug Terry
Doug Terry

Li Zhang
Li Zhang

Documents

StarTrack paper - (MobiSys 2009)
StarTrackNG paper - (OSDI 2010)

StarTrack API

The table below presents a simplified set of key operations in our API.

 Recording Tracks

 Track trk = StartTrack();

 EndTrack(trk); 

 SaveTrackEntryMetadata(trk, metadata); 

 RemoveTrack(trk); 

Grouping Tracks into collections

 TrackCollxn MakeCollection(GrpCriteria[] gCrit,

                                           bool unique); 

 Manipulating Tracks

 TrackCollxn JoinTrkCollections(TrkCollxn tCs[],

                                           bool unique);

 TrackCollxn SortTracks(TrkCollxn tC,

                                  SortAttribute, attr);

 TrackCollxn GetSimilarTracks(TrkCollxn tC,

                          Track refTrk, float simThresh);

 TrackCollxn GetPassByTracks(TrkCollxn tC,

                               Area[] areas);

 TrackCollxn GetCommonSegments(TrkCollxn tC,

                                          float freqThresh);

Retrieval Operations

 int GetTrackCount(TrkCollxn tC); 

 Track[] GetTracks(TrkCollxn tC, int start,

                                               int count);