An Efficient Indexing Method for Load Networks - Cha, Guang-Ho (Transactions on Engineering and Computing Sciences, 2019)
We propose a new indexing method, called the Hilbert-tree, to support the fast retrieval on road networks. Our goals are twofold: increasing the storage utilization and decreasing the directory coverage of the index tree. The first goal is achieved by absorbing splitting if possible, and when splitting is necessary, converting two nodes to three. This is done by proposing a good ordering on the directory nodes. The second goal is achieved by representing the directory regions compactly. We note that there is a trade-off between above two design goals, but the Hilbert-treee is so flexible that it can control the trade-off. We present the design of our index tree and associated algorithms. In addition, we report the results of a series of tests, comparing the proposed index tree with the buddy-tree, which is one of the most successful access methods for a multidimensional space. The results show the superiority of our method.