A hyperplane based indexing technique for high-dimensional data

详细信息    查看全文

• 作者：Guoren Wang ; Xiangmin Zhou ; Bin Wang ; Baiyou Qiao ; Donghong Han
• 关键词：Similarity search ; High-dimensional indexing ; Hyperplane ; Range query ; k-NN query
• 刊名：Information Sciences
• 出版年：2007
• 出版时间：1 June 2007
• 年：2007
• 卷：177
• 期：11
• 页码：2255-2268
• 全文大小：229 K

文摘

In this paper, we propose a novel hyperplane based indexing method to support efficient processing of similarity search queries in high-dimensional spaces. The main idea of the proposed index is to improve data partitioning efficiency in a high-dimensional space by using a hyperplane, which further partitions a subspace and can also take advantage of the twin node concept used in the key dimension based index. Compared with the key dimension concept, the hyperplane is more effective in data filtering. High space utilization is achieved by dynamically performing data reallocation between twin nodes. In addition, a post processing step is used after index building to ensure effective filtration. Extensive experiments based on two types of real data sets are conducted and the results illustrate a significantly improved filtering efficiency. Because of the feature of hyperplane, the proposed indexing method is only suitable to Euclidean spaces.