Bulk operations for space-partitioning trees

Get BibTex-formatted data

Download

PDF

Author

TM Ghanem,R Shah, MF Mokbel,WG Aref, JS Vitter

Entry type

article

Abstract

The emergence of extensible index structures, e.g., GiST (generalized search tree) [J.M. Hellerstein et al. (1995)] and SP-GiST (space-partitioning generalized search tree) [W. G Aref et al., (2001)], calls for a set of extensible algorithms to support different operations (e.g., insertion, deletion, and search). Extensible bulk operations (e.g., bulk loading and bulk insertion) are of the same importance and need to be supported in these index engines. In this paper, we propose two extensible buffer-based algorithms for bulk operations in the class of space-partitioning trees; a class of hierarchical data structures that recursively decompose the space into disjoint partitions. The main idea of these algorithms is to build an in-memory tree of the target space-partitioning index. Then, data items are recursively partitioned into disk-based buffers using the in-memory tree. Although the second algorithm is designed for bulk insertion, it can be used in bulk loading as well. The proposed extensible algorithms are implemented inside SP-GiST; a framework for supporting the class of space-partitioning trees. Both algorithms have I/O bound O(NH/B), where N is the number of data items to be bulk loaded/inserted, B is the number of tree nodes that can fit in one disk page, H is the tree height in terms of pages after applying a clustering algorithm. Experimental results are provided to show the scalability and applicability of the proposed algorithms for the class of space-partitioning trees. A comparison of the two proposed algorithms shows that the first algorithm performs better in case of bulk loading. However the second algorithm is more general and can be used for efficient bulk insertion.

Download

PDF

Date

2004

Journal

Data Engineering, 2004. Proceedings. 20th International Conference on

Key alpha

Aref

Pages

29- 40

Publication Date

2004-01-01

Keywords

buffer storage, computational complexity, tree data structures, tree searching GiST, SP-GiST space-partitioning generalized search tree, buffer-based algorithm, bulk insertion algorithm, bulk loading algorithm, clustering algorithm, disk-based buffer, generalized search tree, hierarchical data structure, in-memory tree, index structure, space-partitioning tree

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Aref,
	title = "Bulk operations for space-partitioning trees ",
	author = "TM Ghanem,R Shah, MF Mokbel,WG Aref, JS Vitter",
	year = "2004",
	journal = "Data Engineering, 2004. Proceedings. 20th International Conference on",
	pages = "29- 40",
	abstract = " The emergence of extensible index structures, e.g., GiST (generalized search tree) [J.M. Hellerstein et al. (1995)] and SP-GiST (space-partitioning generalized search tree) [W. G Aref et al., (2001)], calls for a set of extensible algorithms to support different operations (e.g., insertion, deletion, and search). Extensible bulk operations (e.g., bulk loading and bulk insertion) are of the same importance and need to be supported in these index engines. In this paper, we propose two extensible buffer-based algorithms for bulk operations in the class of space-partitioning trees; a class of hierarchical data structures that recursively decompose the space into disjoint partitions. The main idea of these algorithms is to build an in-memory tree of the target space-partitioning index. Then, data items are recursively partitioned into disk-based buffers using the in-memory tree. Although the second algorithm is designed for bulk insertion, it can be used in bulk loading as well. The proposed extensible algorithms are implemented inside SP-GiST; a framework for supporting the class of space-partitioning trees. Both algorithms have I/O bound O(NH/B), where N is the number of data items to be bulk loaded/inserted, B is the number of tree nodes that can fit in one disk page, H is the tree height in terms of pages after applying a clustering algorithm. Experimental results are provided to show the scalability and applicability of the proposed algorithms for the class of space-partitioning trees. A comparison of the two proposed algorithms shows that the first algorithm performs better in case of bulk loading. However the second algorithm is more general and can be used for efficient bulk insertion.",
	keywords = "buffer storage, computational complexity, tree data structures, tree searching GiST, SP-GiST space-partitioning generalized search tree, buffer-based algorithm, bulk insertion algorithm, bulk loading algorithm, clustering algorithm, disk-based buffer, generalized search tree, hierarchical data structure, in-memory tree, index structure, space-partitioning tree",
}