位置敏感哈希函数数据结构的概率分析

对于高维空间的近邻查找问题,位置敏感哈希(LSH)在查询代价和磁盘空间利用上有着出色表现。在传统分析模型下,LSH被视作随机算法,唯一不确定因素就是哈希函数的选择。研究中将这种模型下得到的碰撞概率称为基于哈希函数的碰撞概率。在本文中,使用了不同的分析模型对LSH作了理论分析。此工作的出发点有2个:1)在现有的分析模型下,用户为了达到理论的效果,必须对每个查询点产生随机的数据结构,这在实际应用中是不现实的。2)用户所关心的性能指标是随机查询点在一个数据结构上的期望碰撞概率。基于此,本篇论文即推导了在汉明距离下,随机点对在任意单个哈希函数上的碰撞概率。研究将此模型下推导出的碰撞概率称为基于随机查询的碰撞概率。同时也一并证明了在汉明空间中,2种碰撞概率完全相同。

基于位置敏感哈希的入侵检测研究与应用

在对网络入侵数据进行检测时,由于入侵数据具有不同的数据特征,入侵形式也不同,使得入侵数据与其约束条件存在较强的关联性。采用传统的方法进行检测时,关联性会对入侵数据的标记带来干扰,选出大量相关数据,不能很好的消除关联数据,导致检测精确度低、效率差的问题。提出采用位置敏感哈希的入侵检测方法。在位置敏感哈希函数的基础上引入监督聚类入侵检测数据集,对部分标记的入侵数据进行监督聚类,组建位置敏感哈希入侵检测模型,并利用建立的位置敏感哈希入侵检测模型来约束大多数未标记入侵数据的聚类,并不断的扩大标记的人侵数据集合,融合于改进的k-近邻法对最终未标记的入侵数据确定其类型,进而有效的完成了对网络的入侵检测。实验结果证明,改进的位置敏感哈希的入侵检测方法检测精确度高。

利用光谱角敏感森林的高光谱数据快速匹配方法

提出了一种新的光谱匹配算法——光谱角敏感森林方法。在位置敏感哈希函数算法的基础上引入光谱角度量,并利用新的数据桶检索结构改进了原位置敏感哈希函数算法中部分目标光谱点无法得到匹配光谱的缺陷。理论和实验证明,光谱角敏感森林算法的计算效率较传统高维数据匹配方法有较明显优势。

一种支持高维数据查询的并行索引机制

提出了一种基于独立特征的并行索引体系结构以检索符合正态分布的高维数据.通过分析并行搜索的多维数据及其复杂度,结合用户设定的维度权重返回待核实的结果,最后通过加权相似度计算函数合并检索结果以完成kNN查询.针对高维数据的异构性特点,给出了规范情景上下文信息数据的算法.通过联合香港大学的2个社区和深圳先进研究院的CNGrid社区进行的测试,证明基于并行检索机制的100NN查询准确率可达93%,在千万个高维数据中的检索时间小于0.7s,结果表明所提出的并行索引机制能有效提高查询效率,尤其适合海量高维数据的有偏组合特征查询.