Presentation | 2002/7/10 Cache Conscious Trees using Arrays : A proposal Hidehisa TAKAMIZAWA, Masayoshi ARITSUGI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Cache conscious indexing structures attracts many researchers because of their efficiency. The key idea to implement the trees is to remove pointers from nodes of trees. This allows a node to increase the number of child nodes, thereby making the height of a tree low. As a result, cache is used effectively. In this paper, Array-Based Cache conscious trees (ABC trees in short) are proposed. ABC trees are constructed as complete trees using arrays. While the tree is treated like a B+tree, it does not hold pointers to child nodes. A node of the ABC tree can be extracted by calculating spatial relations among nodes in the tree. Updates can be processed efficiently because the necessary space for nodes of the complete tree are allocated and the whole spatial relations among nodes in the space can be calculated in advance to the processing. Therefore, it is expected that the costs of node split and merge are relatively low. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Cache / Indexing Structure / Main Memory Database |
Paper # | DE2002-19 |
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) | Cache Conscious Trees using Arrays : A proposal |
Sub Title (in English) | |
Keyword(1) | Cache |
Keyword(2) | Indexing Structure |
Keyword(3) | Main Memory Database |
1st Author's Name | Hidehisa TAKAMIZAWA |
1st Author's Affiliation | Department of Computer Science, Faculty of Engineering, Gunma University() |
2nd Author's Name | Masayoshi ARITSUGI |
2nd Author's Affiliation | Department of Computer Science, Faculty of Engineering, Gunma University |
Date | 2002/7/10 |
Paper # | DE2002-19 |
Volume (vol) | vol.102 |
Number (no) | 207 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |