Arnas David, Leake Carl, Mortari Daniele
Universidad de Zaragoza, Valentin Carderera 4, Huesca 22003, Spain.
Aerospace Engineering, Texas A&M University, College Station, TX 77843-3141, USA.
Appl Math Comput. 2020 May 1;372. doi: 10.1016/j.amc.2019.125010. Epub 2020 Jan 8.
This work focuses on the definition and study of the -dimensional -vector, an algorithm devised to perform orthogonal range searching in static databases with multiple dimensions. The methodology first finds the order in which to search the dimensions, and then, performs the search using a modified projection method. In order to determine the dimension order, the algorithm uses the -vector, a range searching technique for one dimension that identifies the number of elements contained in the searching range. Then, using this information, the algorithm predicts and selects the best approach to deal with each dimension. The algorithm has a worst case complexity of , where is the number of elements retrieved, is the number of elements in the database, and is the number of dimensions of the database. This work includes a detailed description of the methodology as well as a study of the algorithm performance.
这项工作聚焦于n维m向量的定义与研究，这是一种为在多维度静态数据库中执行正交范围搜索而设计的算法。该方法首先确定搜索维度的顺序，然后使用改进的投影方法进行搜索。为了确定维度顺序，该算法使用m向量，这是一种用于一维的范围搜索技术，可识别搜索范围内包含的元素数量。然后，利用此信息，该算法预测并选择处理每个维度的最佳方法。该算法的最坏情况复杂度为O(r log(n/d) + m log d)，其中r是检索到的元素数量，n是数据库中的元素数量，d是数据库的维度数量。这项工作包括对该方法的详细描述以及对算法性能的研究。
