Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

International Workshop on Intelligent Storage Technology (IST06)

Performance Analysis of the Cache Conscious-Generalized Search Tree

Won-Sik KimContact Information, Woong-Kee LohContact Information and Wook-Shin HanContact Information

(1)  Department of Computer Engineering, Kyungpook National University, Korea
(2)  Department of Computer Science & Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), Korea
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.
Keywords: cache conscious tree, generalized search tree, pointer compression, key compression.

Contact Information Won-Sik Kim
Email: wskim@www-db.knu.ac.kr

Contact Information Woong-Kee Loh
Email: woong@mozart.kaist.ac.kr

Contact Information Wook-Shin Han
Email: wshan@knu.ac.kr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)