近似最小树的哈希Dijkstra算法

• 作者: 李厚君 李玉鑑
• 来源期刊: 北京工业大学学报
• 学科: 工学
• 关键词: 近似最小树 局部敏感哈希 Dijkstra
• 年，卷（期）: 2011,（12）
• 所属期刊栏目: 计算机科学
• 页码范围: 1915-1920
• 页数: 6页
• 分类号: TQ015.3
• 语种: 中文

摘要

为了解决Dijkstra（DK）算法对大规模数据构造最小树时效率不高的问题，结合局部敏感哈希映射（LSH），针对欧氏空间中的样本，提出了一种近似最小树的快速生成算法，即LSHDK算法．该算法通过减少查找近邻点的计算量提高运行速度．计算实验结果表明，当数据规模大于50000个点时，LSHDK算法比DK算法速度更快且所计算的近似最小树在维数较低时误差非常小（0．00—0．05％），在维数较高时误差通常为0．1％～3．0％．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李玉鑑		57	357	10.0	17.0
2	李厚君		3	7	2.0	2.0