Project Lachesis: Parsing and Modeling Location HistoriesIntroductionResolutionGoalStays and DestinationsCalculating StaysSlide 7Slide 8Calculating DestinationsSlide 10ExampleSlide 12Slide 13Slide 14Creating Probabilistic ModelsSlide 16Slide 17Calculating πCalculating ACalculating BCalculating Probabilistic ModelsSlide 22Non-Markovian SolutionMarkovian SolutionExperiment ResultsSlide 26Slide 27Slide 28Slide 29Slide 30Experimental ResultsMarkov vs. Non-MarkovConclusionsProject Lachesis:Parsing and Modeling Location HistoriesDaniel KeeneyCS 4440Introduction•Location History is a record of an entity’s location in geographical space over time•Archaeologists and historians look at migrations and census data to reconstruct location histories•New technologies such as GPS allow us to enhance the accuracy and resolution greatlyResolution•Old temporal resolutions ranged from a decade to a century•Old spatial resolutions ranged from tens to hundreds of kilometers•GPS accuracy opens up a completely different type of analysisGoal•By tracking locations in real time, new types of analysis can be performed•Goal: condense, understand, and predict the movements of an object over a period of timeStays and Destinations•Stay is a single instance of an object spending some time in one place •Destination is any place where one or more objects have experienced a stay•Trip occurs between two adjacent stays made by the same object•Path is a representation of the description of a set of trips between destinationsCalculating Stays•The roaming distance, is how far an object can stray while being counted as a stay•The stay duration, is how long an object must remain within the roaming distance to count as a stay•Medoid is the data point nearest to the “center” of the setroamldurtCalculating StaysCalculating Stays•Worst case: O (n2) for n data points, due to medoid and diameter working on all pairs•In practice, clusters which require computation are far smaller than n, effectively yielding O(n)Calculating Destinations•Geographic scale, determines how close two stays can be and still be considered the same destination•Destinations are represented by a location as well as the scale used:destl),(destjjjld  lCalculating DestinationsExampleCreating Probabilistic ModelsAssumptions:•At the beginning of a given time interval, an object is at exactly one destination•During any given time interval, an object makes exactly one transition between destinations•Self-transitions are allowedCreating Probabilistic Models•Models are similar to Hidden Markov Models•Critical difference from HMM is the incorporation of time-dependence, where transition probabilities are conditioned on recurring time intervalsCreating Probabilistic Models•Model consists of three probability matrices•Probability of the object starting time interval at destination is•Probability of transition from to during interval is•Observation probability: observing object at when actually atkid)},({kidΠidjdk)},,({kjiddaA)},({jiddbB jdidCalculating π)},({kidΠCalculating A)},,({kjiddaACalculating B)},({jiddbB Calculating Probabilistic Models•Together as these tables represent a probabilistic model•This model can be used to solve problems such as finding the most likely destination occupied at a particular time, determining the relative likelihood of a location history sequence, or generating a location history sequence ),,( BAΠλ Calculating Probabilistic Models•Using λ we estimate the relative likelihood of a new location history•This is done using a Non-Markovian Solution and a Markovian SolutionNon-Markovian SolutionMarkovian SolutionExperiment ResultsExperiment ResultsExperiment ResultsExperiment ResultsS M T W T F S0123456789Day of WeekNumber of Hours“I always felt more productive on Tuesdays.” - Subject AExperiment ResultsExperiment ResultsS M T W T F S50100150200250Day of WeekDestination IDWeek 16 from Training DataS M T W T F S50100150200250Day of WeekDestination IDWeek 31 from Training DataA typical (left) and an atypical (right) week from Subject A.Experimental ResultsS M T W T F S50100150200250Day of WeekDestination IDA Stochastically Generated Week using Non-Markov ModelS M T W T F S50100150200250Day of WeekDestination IDA Stochastically Generated Week using Markov ModelPlots of synthesized weeks, using Non-Markov (left) and Markov (right) modelsMarkov vs. Non-Markov•Markovian model showed an atypical week to have an unexpectedly high probability•This could be mitigated by “training” on larger data sets, but generally the Non-Markovian model is sufficientConclusions•Proposed rigorous definitions for location histories, stays, and destinations, as well as accompanying algorithms•Non-Markovian is better suited for evaluating likelihoods of a location history•Markovian is better for stochastically generating a history •Future papers will examine trips and