This paper proposes a fast initial construction method of the GBD-tree. The GDB tree has proper characteristics for management of large amount of 2 or 3 dimensional data. However, the GBD-tree needs long initial const...This paper proposes a fast initial construction method of the GBD-tree. The GDB tree has proper characteristics for management of large amount of 2 or 3 dimensional data. However, the GBD-tree needs long initial construction time by originally proposed one-by-one insertion method. A fast insertion method has been proposed, but it needs large size of buffer capable to hold index information of all entries. The paper proposes another fast initial construction method. The method requires only limited size of work space (buffer). The experimental results show the initial construction time reduces into a third or a quarter of the one-by-one insertion method. The memory efficiency and retrieval efficiency are also improved than the one-by-one insertion method.展开更多
This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteris...This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.展开更多
文摘This paper proposes a fast initial construction method of the GBD-tree. The GDB tree has proper characteristics for management of large amount of 2 or 3 dimensional data. However, the GBD-tree needs long initial construction time by originally proposed one-by-one insertion method. A fast insertion method has been proposed, but it needs large size of buffer capable to hold index information of all entries. The paper proposes another fast initial construction method. The method requires only limited size of work space (buffer). The experimental results show the initial construction time reduces into a third or a quarter of the one-by-one insertion method. The memory efficiency and retrieval efficiency are also improved than the one-by-one insertion method.
文摘This paper describes the nearest neighbor (NN) search algorithm on the GBD(generalized BD) tree. The GBD tree is a spatial data structure suitable for two-or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.
