Open Access. Powered by Scholars. Published by Universities.®
Databases and Information Systems Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Databases and Information Systems
Best Upgrade Plans For Large Road Networks, Yimin Lin, Kyriakos Mouratidis
Best Upgrade Plans For Large Road Networks, Yimin Lin, Kyriakos Mouratidis
Kyriakos MOURATIDIS
In this paper, we consider a new problem in the context of road network databases, named Resource Constrained Best Upgrade Plan computation (BUP, for short). Consider a transportation network (weighted graph) G where a subset of the edges are upgradable, i.e., for each such edge there is a cost, which if spent, the weight of the edge can be reduced to a specific new value. Given a source and a destination in G, and a budget (resource constraint) B, the BUP problem is to identify which upgradable edges should be upgraded so that the shortest path distance between source and …
Efficient Verification Of Shortest Path Search Via Authenticated Hints, Man Lung Yiu, Yimin Lin, Kyriakos Mouratidis
Efficient Verification Of Shortest Path Search Via Authenticated Hints, Man Lung Yiu, Yimin Lin, Kyriakos Mouratidis
Kyriakos MOURATIDIS
Shortest path search in transportation networks is unarguably one of the most important online search services nowadays (e.g., Google Maps, MapQuest, etc), with applications spanning logistics, spatial optimization, or everyday driving decisions. Often times, the owner of the road network data (e.g., a transport authority) provides its database to third-party query services, which are responsible for answering shortest path queries posed by their clients. The issue arising here is that a query service might be returning sub-optimal paths either purposely (in order to serve its own purposes like computational savings or commercial reasons) or because it has been compromised by …
Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis
Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis
Kyriakos MOURATIDIS
Shortest path computation is one of the most common queries in location-based services that involve transportation net- works. Motivated by scalability challenges faced in the mo- bile network industry, we propose adopting the wireless broad- cast model for such location-dependent applications. In this model the data are continuously transmitted on the air, while clients listen to the broadcast and process their queries locally. Although spatial problems have been considered in this environment, there exists no study on shortest path queries in road networks. We develop the rst framework to compute shortest paths on the air, and demonstrate the practicality and …
Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu
Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu
Kyriakos MOURATIDIS
Research on spatial network databases has so far considered that there is a single cost value associated with each road segment of the network. In most real-world situations, however, there may exist multiple cost types involved in transportation decision making. For example, the different costs of a road segment could be its Euclidean length, the driving time, the walking time, possible toll fee, etc. The relative significance of these cost types may vary from user to user. In this paper we consider such multi-cost transportation networks (MCN), where each edge (road segment) is associated with multiple cost values. We formulate …