Abstract
Map navigation is one of the most popular applications used by mobile users.
At the same time, it is also one of the time- and resource- consuming applications.
Various methods such as most-recently used and first-in, first-out algorithms are used to reduce the map transmission time and delay.
One of the popular methods is online mobile map prefetching and caching.
However, the mobility and location features of mobile users are usually left out by these methods.
Caching and prefetching maps based on a mobile user's locations would greatly reduce the transmission time and hence the battery power consumption.
For example, if a user is visiting a town, prefetching the maps of nearby interesting stores and caching the maps of the visited, neighboring landmarks would help the user's visitation experience and save the transmission time.
Online mobile map prefetching or caching is useful, but is not widely employed because it involves several different subjects and developers usually are not familiar with all of them.
Essential technologies for online mobile map prefetching and caching consist of four themes: (i) green handheld computing, (ii) location-based services and programming, (iii) map tile system, and (iv) location-aware map prefetching and caching methods.
Keywords
Global positioning system (GPS), green computing, handheld/mobile/smartphone computing, location-based services (LBS), map services
The Proposed Method
Map tile requests and display on mobile devices are slow and energy-consuming.
This research tries to reduce energy consumption of mobile devices and speed up the map display by pre-fetching or caching map tiles for mobile users.
It is divided into the following five steps:
- Path data collection
-
The first step is to collect path data.
Map tile requests are recorded on the servers.
This step can be done before the app is put to use or it continues collecting and updating the paths while the app is used.
- Path data preparation
-
Not all collected paths are useful for this research and the paths may need to be processed before being used.
Also, the GPS data is usually not stable or consistent.
This step may include noise removal, rarely-used path deletion, or path completion.
- Path pattern discovery
-
A map is usually a matrix of map tiles.
Therefore, a path can be represented by a matrix.
The matrix for a path is a sparse matrix and can be stored as a string for storage saving and better performance.
- Path pattern visualization and analysis
-
The discovered patterns and analysis data are displayed visually in this step.
- Path prediction and map tile prefetching and caching
-
This step consists of three sub-steps:
- Path matching:
Similar paths are found by matrix multiplications between the current path and the stored paths.
If the product is greater than a threshold value, the stored path is said to be similar to the current path.
Since the matrices are stored as strings, the multiplications can be done efficiently.
- Tree building:
A tree is then built by superimposing the found paths.
- Tree pruning:
Not all found paths are useful.
This sub-step removes the branches with less weight.
The result tree is then used to prefetch and cache map tiles.
References
- CloudMade. (n.d.). The CloudMade Developer Zone. Retrieved March 21, 2012, from http://developers.cloudmade.com/
- Liu, Q. (2009). Web Latency Reduction with Prefetching (Doctoral dissertation). University of Western Ontario, Ontario, Canada.
- Microsoft. (n.d.). Bing Maps Tile System. Retrieved December 17, 2011, from http://msdn.microsoft.com/en-us/library/bb259689.aspx
|