An Efficient Indexing Method for Load Networks
DOI:
https://doi.org/10.14738/tmlai.66.5861Keywords:
Indexing method, Load networks, Multidimensional indexAbstract
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.
References
(1) Peano, Z., Sur une courbe qui remplit toute une aire plane. Math. Ann., 1890. 36.
(2) Hilbert, D., Uber die stetige Abbildung einer Linie auf ein Flachenstuck. Math. Ann., 1891. 38.
(3) Faloutsos, C., Gray codes for partial match and range querie. IEEE Trans. on Software Engineering, 1998. 14(10): p. 1381-1393.
(4) H.V. Jagadish, H.V., Linear Clustering of Objects with Multiple Attributes. Proc. ACM SIGMOD Conf., 1990.
(5) Faloutsos, C. and Roseman, S., Fractals for secondary key retrieval. Proc. 8th ACM SIGACT-SIGMOD-SIGART Symposium on PODS, 1989.
(6) Orenstein, J.A. and Merrett, T.H., A Class of Data Structures for Associative Searching. Proc. 3rd ACM SIGACT-SIGMOD Symposium on PODS, 1984.
(7) Kumar, A., G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. on Knowledge and Data Engineering, 1994. 6(2): p. 341-347.
(8) Yang,Q., Vellaikal, A. and Dao, S., MB+-Tree: A New Index Structure for Multimedia Databases. Proc. Intl. Workshop on Multi-Media Database, 1995.
(9) Comer,D., The Ubiquitous B-tree. ACM Computing Surveys, 1979. 11(2): p. 121-137.
(10) Guttman, A., R-Trees: A Dynamic Index Structure for Spatial Searching. Proc. ACM SIGMOD Conf., 1984.
(11) Roussopoulos,N., et al., Nearest Neighbor Queries. Proc. ACM SIGMOD Conf., 1995.
(12) Seeger, B. and Kriegel, H.-P., The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. Proc. 16th VLDB Conf., 1990.
