{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T15:00:19Z","timestamp":1773586819444,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540281276","type":"print"},{"value":"9783540319047","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11535331_16","type":"book-chapter","created":{"date-parts":[[2010,7,21]],"date-time":"2010-07-21T20:51:20Z","timestamp":1279745480000},"page":"273-290","source":"Crossref","is-referenced-by-count":232,"title":["On Trip Planning Queries in Spatial Databases"],"prefix":"10.1007","author":[{"given":"Feifei","family":"Li","sequence":"first","affiliation":[]},{"given":"Dihan","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean tsp and other geometric problems. In: FOCS, p. 2 (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: A survey. Mathematical Programming (2003)","DOI":"10.1007\/s10107-003-0438-y"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-tsp and vehicle routing with time-windows. In: STOC, pp. 166\u2013174 (2004)","DOI":"10.1145\/1007352.1007385"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H., Schneider, R., Seeger, B.: The R*-tree: An efficient and robust access method for points and rectangles. In: SIGMOD, pp. 220\u2013231 (1990)","DOI":"10.1145\/93597.98741"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Benetis, R., Jensen, C.S., Karciauskas, G., Saltenis, S.: Nearest neighbor and reverse nearest neighbor queries for moving objects. In: IDEAS, pp. 44\u201353 (2002)","DOI":"10.1109\/IDEAS.2002.1029655"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Berchtold, S., B\u00f6hm, C., Keim, D.A., Kriegel, H.-P.: A cost model for nearest neighbor search in high-dimensional data space. In: PODS, pp. 78\u201386 (1997)","DOI":"10.1145\/263661.263671"},{"issue":"2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/357775.357776","volume":"25","author":"C. B\u00f6hm","year":"2000","unstructured":"B\u00f6hm, C.: A cost model for query processing in high dimensional data spaces. TODS\u00a025(2), 129\u2013178 (2000)","journal-title":"TODS"},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1023\/A:1015231126594","volume":"6","author":"T. Brinkhoff","year":"2002","unstructured":"Brinkhoff, T.: A framework for generating network-based moving objects. GeoInformatica\u00a06(2), 153\u2013180 (2002)","journal-title":"GeoInformatica"},{"key":"16_CR9","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Computer Science Department,Carnegie Mellon University (1976)"},{"key":"16_CR10","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1997","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (1997)"},{"key":"16_CR11","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for tsp with neighborhoods in the plane. In: SODA, pp. 38\u201346 (2001)"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Egenhofer, M.J.: What\u2019s special about spatial?: database requirements for vehicle navigation in geographic space. In: SIGMOD, pp. 398\u2013402 (1993)","DOI":"10.1145\/170036.170096"},{"key":"16_CR13","unstructured":"Even, G., Kortsarz, G.: An approximation algorithm for the group steiner problem. In: SODA, pp. 49\u201358 (2002)"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences\u00a069(3), 485\u2013497 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/3-540-47724-1_14","volume-title":"Advances in Spatial and Temporal Databases","author":"H. Ferhatosmanoglu","year":"2001","unstructured":"Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., Abbadi, A.E.: Constrained nearest neighbor queries. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol.\u00a02121, pp. 257\u2013278. Springer, Heidelberg (2001)"},{"issue":"1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"16_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/352958.352963","volume":"25","author":"R. Hartmut Guting","year":"2000","unstructured":"Hartmut Guting, R., Bohlen, M.H., Erwig, M., Jensen, C.S., Lorentzos, N.A., Schneider, M., Vazirgiannis, M.: A foundation for representing and querying moving objects. TODS\u00a025(1), 1\u201342 (2000)","journal-title":"TODS"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: SIGMOD, pp. 47\u201357 (1984)","DOI":"10.1145\/602259.602266"},{"issue":"2","key":"16_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/320248.320255","volume":"24","author":"G. Hjaltason","year":"1999","unstructured":"Hjaltason, G., Samet, H.: Distance Browsing in Spatial Databases. TODS\u00a024(2), 265\u2013318 (1999)","journal-title":"TODS"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Ihler, E.: Bounds on the Quality of Approximate Solutions to the Group Steiner Problem. Technical report, Institut fur Informatik,Uiversity Freiburg (1990)","DOI":"10.1007\/3-540-53832-1_36"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Kolahdouzan, M.R., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: VLDB, pp. 840\u2013851 (2004)","DOI":"10.1016\/B978-012088469-8.50074-7"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: SIGMOD, pp. 201\u2013212 (2000)","DOI":"10.1145\/342009.335415"},{"key":"16_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/net.3230260407","volume":"26","author":"Y.S. Myung","year":"1995","unstructured":"Myung, Y.S., Lee, C.H., Tcha, D.W.: On the Generalized Minimum Spanning Tree Problem. Networks\u00a026, 231\u2013241 (1995)","journal-title":"Networks"},{"key":"16_CR25","unstructured":"Digital\u00a0Chart of\u00a0the World\u00a0Server, http:\/\/www.maproom.psu.edu\/dcw\/"},{"key":"16_CR26","unstructured":"Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group nearest neighbor queries. In: ICDE, pp. 301\u2013312 (2004)"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: VLDB, pp. 802\u2013813 (2003)","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"16_CR28","series-title":"Lecture Notes in Computer Science","first-page":"394","volume-title":"Database Theory - ICDT \u201997","author":"A. Papadopoulos","year":"1996","unstructured":"Papadopoulos, A., Manolopoulos, Y.: Performance of nearest neighbor queries in r-trees. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol.\u00a01186, pp. 394\u2013408. Springer, Heidelberg (1996)"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: SIGMOD, pp. 71\u201379 (1995)","DOI":"10.1145\/223784.223794"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Shahabi, C., Kolahdouzan, M.R., Sharifzadeh, M.: A road network embedding technique for k-nearest neighbor search in moving object databases. In: GIS, pp. 94\u2013100 (2002)","DOI":"10.1145\/585147.585167"},{"key":"16_CR31","unstructured":"Sharifzadeh, M., Kolahdouzan, M., Shahabi, C.: The Optimal Sequenced Route Query. Technical report, Computer Science Department, University of Southern California (2005)"},{"issue":"1","key":"16_CR32","first-page":"102","volume":"9","author":"S. Shekhar","year":"1997","unstructured":"Shekhar, S., Liu, D.-R.: Ccam: A connectivity-clustered access method for networks and network computations. TKDE\u00a09(1), 102\u2013119 (1997)","journal-title":"TKDE"},{"key":"16_CR33","unstructured":"TSP Home\u00a0Web Site, http:\/\/www.tsp.gatech.edu\/"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: STOC, pp. 296\u2013305 (2001)","DOI":"10.1145\/380752.380813"},{"key":"16_CR35","unstructured":"U.S. Geological Survey, http:\/\/www.usgs.gov\/"},{"key":"16_CR36","doi-asserted-by":"crossref","unstructured":"Tao, Y., Papadias, D.: Time-parameterized queries in spatio-temporal databases. In: SIGMOD, pp. 334\u2013345 (2002)","DOI":"10.1145\/564691.564730"},{"key":"16_CR37","doi-asserted-by":"crossref","unstructured":"Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: VLDB, pp. 287\u2013298 (2002)","DOI":"10.1016\/B978-155860869-6\/50033-0"},{"issue":"10","key":"16_CR38","first-page":"1169","volume":"16","author":"Y. Tao","year":"2004","unstructured":"Tao, Y., Zhang, J., Papadias, D., Mamoulis, N.: An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces. TKDE\u00a016(10), 1169\u20131184 (2004)","journal-title":"TKDE"},{"issue":"1","key":"16_CR39","first-page":"19","volume":"12","author":"Y. Theodoridis","year":"2000","unstructured":"Theodoridis, Y., Stefanakis, E., Sellis, T.: Efficient cost models for spatial queries using r-trees. TKDE\u00a012(1), 19\u201332 (2000)","journal-title":"TKDE"},{"key":"16_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/3-540-47724-1_2","volume-title":"Advances in Spatial and Temporal Databases","author":"M. Vazirgiannis","year":"2001","unstructured":"Vazirgiannis, M., Wolfson, O.: A spatiotemporal model and language for moving objects on road networks. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol.\u00a02121, pp. 20\u201335. Springer, Heidelberg (2001)"},{"key":"16_CR41","doi-asserted-by":"crossref","unstructured":"Xiong, X., Mokbel, M.F., Aref, W.G.: Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In: ICDE, pp. 643\u2013654 (2005)","DOI":"10.1145\/1007568.1007638"},{"key":"16_CR42","unstructured":"Xiong, X., Mokbel, M.F., Aref, W.G., Hambrusch, S.E., Prabhakar, S.: Scalable spatio-temporal continuous query processing for location-aware services. In: SSDBM, pp. 317\u2013327 (2004)"},{"key":"16_CR43","doi-asserted-by":"crossref","unstructured":"Yiu, M.L., Mamoulis, N.: Clustering objects on a spatial network. In: SIGMOD, pp. 443\u2013454 (2004)","DOI":"10.1145\/1007568.1007619"}],"container-title":["Lecture Notes in Computer Science","Advances in Spatial and Temporal Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11535331_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T07:01:11Z","timestamp":1685689271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11535331_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281276","9783540319047"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/11535331_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}