{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:27:31Z","timestamp":1760239651623,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:00:00Z","timestamp":1607904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>To manage multidimensional point data more efficiently, this paper presents an improvement, called HD-tree, of a previous indexing method, called D-tree. Both structures combine quadtree-like partitioning (using integer shift operations without storing internal nodes, but only leaves) and hash tables (for searching for the nodes stored). However, the HD-tree follows a brand-new decomposition strategy, which is called half decomposition strategy. This improvement avoids the generation of nodes containing only a small amount of data and the sequential search of the hash table, so that it can save storage space while having faster I\/O and better time performance when building the tree and querying data. The results demonstrate convincingly that the time and space performance of HD-tree is better than that of D-tree regardless of uniform or uneven data, which are less affected by data distribution.<\/jats:p>","DOI":"10.3390\/a13120338","type":"journal-article","created":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T21:25:08Z","timestamp":1607981108000},"page":"338","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["HD-Tree: An Efficient High-Dimensional Virtual Index Structure Using a Half Decomposition Strategy"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3157-2402","authenticated-orcid":false,"given":"Ting","family":"Huang","sequence":"first","affiliation":[{"name":"School of Computer Science, China University of Geosciences (Wuhan), 388 Lumo Road, Wuhan 430074, China"}]},{"given":"Zhengping","family":"Weng","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences (Wuhan), 388 Lumo Road, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9651-4473","authenticated-orcid":false,"given":"Gang","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences (Wuhan), 388 Lumo Road, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6280-8791","authenticated-orcid":false,"given":"Zhenwen","family":"He","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences (Wuhan), 388 Lumo Road, Wuhan 430074, China"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.enbuild.2018.09.002","article-title":"Extracting typical occupancy data of different buildings from mobile positioning data","volume":"180","author":"Jiefan","year":"2018","journal-title":"Energy Build."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1016\/j.camwa.2012.09.011","article-title":"Is the k-NN classifier in high dimensions affected by the curse of dimensionality?","volume":"65","author":"Pestov","year":"2013","journal-title":"Comput. Math. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10586-017-0982-5","article-title":"A Gaussian process based big data processing framework in cluster computing environment","volume":"21","author":"Manogaran","year":"2018","journal-title":"Clust. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/j.future.2017.09.020","article-title":"Next generation cloud computing: New trends and research directions","volume":"79","author":"Varghese","year":"2018","journal-title":"Future Gener. Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Byun, H., and Lim, H. (2020). Comparison on Search Failure between Hash Tables and a Functional Bloom Filter. Appl. Sci., 10.","key":"ref_5","DOI":"10.3390\/app10155218"},{"key":"ref_6","first-page":"759","article-title":"Large Spatial Database Indexing with aX-tree","volume":"3","author":"Samson","year":"2018","journal-title":"Int. J. Sci. Res. Comput. Sci. Eng. Inf. Technol."},{"doi-asserted-by":"crossref","unstructured":"Oukid, I., Lasperas, J., Nica, A., Willhalm, T., and Lehner, W. (July, January 26). FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.","key":"ref_7","DOI":"10.1145\/2882903.2915251"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0004-3702(79)90003-1","article-title":"The B* tree search algorithm: A best-first proof procedure","volume":"12","author":"Berliner","year":"1979","journal-title":"Artif. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.ins.2018.09.012","article-title":"Fast neighbor search by using revised kd tree","volume":"472","author":"Chen","year":"2019","journal-title":"Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s10707-018-0330-9","article-title":"Spatial data management in apache spark: The geospark perspective and beyond","volume":"23","author":"Yu","year":"2019","journal-title":"Geoinformatica"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1007\/s10586-017-1183-y","article-title":"B+-tree construction on massive data with Hadoop","volume":"22","author":"Ngu","year":"2019","journal-title":"Clust. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.5121\/ijdms.2017.9602","article-title":"Spatial R-tree index based on grid division for query processing","volume":"9","author":"Rslan","year":"2017","journal-title":"Int. J. Database Manag. Syst. (IJDMS)"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"4676","DOI":"10.1016\/j.eswa.2015.01.011","article-title":"Optimizing R-tree for flash memory","volume":"42","author":"Jin","year":"2015","journal-title":"Expert Syst. Appl."},{"doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.P., Schneider, R., and Seeger, B. (1990, January 23\u201325). The R*-tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic, NJ, USA.","key":"ref_14","DOI":"10.1145\/93597.98741"},{"doi-asserted-by":"crossref","unstructured":"Eldawy, A., and Mokbel, M.F. (2015, January 13\u201317). Spatialhadoop: A mapreduce framework for spatial data. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, Seoul, Korea.","key":"ref_15","DOI":"10.1109\/ICDE.2015.7113382"},{"doi-asserted-by":"crossref","unstructured":"Lee, J., Hong, B., Hong, J., Kim, C., and Kim, W.C. (2018, January 15\u201317). Optimal index partitioning of main-memory based TPR*-tree for real-time tactical moving objects. Proceedings of the 2018 IEEE International Conference on Big Data and Smart Computing (BigComp), Shanghai, China.","key":"ref_16","DOI":"10.1109\/BigComp.2018.00070"},{"doi-asserted-by":"crossref","unstructured":"Jensen, C.S., Lu, H., and Yang, B. (2009, January 8\u201310). Indexing the trajectories of moving objects in symbolic indoor space. Proceedings of the International Symposium on Spatial and Temporal Databases, Aalborg, Denmark.","key":"ref_17","DOI":"10.1007\/978-3-642-02982-0_15"},{"doi-asserted-by":"crossref","unstructured":"Islam, M.S., Liu, C., Rahayu, W., and Anwar, T. (2016, January 24\u201328). Q+ tree: An efficient quad tree based data indexing for parallelizing dynamic and reverse skylines. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, Indianapolis, IN, USA.","key":"ref_18","DOI":"10.1145\/2983323.2983764"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1007\/s10586-015-0475-3","article-title":"Decomposition tree: A spatio-temporal indexing method for movement big data","volume":"18","author":"He","year":"2015","journal-title":"Clust. Comput."},{"doi-asserted-by":"crossref","unstructured":"Baofeng, Y., Cheng, M., Shaofeng, C., Lei, W., and Youqiang, G. (2018, January 4\u20136). A Dynamic Prefix XML Encoding Scheme Based on Fraction. Proceedings of the 2018 3rd International Conference on Information Systems Engineering (ICISE), Shanghai, China.","key":"ref_20","DOI":"10.1109\/ICISE.2018.00025"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.jss.2017.07.005","article-title":"Efficient query processing on large spatial databases: A performance study","volume":"132","author":"Roumelis","year":"2017","journal-title":"J. Syst. Softw."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/338\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:44:39Z","timestamp":1760179479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,14]]},"references-count":21,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120338"],"URL":"https:\/\/doi.org\/10.3390\/a13120338","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,12,14]]}}}