IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2008 E91-D(2):243-250; doi:10.1093/ietisy/e91-d.2.243

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by YEO, M. H. Articles by YOO, J. S. Search for Related Content Social Bookmarking          What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Regular Section -- Papers -- Database

The Optimization of In-Memory Space Partitioning Trees for Cache Utilization

Myung Ho YEO¹, Young Soo MIN², Kyoung Soo BOK³ and Jae Soo YOO¹

¹ The authors are with the Department of Computer and Communication Engineering, Chungbuk National University, Cheongju, Korea. E-mail: yjs{at}cbnu.ac.kr, ² The author is with Electronics and Telecommunications Research Institute (ETRI), Daejeon, Korea., ³ The author is with Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea.

In this paper, a novel cache conscious indexing technique based on space partitioning trees is proposed. Many researchers investigated efficient cache conscious indexing techniques which improve retrieval performance of in-memory database management system recently. However, most studies considered data partitioning and targeted fast information retrieval. Existing data partitioning-based index structures significantly degrade performance due to the redundant accesses of overlapped spaces. Specially, R-tree-based index structures suffer from the propagation of MBR (Minimum Bounding Rectangle) information by updating data frequently. In this paper, we propose an in-memory space partitioning index structure for optimal cache utilization. The proposed index structure is compared with the existing index structures in terms of update performance, insertion performance and cache-utilization rate in a variety of environments. The results demonstrate that the proposed index structure offers better performance than existing index structures.

Key Words: cache conscious, in-memory, index structure, KDB-tree

---

Manuscript received April 6, 2007. Manuscript revised September 1, 2007.

Reference

[1] M.F. Mokbel, T.M. Ghanem, and W.G. Aref, "Spatio-temporal access methods," Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol.26, no.2, pp.40–49, 2003.

[2] B. Wang and J.Q. Gan, "SC-tree: An efficient structure for high-dimensional data indexing," Proc. BNCOD, pp.164–176, 2006.

[3] I. Csabai, M. Trencseni, L. Dobos, P. Jozsa, G. Herczegh, N. Purger, T. Budavari, and A.S. Szalay, "Spatial indexing of large multidimensional databases," Proc. CIDR, pp.207–218, 2007.

[4] J. An, Y.P. Chen, Q. Xu, and X. Zhou, "A new indexing method for high dimensional dataset," Proc. DASFAA, pp.385–397, 2005.

[5] K. Chakrabarti and S. Mehrotra, "The hybrid tree: An index structure for high dimensional feature spaces," Proc. ICDE, pp.440–447, 1999.

[6] K.S. Bok, D.M. Seo, S.S. Shin, and J.S. Yoo, "TPKDB-tree: An index structure for efficient retrieval of future positions of moving objects," Proc. ER, pp.67–78, 2004.

[7] J.T. Robinson, "The K-D-B-tree: A search structure for large multidimensional dynamic indexes," Proc. ACM SIGMOD Conference, pp.10–18, 1981.

[8] H.Y. Lin and P.W. Huang, "Perfect KDB-tree: A compact KDB-tree structure for indexing multidimensional data," Proc. ICITA (2), pp.411–414, 2005.

[9] R. Orlandic and B. Yu, "Implementing KDB-trees to support high-dimensional data," Proc. International Database Engineering & Applications Symposium, pp.58–67, 2001.

[10] B. Yu, T. Bailey, R. Orlandic, and J. Somavaram, "KDB_KD-tree: A compact KDB-tree structure for indexing multidimensional data," Proc. International Conference on Information Technology: Coding and Computing, pp.676–680, 2003.

[11] P. Bernstein, M. Brodie, S. Ceri, D.D. Witt, M. Franklin, H. Garcia-Molina, J. Gray, J. Held, J. Hellerstein, H.V. Jagadish, M. Lesk, D. Maier, J. Naughton, H. Pirahesh, M. Stonebraker, and J. Ullman, "The asilomar report on database research," SIGMOD Record, vol.27, no.4, pp.74–80, 1998.

[12] P. Boncz, S. Manegold, and M.L. Kersten, "Database architecture optimized for the new bottleneck: Memory access," Proc. 25th VLDB Conference, pp.54–65, 1999.

[13] A. Ailamaki, D.J. DeWitt, M.D. Hill, and D.A. Wood, "DBMSs on a modern processor: Where does time go?," Proc. 25th VLDB Conference, pp.266–277, 1999.

[14] J. Rao and K.A. Ross, "Cache conscious indexing for decision-support in main memory," Proc. 25th VLDB Conference, pp.78–89, 1999.

[15] J. Rao and K.A. Ross, "Making B⁺-trees cache conscious in main memory," Proc. ACM SIGMOD Conference, pp.475–486, 2000.

[16] K. Kim, S.K. Cha, and K. Kwon, "Optimizing multidimensional index trees for main memory access," Proc. ACM SIGMOD Conference, pp.139–150, 2001.

[17] P. Mucci, The Performance API (PAPI), White Paper of the University of Tennessee, available from http://icl.cs.utk.edu/projects/papi/, 2001.

[18] S.T. Leutenegger, "Multi dimensional data sets," http://www.cs.du.edu/~leut/MultiDimData.html, 1996.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by YEO, M. H. Articles by YOO, J. S. Search for Related Content Social Bookmarking          What's this?