Title | ||
---|---|---|
Space-Partitioning-Based Bulk-Loading for the NSP-Tree in Non-ordered Discrete Data Spaces |
Abstract | ||
---|---|---|
Properly-designed bulk-loading techniques are more efficient than the conventional tuple-loading method in constructing a multidimensional index tree for a large data set. Although a number of bulk-loading algorithms have been proposed in the literature, most of them were designed for continuous data spaces (CDS) and cannot be directly applied to non-ordered discrete data spaces (NDDS). In this paper, we present a new space-partitioning-based bulk-loading algorithm for the NSP-tree -- a multidimensional index tree recently developed for NDDSs . The algorithm constructs the target NSP-tree by repeatedly partitioning the underlying NDDS for a given data set until input vectors in every subspace can fit into a leaf node. Strategies to increase the efficiency of the algorithm, such as multi-way splitting, memory buffering and balanced space partitioning, are employed. Histograms that characterize the data distribution in a subspace are used to decide space partitions. Our experiments show that the proposed bulk-loading algorithm is more efficient than the tuple-loading algorithm and a popular generic bulk-loading algorithm that could be utilized to build the NSP-tree. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-85654-2_37 | DEXA |
Keywords | Field | DocType |
multidimensional index tree,large data,proposed bulk-loading algorithm,new space-partitioning-based bulk-loading algorithm,space-partitioning-based bulk-loading,popular generic bulk-loading algorithm,properly-designed bulk-loading technique,bulk-loading algorithm,continuous data space,data distribution,non-ordered discrete data spaces,tuple-loading algorithm,indexation | Space partitioning,Data mining,Multidimensional index,Histogram,Data space,Subspace topology,Computer science,Tree (data structure),FSA-Red Algorithm | Conference |
Volume | ISSN | Citations |
5181 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 15 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gang Qian | 1 | 784 | 63.77 |
Hyun-jeong Seok | 2 | 4 | 1.09 |
Qiang Zhu | 3 | 398 | 60.85 |
Sakti Pramanik | 4 | 770 | 204.19 |