Abstract
Recently, a main memory index structure called the cache conscious-generalized search tree (CC-GiST) was proposed. The CC-GiST is such a novel index structure that it can be used for implementing all the existing cache conscious trees with the minimal efforts. It incorporates the pointer compression and the key compression techniques, which were adopted by the existing cache conscious trees to reduce the cache misses, in a single framework. In this paper, we formally analyze the performance of the CC-GiST. We compare the performance of the CC-GiST with the existing cache conscious trees. The result shows that the CC-GiST has the negligible overhead for supporting all the existing cache conscious trees in a single framework, and the performance of the tree is almost unaffected.
Chapter PDF
Similar content being viewed by others
References
Ailamaki, A., DeWitt, D.J., Hill, M.D., Wood, D.A.: DBMS on a Modern Processor: Where Does Time Go? In: Proc. Int’l Conf. Very Large Databases, Edinburgh, Scotland, UK, September 1999, pp. 54–65 (1999)
Bohannon, P., Mcilroy, P., Rastogi, R.: Main-Memory Index Structures with Fixed-Size Partial Keys. In: Proc. ACM SIGMOD/PODS Int’l Conf. Management of Data, Santa Barbara, California, May 2001, pp. 163–174 (2001)
Boncz, P.A., et al.: Database Architecture Optimized for the New Bottleneck: Memory Access. In: Proc. Int’l Conf. Very Large Databases, Edinburgh, Scotland, UK, September 1999, pp. 54–65 (1999)
Calder, B., Krintz, C., John, S., Austin, T.: Cache-Consious Data Placement. In: Proc. 8th Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1998, pp. 139–149 (1998)
Chilimbi, T.M., Larus, J.R., Hill, M.D.: Improving Pointer Based Codes through Cache-Conscious Data Placement, Technical Report, Computer Science Department, University of Wisconsin-Madison (1998)
Chilimbi, T.M., Larus, J.R., Hill, M.D.: Making Pointer Based Data Structures Cache Conscious. IEEE Computer 33(12), 67–74 (2000)
Hellerstein, J.M., Naughton, J.F., Pfeffer, A.: Generalized Search Trees for Database Systems. In: Proc. Int’l Conf. Very Large Data Bases, Zurich, Switzerland, September 1995, pp. 562–573 (1995)
Kim, K., Cha, S.K., Kwon, K.: Optimizing Multidimensional Index Trees for Main Memory Access. In: Proc. ACM SIGMOD/PODS Int’l Conf. Management of Data, Santa Barbara, California, May 2001, pp. 139–150 (2001)
Kim, W.-S., Loh, W.-K., Han, W.-S.: CC-GiST: Cache Conscious-Generalized Search Tree, Technical Report, Department of Computer Engineering, Kyungpook National University (2006), Also available at http://www-db.knu.ac.kr/~wshan/cc-gist.pdf
Rao, J., Ross, K.A.: Making B + -Trees Cache Conscious in Main Memory. In: Proc. ACM-SIGMOD Int’l Conf. Management of Data, Dallas, Texas, May 2000, pp. 475–486 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, WS., Loh, WK., Han, WS. (2006). Performance Analysis of the Cache Conscious-Generalized Search Tree. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science – ICCS 2006. ICCS 2006. Lecture Notes in Computer Science, vol 3993. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758532_85
Download citation
DOI: https://doi.org/10.1007/11758532_85
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34383-7
Online ISBN: 978-3-540-34384-4
eBook Packages: Computer ScienceComputer Science (R0)