Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/35148
Title: Effective caching of paths and regions for mobile services
Authors: Thomsen, Jeppe Rishede
Advisors: Yiu, Man Lung (COMP)
Keywords: Computer algorithms.
Mobile computing.
Issue Date: 2015
Publisher: The Hong Kong Polytechnic University
Abstract: Cheap GPS-enabled mobile devices have made online location based services (LBSs) increasingly common. Examples of LBS are: route planner, navigation assistance, restaurant recommendation, meeting point recommendation, and nearby friend notification. In location based services, caching can be used to reduce computational load or communication latency for queries. In this thesis, we consider three problems on caching paths and regions for mobile services. Our first problem is to investigate caching techniques for shortest paths. However, existing caching techniques do not exploit the optimal substructure property of shortest paths. We propose a novel caching problem for shortest paths, and develop algorithms and data structures for this problem. Our second problem is to explore trade-offs between the lengths and the query coverage of concise shortest paths, in online driving direction services. Driving instructions are equivalent to so-called concise shortest paths, which occupy much less space than the corresponding shortest paths. The caching of concise shortest paths has two opposite effects on the cache hit ratio. The cache can accommodate a larger number of concise paths, but each individual concise path contains fewer nodes and so may answer fewer shortest path queries. We formulate the concept of a generic shortest path enabling trade-off between a paths size and the number of queries it can answer. We present algorithms for computing and caching generic concise shortest paths. Our third problem is to compute safe regions for the sum-optimal meeting point notification problem. It has applications like social networking services or online games, in which multiple moving users in a group may wish to be continuously notified about the best meeting point from their locations. To reduce the communication frequency, an application server can compute safe regions, which capture the validity of query results with respect to users locations. Unfortunately, the safe regions in our problem exhibit characteristics such as irregular shapes and inter-dependencies, which render existing methods for single safe region inapplicable. We present algorithms for computing safe regions for sum-optimal meeting point. In summary, we make the following contributions: (i) algorithms and data structures for caching of shortest paths; (ii) algorithms for computing generic concise shortest paths; (iii) algorithms for computing the safe regions for the sum-optimal point notification problem.
Description: PolyU Library Call No.: [THS] LG51 .H577P COMP 2015 Thomsen
xvi , 137 pages :illustrations
URI: http://hdl.handle.net/10397/35148
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b28157357_link.htmFor PolyU Users203 BHTMLView/Open
b28157357_ir.pdfFor All Users (Non-printable)1.65 MBAdobe PDFView/Open
Show full item record

Page view(s)

42
Last Week
2
Last month
Checked on Mar 26, 2017

Download(s)

20
Checked on Mar 26, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.