Performance Enhancement of a DVA-tree by the Independent Vector Approximation


The KIPS Transactions:PartD, Vol. 19, No. 2, pp. 151-160, Apr. 2012
10.3745/KIPSTD.2012.19.2.151,   PDF Download:

Abstract

Most of the distributed high-dimensional indexing structures provide a reasonable search performance especially when the dataset is uniformly distributed. However, in case when the dataset is clustered or skewed, the search performances gradually degrade as compared with the uniformly distributed dataset. We propose a method of improving the k-nearest neighbor search performance for the distributed vector approximation-tree based on the strongly clustered or skewed dataset. The basic idea is to compute volumes of the leaf nodes on the top-tree of a distributed vector approximation-tree and to assign different number of bits to them in order to assure an identification performance of vector approximation. In other words, it can be done by assigning more bits to the high-density clusters. We conducted experiments to compare the search performance with the distributed hybrid spill-tree and distributed vector approximation-tree by using the synthetic and real data sets. The experimental results show that our proposed scheme provides consistent results with significant performance improvements of the distributed vector approximation-tree for strongly clustered or skewed datasets.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. H. Choi and K. C. Lee, "Performance Enhancement of a DVA-tree by the Independent Vector Approximation," The KIPS Transactions:PartD, vol. 19, no. 2, pp. 151-160, 2012. DOI: 10.3745/KIPSTD.2012.19.2.151.

[ACM Style]
Hyun Hwa Choi and Kyu Chul Lee. 2012. Performance Enhancement of a DVA-tree by the Independent Vector Approximation. The KIPS Transactions:PartD, 19, 2, (2012), 151-160. DOI: 10.3745/KIPSTD.2012.19.2.151.