Abstract
Generally, multidimensional data require a large amount of storage space. There are a few limits to store and manage those large amounts of data in single workstation. If we manage the data on parallel computing environment which is being actively researched these days, we can get highly improved performance. In this paper, we propose an efficient index structure for multidimensional data that exploits the parallel computing environment. The proposed index structure is constructed based on nP(processor)-n×mD(disk) architecture which is the hybrid type of nP-nD and 1P-nD. Its node structure increases fan-out and reduces the height of an index tree. Our proposed index structure gives a range search algorithm that maximizes I/O parallelism. The range search algorithm is applied to k-nearest neighbor queries. Through various experiments, it is shown that the proposed method outperforms other parallel index structures.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Robinson, J.T.: The K-D-B-tree: A search structure for large multidimensional dynamic indexed. In: Proc. ACM SIGMOD Conference, pp. 10–18 (1981)
Guttman, A.: R-Trees: A dynamic index structure for spatial searching. In: Proc. ACM SIGMOD Conference, pp. 47–57 (1984)
Nievergelt, J., Hinterberger, H., Sevcik, K.: The grid file: An adaptable, symmetric multikey file structure. ACM Transactions on Database Systems 8(1), 38–71 (1984)
Beckmann, N., Kornacker, H.P., Schneider, R., Seeger, B.: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proc. ACM SIGMOD Conference, pp. 322–331 (1990)
Lin, K., Jagadish, H.V., Faloutsos, C.: The TV-Tree: An Index Structure for High-dimensional Data. VLDB Journal 3(4), 517–542 (1994)
Yoo, J.S., Lee, S.H., Cho, K.H., Lee, J.S.: An Efficient Index Scheme for High-Dimensional Image Data. International Journal of Information Technology 6(1), 1–15 (2000)
Berchtold, S., Keim, D.A., Kriegel, H.-P.: The X-tree: An Index Structure for High-Dimensional Data. In: Proc. VLDB, pp. 28–39 (1996)
Chakrabarti, K., Mehrotra, S.: The Hybrid Tree: An Index Structure for High-Dimensional Feature Spaces. In: Proc. ICDE, pp. 440–447 (1999)
Yu, B., Orlandic, R., Bailey, T., Somavaram, J.: KDBKD-Tree: A Compact KDB-Tree Structure for Indexing Multidimensional Data. In: Proc. International Conference on Information Technology: Coding and Computing, pp. 676–680 (2003)
Weber, R., Scheck, H.J., Blott, S.: Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In: Proc. VLDB, pp. 194–205 (1998)
Gionis, A., Indyk, P., Motwani, R.: Similarity Search in High Dimensions via Hashing. In: Proc. VLDB, pp. 518–529 (1999)
Kamel, I., Faloutsos, C.: Parallel R-trees. In: Proc. ACM SIGMOD, pp. 195–204 (1992)
Berchtold, S., Bohm, C., Braunmuller, B., Keim, D.A., Kriegel, H.P.: Fast Parallel Similarity Search in Multimedia Databases. In: Proc. ACM SIGMOD, pp. 1–12 (1997)
Bang, K.S., Lu, H.: The PML-tree: An Efficient Parallel Spatial Index Structure for Spatial Databases. In: Proc. ACM Annual Computer Science Conference, pp. 79–88 (1996)
Scnnitzer, B., Leutenegger, S.T.: Master-Client R-trees: A New Parallel R-tree Architecture. In: Proc. SSDBM, pp. 68–77 (1999)
Fu, X., Wang, D., Zheng, W., Sheng, M.: GPR-Tree: A Global Parallel Index Structure for Multiattribute Declustering on Cluster of Workstations. In: Proc. APDC, pp. 300–306 (1997)
Weber, R.: Parallel VA-File. In: Proc. ECDL, pp. 83–92 (2000)
Wang, B., Horinokuchi, H., Kaneko, K., Makinouchi, A.: Parallel R-tree Search Algorithm on DSVM. In: Proc. DASFAA, pp. 237–245 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bok, K., Seo, D., Song, S., Kim, M., Yoo, J. (2005). An Index Structure for Parallel Processing of Multidimensional Data. In: Fan, W., Wu, Z., Yang, J. (eds) Advances in Web-Age Information Management. WAIM 2005. Lecture Notes in Computer Science, vol 3739. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11563952_51
Download citation
DOI: https://doi.org/10.1007/11563952_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29227-2
Online ISBN: 978-3-540-32087-6
eBook Packages: Computer ScienceComputer Science (R0)