{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:00:53Z","timestamp":1760241653575,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,6,21]],"date-time":"2018-06-21T00:00:00Z","timestamp":1529539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Open Geospatial Consortium","award":["Testbed 13"],"award-info":[{"award-number":["Testbed 13"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Performing similarity analysis on trajectories consisting of massive numbers of tracking points is computationally challenging. We introduce a progressive minimum bounding rectangle (MBR) and minimum distance (MINDIST) approach to process the K Best Connected Trajectory (K-BCT) query, which aims to find the top K similarity trajectories to a given query trajectory. Our approach has three unique features to speed up the query. First, the approach builds a series of progressive MBRs from the query trajectory to determine the order of reference trajectories to identify the target top K reference trajectories at an earlier stage. Second, this method introduces a grid-based search method to speed up the matched point detection between two trajectories for similarity measures. Third, this approach further leverages the many-core computing power of Graphical Processing Unit (GPU) devices to perform the query in a parallel manner. We have conducted tests with ship tracking data and human movement data using GPU instances from Amazon Web Services. Preliminary results indicate that (a) parallel computing has greatly improved the efficiency of the query, and (b) our optimized approach can further speedup the computation compared to parallel implementations.<\/jats:p>","DOI":"10.3390\/ijgi7070239","type":"journal-article","created":{"date-parts":[[2018,6,22]],"date-time":"2018-06-22T02:46:21Z","timestamp":1529635581000},"page":"239","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Parallel K Best Connected Trajectory (K-BCT) Query with GPGPU: A Combinatorial Min-Distance and Progressive Bounding Box Approach"],"prefix":"10.3390","volume":"7","author":[{"given":"Jing","family":"Li","sequence":"first","affiliation":[{"name":"Department of Geography and the Environment, University of Denver, Denver, CO 80208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuantong","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Geography and the Environment, University of Denver, Denver, CO 80208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tong","family":"Zhang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430070, Hubei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"You","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Denver, Denver, CO 80208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,21]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., and Huang, Y. (2010). T-drive: Driving directions based on taxi trajectories. Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM.","key":"ref_1","DOI":"10.1145\/1869790.1869807"},{"doi-asserted-by":"crossref","unstructured":"Zheng, Y. (2015). Trajectory data mining: An overview. ACM Trans. Intell. Syst. Technol., 6.","key":"ref_2","DOI":"10.1145\/2743025"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1016\/j.jss.2008.11.832","article-title":"Searching for similar trajectories in spatial networks","volume":"82","author":"Tiakas","year":"2009","journal-title":"J. Syst. Softw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1080\/13658816.2015.1081205","article-title":"Trajectory Box Plot: A new pattern to summarize movements","volume":"30","author":"Etienne","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"doi-asserted-by":"crossref","unstructured":"Magdy, N., Sakr, M.A., Mostafa, T., and El-Bahnasy, K. (2015, January 12\u201314). Review on trajectory similarity measures. Proceedings of the IEEE 7th International Conference on Intelligent Computing and Information Systems (ICICIS), Cairo, Egypt.","key":"ref_5","DOI":"10.1109\/IntelCIS.2015.7397286"},{"doi-asserted-by":"crossref","unstructured":"Deng, K., Xie, K., Zheng, K., and Zhou, X. (2011). Trajectory indexing and retrieval. Computing with Spatial Trajectories, Springer.","key":"ref_6","DOI":"10.1007\/978-1-4614-1629-6_2"},{"doi-asserted-by":"crossref","unstructured":"Frentzos, E., Gratsias, K., and Theodoridis, Y. (2007, January 15\u201320). Index-based most similar trajectory search. Proceedings of the IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey.","key":"ref_7","DOI":"10.1109\/ICDE.2007.367927"},{"doi-asserted-by":"crossref","unstructured":"Gowanlock, M., and Casanova, H. (2015, January 25\u201329). Indexing of spatiotemporal trajectories for efficient distance threshold similarity searches on the GPU. Proceedings of the IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India.","key":"ref_8","DOI":"10.1109\/IPDPS.2015.24"},{"key":"ref_9","first-page":"32","article-title":"Geolife: A collaborative social networking service among user, location and trajectory","volume":"33","author":"Zheng","year":"2010","journal-title":"IEEE Data Eng. Bull."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s10707-007-0027-y","article-title":"One way distance: For shape based similarity search of moving object trajectories","volume":"12","author":"Lin","year":"2008","journal-title":"GeoInformatica"},{"unstructured":"Besse, P., Guillouet, B., Loubes, J.-M., and Fran\u00e7ois, R. (2018, June 20). Review and Perspective for Distance Based Trajectory Clustering, arXiv, Available online: http:\/\/arxiv.org\/abs\/1508.04904.","key":"ref_11"},{"doi-asserted-by":"crossref","unstructured":"Arefin, A.S., Riveros, C., Berretta, R., and Moscato, P. (2012). Gpu-fs-knn: A software tool for fast and scalable knn computation using gpus. PLoS ONE, 7.","key":"ref_12","DOI":"10.1371\/journal.pone.0044000"},{"unstructured":"Wang, H., Su, H., Zheng, K., Sadiq, S., and Zhou, X. (2013). An effectiveness study on trajectory similarity measures. Proceedings of the Twenty-Fourth Australasian Database Conference-Volume 137, Australian Computer Society, Inc.","key":"ref_13"},{"doi-asserted-by":"crossref","unstructured":"Mariescu-Istodor, R., and Fr\u00e4nti, P. (2017). Grid-based method for GPS route analysis for retrieval. ACM Trans. Spat. Algorithms Syst., 3.","key":"ref_14","DOI":"10.1145\/3125634"},{"doi-asserted-by":"crossref","unstructured":"Zhang, J., You, S., and Gruenwald, L. (2012). U 2 STRA: High-performance data management of ubiquitous urban sensing trajectories on GPGPUs. Proceedings of the 2012 ACM Workshop on City data Management Workshop, ACM.","key":"ref_15","DOI":"10.1145\/2390226.2390229"},{"doi-asserted-by":"crossref","unstructured":"Jacox, E.H., and Samet, H. (2007). Spatial join techniques. ACM Trans. Database Syst., 32.","key":"ref_16","DOI":"10.1145\/1206049.1206056"},{"doi-asserted-by":"crossref","unstructured":"Rahat, T.A., Arman, A., and Ali, M.E. (2018). Maximizing reverse k-nearest neighbors for trajectories. Databases Theory and Applications, Springer. Lecture Notes in Computer Science.","key":"ref_17","DOI":"10.1007\/978-3-319-92013-9_21"},{"doi-asserted-by":"crossref","unstructured":"Lettich, F., Orlando, S., and Silvestri, C. (2015). Processing streams of spatial k-NN queries and position updates on manycore GPUs. Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM.","key":"ref_18","DOI":"10.1145\/2820783.2820803"},{"unstructured":"Leal, E., Gruenwald, L., Zhang, J., and You, S. (November, January 29). Tksimgpu: A parallel top-k trajectory similarity query processing algorithm for gpgpus. Proceedings of the IEEE International Conference on Big Data (Big Data), Santa Clara, CA, USA.","key":"ref_19"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1080\/136588197242428","article-title":"Spatial relations, minimum bounding rectangles, and spatial data structures","volume":"11","author":"Papadias","year":"1997","journal-title":"Int. J. Geogr. Inf. Sci."},{"doi-asserted-by":"crossref","unstructured":"Tripathi, P.K., Debnath, M., and Elmasri, R. (2016). A direction based framework for trajectory data analysis. Proceedings of the 9th ACM International Conference on PErvasive Technologies Related to Assistive Environments, ACM.","key":"ref_21","DOI":"10.1145\/2910674.2910728"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"949","DOI":"10.14778\/2536206.2536221","article-title":"Direction-preserving trajectory simplification","volume":"6","author":"Long","year":"2013","journal-title":"Proc. VLDB Endow."},{"doi-asserted-by":"crossref","unstructured":"Brox, T., and Malik, J. (2010). Object segmentation by long term analysis of point trajectories. European Conference on Computer Vision, Springer. Lecture Notes in Computer Science.","key":"ref_23","DOI":"10.1007\/978-3-642-15555-0_21"},{"doi-asserted-by":"crossref","unstructured":"Zou, Y.-G., and Fan, Q.-L. (2009, January 25\u201328). OQ-Quad: An efficient query processing for continuous k-nearest neighbor based on quad tree. Proceedings of the 4th International Conference on Computer Science & Education, Nanning, China.","key":"ref_24","DOI":"10.1109\/ICCSE.2009.5228493"},{"doi-asserted-by":"crossref","unstructured":"Chen, Z., Shen, H.T., Zhou, X., Zheng, Y., and Xie, X. (2010). Searching trajectories by locations: an efficiency study. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, ACM.","key":"ref_25","DOI":"10.1145\/1807167.1807197"},{"unstructured":"Waga, K., Tabarcea, A., Mariescu-Istodor, R., and Fr\u00e4nti, P. (2013, January 8\u201310). Real time access to multiple GPS tracks. Proceedings of the 9th International Conference on Web Information Systems and Technologies (WEBIST 2013), Aachen, Germany.","key":"ref_26"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or its caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Cartographica"},{"unstructured":"Kothuri, R.V., and Ravada, S. (2011). Pruning of Spatial Queries Using Index Root MBRS on Partitioned Indexes. (No. 7877405), U.S. Patent.","key":"ref_28"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ins.2017.01.016","article-title":"Parallel trajectory search based on distributed index","volume":"388","author":"Wang","year":"2017","journal-title":"Inf. Sci."},{"unstructured":"(2018, June 06). MarineCadastre.gov|Vessel Traffic Data, Available online: https:\/\/marinecadastre.gov\/ais\/.","key":"ref_30"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/7\/239\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:09:40Z","timestamp":1760195380000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/7\/239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,21]]},"references-count":30,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["ijgi7070239"],"URL":"https:\/\/doi.org\/10.3390\/ijgi7070239","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2018,6,21]]}}}