X hits on this document





12 / 12

driver through high crime areas of a city at night, or through unsafe roads in order to save a few minutes of travel time.

A road network partitioning algorithm was introduced. The algorithm uses the hierarchy of roads to segment the network into areas that are enclosed by large roads. This method yields very natural partitions, where large areas are observed at regions with low road densities, and much finer areas are observed at dense regions such as big cities. Ar- eas are a central concept to route planning, as they pro- vide the basis for hierarchical path finding, area level pre- computation, and area sensitive support of driving patterns.

We showed that significant query processing gains can be obtained, by following the principle that drivers tend to travel through the largest roads available for the trip, unless small roads along the way have a speed advantage over the large ones. We also presented a method to identify such fast roads, and efficiently incorporate them into route planning. In our experimental study we demonstrated that incorpo- rating fast small roads into the hierarchical path finding al- gorithm can significantly improve the quality of routes.

Through an empirical study, on real road networks, us- ing a realistic traffic information, we verify the large perfor- mance gains of our algorithms vs. competing methods, while showing that computed routes are close to optimal.



[1] R. Agrawal and R. Srikant. Mining sequential patterns. In Proc. Int. Conf. on Data Engineering (ICDE’95), 1995.

[2] A. Awasthi, Y. Lechevallier, M. Parent, and J.-M. Proth. Rule based prediction of fastest paths on urban networks. In Proc. Conf. on Intelligent Transportation Systems, 2005.

[3] T. Brinkhoff. Network-based generator of moving objects. Technical report, IAPG, http://www.fh-oow.de/institute/iapg/personen/ brinkhoff/generator/.

[4] Y.-L. Chou, H. E. Romeijn, and R. L. Smith. Approximating shortest paths in large-scale networks with an application to intelligent transportation sytems. INFORMS Journal on Computing, 10:163–179, 1998.

[5] D. Delling, P. Sanders, D. Schultes, and D. Wagner. Highway hierarchies star. In Proc. 9th DIMACS Implementation Challenge, 2006.

[6] C. Demetrescu, S. Emiliozzi, and G. F. Italiano. Experimental analysis of dynamic all pairs shortest path algorithms. In Proc. Symposium on Discrete Algorithms (SODA’04), 2004.

[7] E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.

[8] T. Elomaa and J. Rousu. General and efficient multisplitting of numerical attributes. Machine Learning, 36(3):201–244, 1999.

[9] R. W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962.

[10] D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasquale. Experimental analysis of dynamic algorithms for the single-source shortest-path problem. ACM Journal of Experimental Algorithms, 3:5, 1998.

[11] L. Fu, D. Sun, and L. R. Rilett. Heuristic shortest path algorithms for transportation applications: state


of the art. Computers in Operations Research, 33(11):3324–3343, 2006.

[12] J. Gehrke, R. Ramakrishnan, and V. Ganti. Rainforest: A framework for fast decision tree construction of large datasets. In Proc. Int. Conf. on Very Large Data Bases (VLDB’98), 1998.

[13] H. Gonzalez, J. Han, and X. Li. Flowcube: Constructuing RFID flowcubes for multi-dimensional analysis of commodity flows. In Proc. Int. Conf. on Very Large Data Bases (VLDB’06), 2006.

[14] H. Gonzalez, J. Han, X. Li, and D. Klabjan. Warehousing and analysis of massive RFID data sets. In Proc. Int. Conf. on Data Engineering (ICDE’06), 2006.

[15] J. Han and J. Pei. Mining frequent patterns by pattern-growth: Methodology and implications. SIGKDD Explorations (Special Issue on Scalable Data Mining Algorithms), 2:14–20, 2000.

[16] P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on system science and cybernetics, 4:100–107, 1968.

[17] J. A. Hartigan. Clustering Algorithms. John Wiley & Sons, 1975.

[18] N. Jing, Y.-W. Huang, and E. A. Rundensteiner. Hierarchical optimization of optimal path finding for transportaton applications. In Proc. Int. Conf. on Information and Knowledge Management (CIKM’96), 1996.

[19] S. Jung and S. Pramanik. HiTi graph model of topographical road maps in navigation systems. In Proc. Int. Conf. on Data Engineering (ICDE’96), 1996.

[20] E. Kanoulas, Y. Du, T. Xia, and D. ZXhang. Finding fastest paths on a road network with speed patterns. In Proc. Int. Conf. on Data Engineering (ICDE’06), 2006.

[21] V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. Symposium on Foundations of Computer Science, 1999.

[22] S. Pallottino and M. G. Scutell`a. Shortest path algorithms in transportation models: classical and innovative aspects. Technical Report TR-97-06, 14, 1997.

[23] J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. In Proc. Int. Conf. Data Engineering (ICDE’01), 2001.

[24] J. Quinlan. Improved use of continuous attributes in c4.5. Journal of Artificial Intelligence Research, 4:77–90, 1996.

[25] J. R. Quinlan. Induction of decision trees. Machine Learning, 1:81–106, 1986.

[26] P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proc. 17th European Symposium on Algorithms (ESA), 2005.

Document info
Document views24
Page views24
Page last viewedThu Oct 27 18:57:04 UTC 2016