Critical Point Algorithm

This technology is protected under U.S. Patent # 8,249,807 – Method for Determining Critical Points in Location Data Generated by Location-Based Applications.

Since GPS generates a large amount of location data, this data must be carefully managed to avoid wasting resources (e.g. battery energy) by transferring fixes to a server that may not contain useful information (e.g. repeated GPS fixes when the user is standing still, fixes lying upon the same vector when traveling in a straight line).  Traditional LBS transfer fixes to the server regularly based on a fixed time period, which can result in transferring some of these irrelevant fixes, as well as accidentally discarding fixes that actually contain useful information.

The path of the user can be accurately represented by using only small portions of GPS data generated by mobile phones.  The Critical Point Algorithm (CPA) uses the change in direction between sequential points as well as the user’s speed to filter non-critical points from a set of GPS data, therefore, only critical points representing the path of the user remain  (Figure 4).  Only these critical points are transferred to a server for storage and analysis.  By pre-filtering GPS data before it leaves the device, CPA saves battery energy, reduce data transfer costs, and saves network bandwidth, while still accurately representing the user’s path.  Table 1 shows the storage and financial savings per trip for transferring only critical points to the server.  Assuming that each user takes around 4 trips per day, the savings quickly compound for thousands of users across long periods of time.

Figure 4 All GPS Points, and Critical Points Only

All GPS Points, and Critical Points Only

Table 1 Savings from using the Critical Point Algorithm


For more information on the Critical Point algorithm, see: