Parsing location histories

US7868786B2 · kind B2 · utility

Assignee

• Microsoft Corporation · US

Inventors

• Kentaro Toyama · Redmond, US
• Ramaswamy Hariharan · Irvine, US
• Ross Cutler · Duvall, US
• John R. Douceur · Bellevue, US
• Nuria M. Oliver · Seattle, US
• Eric Ringger · Seattle, US
• Daniel C. Robbins · Seattle, US
• Matthew Uyttendaele · Seattle, US

Key dates

• Filing date: Oct 19, 2004
• Grant date: Jan 11, 2011
• Expiry date: Nov 11, 2029

Classification

• Technology area (CPC G): Physics
• CPC primary: G06Q30/02
• WIPO field: IT methods for management
• WIPO sector: Electrical engineering

Abstract

A location history is a collection of locations over time for an object. A stay is a single instance of an object spending some time in one place, and a destination is any place where one or more objects have experienced a stay. Location histories are parsed using stays and destinations. In a described implementation, each location of a location history is recorded as a spatial position and a corresponding time at which the spatial position is acquired. Stays are extracted from a location history by analyzing locations thereof with regard to a temporal threshold and a spatial threshold. Specifically, two or more locations are considered a stay if they exceed a minimum stay duration and are within a maximum roaming distance. Each stay includes a location, a starting time, and an ending time. Destinations are produced from the extracted stays using a clustering operation and a predetermined scaling factor.