The Optimal Sequenced Route Query Based On Distributed Systems

An optimal sequenced route?OSR?query concerns a starting point p,a sequence M and n point sets U ₁,U ₂,...,U _m.The objective of this query is to identify a sequenced route R_p,such that follows sequence M and its length is minimum over all the sequenced routes that follow M.OSR queries find important applications in spatial applications such as navigation devices and online map services.With the rapid development of location based application,existing optimal sequenced route query algorithm cannot fulfill the requirement of real-time capability and scalability of applications.In an application of enterprise level,there may be a lot of users conduct optimal sequenced queries on a same data set at the same time;the data set for querying can be too large for a single machine;the load of computing can be too heavy for a single machine.Therefore,the storage and computing of queries need to be deploy on distributed cluster in some practical applications.This paper will discuss optimal sequenced route query algorithms on distributed systems.To solve these problems,optimal sequenced route query algorithms on distributed systems are researched and implemented in this paper.In this paper,the optimal sequenced route query problem is divided into two sub-problems:the optimal sequenced route query on Euclidean space and the optimal sequenced route query on metric space.We build distributed R-Tree and M-Tree index structures,and combined them with searching and pruning in inverted order to improve the efficiency of algorithms.In the final part of this paper,we prove the efficiency of proposed algorithms with experiments based on real dataset.