Categories
Android Apps Kotlin

Location data reduction in Android

Android LocationManager allows fine location data updates with customisable interval. This means the phone could return new coordinates even after every 100ms. If the app would then upload all of these points, it would result in expensive data and battery usage. Can this location data be reduced before sending it to the server?

Problem

Android location data needs to be reduced so less of it is uploaded to server. Critical coordinates, like car turning, need to be retained.

Superfluous location data
Critical location data

Possible solutions

At first, the developer could consider 2 simple data reduction algorithms

  • Time based reduction: Upload data after certain intervals
  • Distance based reduction: Upload data after some distance is travelled

These are fine and will reduce the data. But they have the problem that critical points might be missed, and superfluous data is still uploaded. Does there exist a more comprehensive algorithm?

Ramer-Douglas-Peucker algorithm

The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. It recursively loops the points and keeps the ones that can be used to relatively accurately represent the original data. The algorithm can be configured with the allowable margin of error.

Visualisation of the RDP algorithm

RDP sounds like a great solution for location data reduction. However, it has one critical shortcoming: Its implementations can only be used for data batches, not for streaming data.

Geotab/curve

Geotab has released a curve logging library with streaming data functionality. It can be used to reduce different single value data, like speed or fuel level. In addition to single values, it can also reduce location data that has 2 coordinate values.

When the developer wants to use this algorithm in Android, there however is another problem. Geotab/curve is written in Python, which is generally not available in Android system. Therefore this library needs to be converted to Kotlin.

Kotlin port

Objects

The code consists of a buffer object and its manager DataReducer class. The default buffer size is 10, which is enough to create an accurate result.

class DataReducer(
    private var allowedError: Double = 2.0,
) {
    private val buffer = Buffer(bufferSize)

Callback

DataReducer has a retained callback

var retained: ((Point) -> Unit)? = null

The algorithm dispatches the retained points via this callback.

Adding points

New coordinates are added to the reducer via the addPoint method.

fun addPoint(point: Point)

If the buffer is filled and the algorithm finds a critical point, the retained function is called with this newly found coordinate.

Reducing the buffer

The buffer can be reduced manually by calling the reduce() function.

fun reduce()

The app should call this method when the app quits. After that all remaining retained points are returned via the retained block.

The reduce() function is called automatically when buffer is full. Therefore the developer should only call it when the location data stream is finished.

Usage

The developer needs to initialised the DataReducer object with DataType.GPS.

val dataReducer = DataReducer(dataType = DataType.GPS)

After that, she needs to set the lambda callback block. The reducer will stream the retained points over time to this single callback.


dataReducer.retained = {
	// retained coordinates from the reducer
	webService.uploadCoordinate(it)
}

Then, she can start adding points to the buffer

// Android Location Listener
val locationListener = LocationListener { location ->
	// convert Android location to LocationPoint
  val point = LocationPoint(location.latitude,
										location.longitude,
                    location.time.toDouble(),
  )
	// add the point to the Data Reducer
  dataReducer.addPoint(point)
}

And the reducer will return the retained points in the retained callback:

dataReducer.retained = {
	webService.uploadCoordinate(it)
}

Source code

Results

A driving simulation shows that the algorithm does not return points when car is driving in a straight line. In the corner, however, it returns multiple points. This is the desired result, because the car route can still be described with a lot fever coordinates.

The algorithm reduces a test route with 625 coordinates to just 14 points.

Other uses

Developers can use this data reduction algorithm for any other streaming data, like battery level or network usage. They can manage the retaining frequency by configuring the allowedError parameter. This value should be set to higher to retain more data.

Considerations

The algorithm continually returns new when it detects a critical point. If the app stops, the developer should call the reduce() method manually. Then the algorithm will return a list of retained points.

  • App needs to handle receiving multiple data points at once.
  • App needs to use timestamps from the data points, not callback time.

This algorithm works best for driving data. Every use case needs testing and configuring of the allowedError parameter.

Conclusion

All apps need to consider their battery and network usage. Android’s LocationManager can return location data very frequently. Consequently the developer needs to think about data reduction.

Time or distance based reductions will miss critical points from the driver’s route and keep superfluous ones. Therefore the developer can use the Ramer-Douglas-Peucker algorithm, which will accurately represent the original data with greatly reduced points.

Source code