An Efficient Multi-Dimensional Index Structure for Large Data Set
ByoungYup Lee, Jaesoo Yoo · Journal of the Korean Association of Geographic Information Studies · 2002
In this paper, We propose a multi-dimensional index structure, called a VA (vector approximate) -tree that constructs a tree with vector approximates of multi-dimensional feature vectors. To save storage space for index structures, the VA-tree employs vector approximation concepts of VA-file that presents feature vectors with much smaller number of bits than original value. Since the VA-tree is a tree structure, it does not suffer from performance degradation owing to the increase of data. Also, even though the VA-tree is MBR Minimum Bounding Region) based tree structure like a R-tree, its split algorithm never allows overlap between MBRs. We show through various experiments that our proposed VA-tree is the efficient index structure for large amount of multi-dimensional data.