iPoc: A Polar Coordinate Based Indexing Method for Nearest Neighbor Search in High Dimensional Space

摘要：

K-nearest neighbor (KNN) search in high dimensional space is essential for database applications, especially multimedia database ap plications, because images and audio clips axe always modeled as high dimensional vectors. However, performance of existing indexing methods degrades dramatically as the dimensionality increases. In this paper, we propose a novel polar coordinate based indexing method, called iPoc, for efficient KNN search in high dimensional space. First, data space is initially partitioned into hypersphcre regions, and then each hypersphere is further refined into hypersectors via hyperspherical surface clustering. After that, a series of local polar coordinate systems can be derived from hypersectors, taking advantage of the geometric characters of hypersec tors. During search processing, iPoc can effectively prune query-unrelated data points by estimating the lower and upper bounds in both radial co ordinate and angle coordinate. Furthermore, we design a key mapping scheme to merge keys measured by independent local polar coordinates into the global polar coordinates. Finally, the global polar coordinates are indexed by a traditional 2-dimensional spatial index, e.g., R-tree. Exten sive experiments on real audio datasets and synthetic datasets confirm the effectiveness and efficiency of our proposal and prove that iPoc is more efficient than the existing high dimensional KNN search methods.

关键词： Nearest neighbor search high dimensional index

作者: Zhang Liu Chaokun Wang Peng Zou Wei Zheng Jianmin Wang

作者单位: Department of Computer Science and Technology, Tsinghua University School of Software, Tsinghua University, Beijing 100084, China Tsinghua National Laboratory for Info School of Software, Tsinghua University, Beijing 100084, China

会议类型: 国际会议

会议名称: 11th International Conference,WAIM 2010(第十一届网络时代管理国际会议)

会议地点: 九寨沟

会议语种:英文

页码: 345-356

在线出版日期: 2010-07-14（万方平台首次上网日期，不代表论文的发表时间）