计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (10): 881-889.DOI: 10.3778/j.issn.1673-9418.2010.10.002

• 学术研究 • 上一篇    下一篇

多维度量空间中发现相互kNN*

刘俊岭1,2, 孙焕良2+   

  1. 1. 东北大学 信息科学与工程学院, 沈阳 110004
    2. 沈阳建筑大学 信息与控制工程学院, 沈阳 110168
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-10-01 发布日期:2010-10-01
  • 通讯作者: 孙焕良

Finding Mutual k-Nearest Neighbors in Multi-Metric Space*

LIU Junling 1,2, SUN Huanliang2+   

  1. 1. College of Information Science and Engineering, Northeastern University, Shenyang 110004, China
    2. College of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-10-01 Published:2010-10-01
  • Contact: SUN Huanliang

摘要: 发现两类对象的相互k最近邻居可为工作匹配、大学选择等应用提供决策。现有的方法主要处理单度量空间(如L2 norm), 这些方法有可能导致不公平的匹配。形式化多度量空间的相互最近邻问题, 提出基于空间索引的多度量空间下的相互k最近邻算法。利用人工数据集, 测试了大量的参数设置下的算法性能, 结果表明提出的算法优于可选的直接算法。

关键词: 相互k最近邻, 多度量空间, R树, Minkowski区域

Abstract: Finding mutual k-nearest neighbors in two kinds of objects can provide decisions for applications such as job matching and college selection. Existing methods mainly focus on processing mutual nearest neighbor queries in one single metric space (e.g. L2 norm) and this will probably lead to an unfair assignment. This paper formally ex-plores the problem of mutual nearest neighbors in multi-metric space. Based on space indices, algorithms are pro-posed for finding mutual k-nearest neighbors in multi-metric space. With the synthetic dataset, the algorithms are experimentally evaluated for a wide range of variable settings, and show that the proposed solutions outperform al-ternative brute force methods.

Key words: mutual k-nearest neighbors, multi-metric space, R-tree, Minkowski region

中图分类号: