{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T18:06:37Z","timestamp":1778609197882,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T00:00:00Z","timestamp":1674777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61972198"],"award-info":[{"award-number":["61972198"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Jiangsu Province of China","award":["BK20191273"],"award-info":[{"award-number":["BK20191273"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>A multi-attribute trajectory consists of a spatio-temporal trajectory and a set of descriptive attributes. Such data enrich the representation of traditional spatio-temporal trajectories to have comprehensive knowledge of moving objects. Range query is a fundamental operator over multi-attribute trajectories. Such a query contains two predicates, spatio-temporal and attribute, and returns the objects whose locations are within a distance threshold to the query trajectory and attributes contain expected values. There are different execution plans for answering the query. To enhance the capability of a trajectory database, an optimizer is essentially required to (i) accurately estimate the cost for alternative query strategies in terms of disk accesses, (ii) build a decision-making module that automatically sorts the data in an appropriate way and selects the optimal query plan, and (iii) update the analytical models when new trajectories are arrived. The cost model supports both uniform and non-uniform spatio-temporal data distribution and incorporates attribute distribution. The optimizer is fully developed inside a database system kernel and comprehensively evaluated in terms of accuracy and effectiveness by using large real and synthetic datasets.<\/jats:p>","DOI":"10.1145\/3555811","type":"journal-article","created":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T11:41:14Z","timestamp":1662810074000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Query Optimizer for Range Queries over Multi-Attribute Trajectories"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0929-5234","authenticated-orcid":false,"given":"Jianqiu","family":"Xu","sequence":"first","affiliation":[{"name":"Nanjing University of Aeronautics and Astronautics, Jiangjun Road, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1199-6678","authenticated-orcid":false,"given":"Hua","family":"Lu","sequence":"additional","affiliation":[{"name":"Roskilde University, Roskilde, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,27]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"[n. d.]. http:\/\/factory.datatang.com\/en\/."},{"key":"e_1_3_1_3_2","first-page":"390","volume-title":"IEEE ICDE","author":"Akdere M.","year":"2012","unstructured":"M. Akdere, U. \u00c7etintemel, M. Riondato, E. Upfal, and S. B. Zdonik. 2012. Learning-based query performance modeling and prediction. In IEEE ICDE. IEEE Computer Society, 390\u2013401."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357776"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151111"},{"key":"e_1_3_1_7_2","first-page":"2207","volume-title":"SIGMOD","author":"Cong G.","year":"2016","unstructured":"G. Cong and C. S. Jensen. 2016. Querying geo-textual data: Spatial keyword queries and beyond. In SIGMOD. 2207\u20132212."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2005.03.004"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2782759.2782768"},{"key":"e_1_3_1_10_2","first-page":"337","volume-title":"ACM SIGMOD","author":"al. M. A. Soliman et","year":"2014","unstructured":"M. A. Soliman et al.2014. Orca: A modular query optimizer architecture for big data. In ACM SIGMOD. ACM, 337\u2013348."},{"issue":"10","key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1109\/TKDE.2004.48","article-title":"An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces","volume":"16","author":"al. Y. Tao et","year":"2004","unstructured":"Y. Tao et al.2004. An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces. IEEE Trans. Knowl. Data Eng. 16, 10 (2004), 1169\u20131184.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_1_12_2","first-page":"1528","volume-title":"ICDE","author":"Fang Y.","year":"2016","unstructured":"Y. Fang, R. Cheng, W. Tang, S. Maniu, and X. S. Yang. 2016. Scalable algorithms for nearest-neighbor joins on big trajectory data. In ICDE. 1528\u20131529."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-006-0007-7"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0090-4"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352963"},{"issue":"2","key":"e_1_3_1_16_2","first-page":"56","article-title":"SECONDO: A platform for moving objects database research and for publishing and integrating research implementations","volume":"33","author":"G\u00fcting R. H.","year":"2010","unstructured":"R. H. G\u00fcting, T. Behr, and C. D\u00fcntgen. 2010. SECONDO: A platform for moving objects database research and for publishing and integrating research implementations. IEEE Data Eng. Bull. 33, 2 (2010), 56\u201363.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0185-7"},{"issue":"2","key":"e_1_3_1_18_2","first-page":"Article 7","article-title":"Symbolic trajectories","volume":"1","author":"G\u00fcting R. H.","year":"2015","unstructured":"R. H. G\u00fcting, F. Vald\u00e9s, and M. L. Damiani. 2015. Symbolic trajectories. ACM Trans. Spat. Algor. Syst. 1, 2 (2015), Article 7.","journal-title":"ACM Trans. Spat. Algor. Syst."},{"key":"e_1_3_1_19_2","first-page":"223","volume-title":"DASFAA","author":"Han Y.","year":"2015","unstructured":"Y. Han, L. Wang, Y. Zhang, W. Zhang, and X. Lin. 2015. Spatial keyword range search on trajectories. In DASFAA. 223\u2013240."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.141"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453971"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00149-7"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850588"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368299"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-021-00157-1"},{"issue":"2","key":"e_1_3_1_27_2","first-page":"13:1\u201313:46","article-title":"Efficient algorithms and cost models for reverse spatial-keyword k-nearest neighbor search","volume":"39","author":"Lu Y.","year":"2014","unstructured":"Y. Lu, J. Lu, G. Cong, W. Wu, and C. Shahabi. 2014. Efficient algorithms and cost models for reverse spatial-keyword k-nearest neighbor search. ACM Trans. Database Syst. 39, 2 (2014), 13:1\u201313:46.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_3_1_28_2","first-page":"2557","volume-title":"ACM SIGMOD","author":"Negi P.","year":"2021","unstructured":"P. Negi, M. Interlandi, R. Marcus, M. Alizadeh, T. Kraska, M. Friedman, and A. Jindal. 2021. Steering query optimizers: A practical take on big data workloads. In ACM SIGMOD. ACM, 2557\u20132569."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501656"},{"key":"e_1_3_1_30_2","first-page":"725","volume-title":"SIGMOD","author":"Shang Z.","year":"2018","unstructured":"Z. Shang, G. Li, and Z. Bao. 2018. DITA: Distributed in-memory trajectory analytics. In SIGMOD. 725\u2013740."},{"key":"e_1_3_1_31_2","first-page":"4:1\u20134:12","volume-title":"SSDBM","author":"Sprenger S.","year":"2018","unstructured":"S. Sprenger, P. Sch\u00e4fer, and U. Leser. 2018. Multidimensional range queries on modern hardware. In SSDBM. 4:1\u20134:12."},{"key":"e_1_3_1_32_2","first-page":"1566","volume-title":"ICDE","author":"Sprenger S.","year":"2019","unstructured":"S. Sprenger, P. Sch\u00e4fer, and U. Leser. 2019. BB-tree: A main-memory index structure for multidimensional range queries. In ICDE. 1566\u20131569."},{"key":"e_1_3_1_33_2","first-page":"963","volume-title":"ICDE","author":"Su H.","year":"2015","unstructured":"H. Su, K. Zheng, K. Zeng, J. Huang, S. W. Sadiq, N. J. Yuan, and X. Zhou. 2015. Making sense of trajectory data: A partition-and-summarization approach. In ICDE. 963\u2013974."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/1435713.1437594"},{"key":"e_1_3_1_35_2","first-page":"191","volume-title":"ICDE","author":"Tao Y.","year":"2002","unstructured":"Y. Tao, D. Papadias, and J. Zhang. 2002. Cost models for overlapping and multi-version B-trees. In ICDE. 191\u2013200."},{"key":"e_1_3_1_36_2","first-page":"161","volume-title":"ACM SIGACT-SIGMOD-SIGART","author":"Theodoridis Y.","year":"1996","unstructured":"Y. Theodoridis and T. K. Sellis. 1996. A model for the prediction of R-tree performance. In ACM SIGACT-SIGMOD-SIGART. 161\u2013171."},{"key":"e_1_3_1_37_2","first-page":"476","volume-title":"ICDE","author":"Theodoridis Y.","year":"1998","unstructured":"Y. Theodoridis, E. Stefanakis, and T. K. Sellis. 1998. Cost models for join queries in spatial databases. In ICDE. 476\u2013483."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.842247"},{"key":"e_1_3_1_39_2","first-page":"1653","volume-title":"ACM SIGKDD","author":"Tong Y.","year":"2017","unstructured":"Y. Tong, Y. Chen, Z. Zhou, L. Chen, J. Wang, Q. Yang, J. Ye, and W. Lv. 2017. The simpler the better: A unified approach to predicting original taxi demands based on large-scale online platforms. In ACM SIGKDD. 1653\u20131662."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_3_1_41_2","first-page":"905","volume-title":"DEXA","author":"Trajcevski G.","year":"2003","unstructured":"G. Trajcevski and P. Scheuermann. 2003. Triggers and continuous queries in moving objects database. In DEXA. 905\u2013910."},{"key":"e_1_3_1_42_2","first-page":"88:1\u201388:4","volume-title":"ACM SIGSPATIAL","author":"Vald\u00e9s F.","year":"2017","unstructured":"F. Vald\u00e9s and R. H. G\u00fcting. 2017. Efficient multi-attribute analysis for trajectories: A case study for aircraft. In ACM SIGSPATIAL. 88:1\u201388:4."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-016-0286-6"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0525-6"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2776268"},{"key":"e_1_3_1_46_2","first-page":"597","volume-title":"ICDE","author":"Wang S.","year":"2017","unstructured":"S. Wang, Z. Bao, J. S. Culpepper, T. Sellis, M. Sanderson, and X. Qin. 2017. Answering top-k exemplar trajectory queries. In ICDE. 597\u2013608."},{"key":"e_1_3_1_47_2","first-page":"535","volume-title":"SIGIR","author":"Wang S.","year":"2018","unstructured":"S. Wang, Z. Bao, J. Shane Culpepper, Z. Xie, Q. Liu, and X. Qin. 2018. Torch: A search engine for trajectory data. In SIGIR. 535\u2013544."},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.172"},{"key":"e_1_3_1_49_2","unstructured":"W. Wu Y. Chi S. Zhu J. Tatemura H. Hacig\u00fcm\u00fcs and J. F. Naughton. 2013. Predicting Query Execution Time: Are Optimizer Cost Models Really Unusable? IEEE Computer Society 1081\u20131092."},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137655"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-012-0158-7"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-018-0326-5"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2787711"},{"key":"e_1_3_1_54_2","first-page":"259","volume-title":"EDBT","author":"Yan Z.","year":"2011","unstructured":"Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. 2011. SeMiTri: A framework for semantic annotation of heterogeneous trajectories. In EDBT. 259\u2013270."},{"issue":"3","key":"e_1_3_1_55_2","first-page":"49:1\u201349:38","article-title":"Semantic trajectories: Mobility data computation and annotation","volume":"4","author":"Yan Z.","year":"2013","unstructured":"Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. 2013. Semantic trajectories: Mobility data computation and annotation. ACM TIST 4, 3 (2013), 49:1\u201349:38.","journal-title":"ACM TIST"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732949"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-017-0498-1"},{"key":"e_1_3_1_58_2","first-page":"975","volume-title":"ICDE","author":"Zheng B.","year":"2015","unstructured":"B. Zheng, N. J. Yuan, K. Zheng, X. Xie, S. W. Sadiq, and X. Zhou. 2015. Approximate keyword search in semantic trajectory database. In ICDE. 975\u2013986."},{"key":"e_1_3_1_59_2","first-page":"230","volume-title":"ICDE","author":"Zheng K.","year":"2013","unstructured":"K. Zheng, S. Shang, N. J. Yuan, and Y. Yang. 2013. Towards efficient search for activity trajectories. In ICDE. 230\u2013241."},{"issue":"2","key":"e_1_3_1_60_2","first-page":"27","article-title":"Go beyond raw trajectory data: Quality and semantics","volume":"38","author":"Zheng K.","year":"2015","unstructured":"K. Zheng and H. Su. 2015. Go beyond raw trajectory data: Quality and semantics. IEEE Data Eng. Bull. 38, 2 (2015), 27\u201334.","journal-title":"IEEE Data Eng. Bull."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555811","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:36Z","timestamp":1750182696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,27]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3555811"],"URL":"https:\/\/doi.org\/10.1145\/3555811","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,27]]},"assertion":[{"value":"2021-12-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}