Multi-cost and upgradable spatial network databases

In this dissertation, we first consider data processing problems in multi-cost networks and in upgradable networks. These network types are motivated by real-life situations, which do not fall under the standard spatial network formulation and have not received much attention from database researche...

Full description

Saved in:
Bibliographic Details
Main Author: LIN, Yimin
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2014
Subjects:
Online Access:https://ink.library.smu.edu.sg/etd_coll/520
https://ink.library.smu.edu.sg/context/etd_coll/article/1523/viewcontent/Multi_Cost_and_Upgradable_Spatial_Network_Databases.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.etd_coll-1523
record_format dspace
spelling sg-smu-ink.etd_coll-15232023-11-02T04:22:27Z Multi-cost and upgradable spatial network databases LIN, Yimin In this dissertation, we first consider data processing problems in multi-cost networks and in upgradable networks. These network types are motivated by real-life situations, which do not fall under the standard spatial network formulation and have not received much attention from database researchers. In a multi-cost network (MCN), each edge is associated with more than one weight type that may affect the user-specific perception of distance. We study two query types on MCNs, namely, the MCN skyline and the MCN top-k query. In an upgradable network, a subset of the edges are amenable to weight reduction, at a cost (e.g., monetary cost). In this context, we consider the resource constrained best upgrade plan (BUP) problem. The goal is to choose some edges for upgrade so that the sum of network distances in a specific set of source-destination pairs is minimized, without the total upgrade cost exceeding a certain budget. In the latter part of the dissertation we propose methods for the verification of shortest path search on (plain) spatial networks that are outsourced to a third-party server. Since third parties are not necessarily trusted, the users need a means to verify that the paths reported by the server are the actual shortest paths. 2014-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/etd_coll/520 https://ink.library.smu.edu.sg/context/etd_coll/article/1523/viewcontent/Multi_Cost_and_Upgradable_Spatial_Network_Databases.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Dissertations and Theses Collection (Open Access) eng Institutional Knowledge at Singapore Management University multi-cost networks spatial networks preference query processing shortest path verification spatial data management Databases and Information Systems OS and Networks
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic multi-cost networks
spatial networks
preference query processing
shortest path verification
spatial data management
Databases and Information Systems
OS and Networks
spellingShingle multi-cost networks
spatial networks
preference query processing
shortest path verification
spatial data management
Databases and Information Systems
OS and Networks
LIN, Yimin
Multi-cost and upgradable spatial network databases
description In this dissertation, we first consider data processing problems in multi-cost networks and in upgradable networks. These network types are motivated by real-life situations, which do not fall under the standard spatial network formulation and have not received much attention from database researchers. In a multi-cost network (MCN), each edge is associated with more than one weight type that may affect the user-specific perception of distance. We study two query types on MCNs, namely, the MCN skyline and the MCN top-k query. In an upgradable network, a subset of the edges are amenable to weight reduction, at a cost (e.g., monetary cost). In this context, we consider the resource constrained best upgrade plan (BUP) problem. The goal is to choose some edges for upgrade so that the sum of network distances in a specific set of source-destination pairs is minimized, without the total upgrade cost exceeding a certain budget. In the latter part of the dissertation we propose methods for the verification of shortest path search on (plain) spatial networks that are outsourced to a third-party server. Since third parties are not necessarily trusted, the users need a means to verify that the paths reported by the server are the actual shortest paths.
format text
author LIN, Yimin
author_facet LIN, Yimin
author_sort LIN, Yimin
title Multi-cost and upgradable spatial network databases
title_short Multi-cost and upgradable spatial network databases
title_full Multi-cost and upgradable spatial network databases
title_fullStr Multi-cost and upgradable spatial network databases
title_full_unstemmed Multi-cost and upgradable spatial network databases
title_sort multi-cost and upgradable spatial network databases
publisher Institutional Knowledge at Singapore Management University
publishDate 2014
url https://ink.library.smu.edu.sg/etd_coll/520
https://ink.library.smu.edu.sg/context/etd_coll/article/1523/viewcontent/Multi_Cost_and_Upgradable_Spatial_Network_Databases.pdf
_version_ 1781793995011129344