| Presentation | 2002/7/10 Accelerating insertion processing to the CSS-tree Yoshihisa HONDA, Hideyuki KAWASHIMA, Michita IMAI, Yuichiro ANZAI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In recent years, memory index structures that accelerate search speed utilizing the structure of CPU cache have proposed. Especially, the Full Cache Sensitive Search Tree (CSS-tree) proposed in 1999 is faster than hash depending on data size and require smaller amount of space than B-tree. On the other hand, reconstructing the CSS-tree is so slow that it has been considered that the CSS-tree is only useful under static environments such as OLAP. However, if updating is limited only to additional insertions, the reconstruction cost can be dramatically decreased. Then, in this research, we propose the new techniques that accelerate insertion processing to the C-SS-tree. The technique consists of (1) preliminary acquiring excess index structure space to reduce cost for node expanding and (2) omitting leaf nodes to reduce cost for remapping the leaf nodes and instead, storing key value into internal nodes. To evaluate the proposed technique, we implemented an experimental system with C language and assemblers on SunOS 5.6 and measured the insertion time and the size of memory space for the structure. The result showed that the proposed technique accelerates 7.18 times faster than original technique. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | CSS-tree / database System / memory index structure / cache memory |
| Paper # | DE2002-20 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2002/7/10(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Data Engineering (DE) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Accelerating insertion processing to the CSS-tree |
| Sub Title (in English) | |
| Keyword(1) | CSS-tree |
| Keyword(2) | database System |
| Keyword(3) | memory index structure |
| Keyword(4) | cache memory |
| 1st Author's Name | Yoshihisa HONDA |
| 1st Author's Affiliation | Graduate School of Science and Technology, Keio University() |
| 2nd Author's Name | Hideyuki KAWASHIMA |
| 2nd Author's Affiliation | Graduate School of Science and Technology, Keio University |
| 3rd Author's Name | Michita IMAI |
| 3rd Author's Affiliation | Faculty of Science and Technology, keio University |
| 4th Author's Name | Yuichiro ANZAI |
| 4th Author's Affiliation | Faculty of Science and Technology, keio University |
| Date | 2002/7/10 |
| Paper # | DE2002-20 |
| Volume (vol) | vol.102 |
| Number (no) | 207 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |