随着社会的发展和时代的进步,数据维数越来越高,数据库规模越来越大,复杂性越来越高,那么怎么从海量高维数据中快速找到目标数据成了一个难题。对于低维的小数据集,我们可以通过线性计算很容易解决,但是对于海量高维数据集,线性查找往往需要很庞大的运算量,非常耗时。为了解决这一难题,一方面需要设计更加高效的索引结构对数据进行有效组织,另一方面需要为索引结构配以高效的查询机制实现更加准确快速的搜索。这种技术我们称之为高维最近邻查询(Nearest Neighbor,NN)技术,现已成为海量多媒体数据检索研究中的一个基础问题。由于高维空间中存在“维数灾难”现象,使得高效查找精确最近邻变得十分困难。而通过牺牲少量精度以求解近似最近邻(Approximate Nearest Neighbor,ANN)代替精确解却能够获得巨大的效率提升,因此研究者们重点关注近似最近邻查询技术。目前,局部敏感哈希技术(LSH)及其变种被公认为是近似最近邻查询最有效的解决方案。LSH的基本思想就是:原始数据空间相邻的两个点通过相同的映射或投影后,这两个点在新的数据空间中相邻的概率同样很大,而不相邻的两个点被映射进同一个桶里的概率很小。本文对局部敏感哈希技术、空间曲线和近邻图进行了重点研究和分析。在局部敏感哈希技术方面,对目前的多种哈希算法进行了学习和研究,对其技术优劣性进行了分析。局部敏感哈希的优势是能实现候选点的快速筛选,通过构建复合哈希函数能有效过滤不相关点得到高质量的候选集,但缺点是访问候选点依赖大量的随机I/O,而且存在大量漏报,为了获取高质量的返回结果,需要构建多个哈希表,访问足够多的候选点,从而导致了庞大的时间和空间开销。空间曲线可以建立复合哈希值的线序关系,从而能实现邻域的快速定位。近邻图技术借助数据点间的邻接关系能快速地收敛到更好的候选点,但受初始搜索点质量的影响容易陷入局部最优。为了克服当前LSH方法的缺陷,本文提出了一种新的算法——NNG-LSH,该方法通过空间曲线和近邻图来实现邻域快速定位和近邻搜索的局部收敛。作者首先通过空间曲线在复合哈希值上建立一种线序(即字典序)关系,然后对应的原始数据集也是升序排列,这样哈希值相似的点可以被存储在连续的磁盘页上,从而为在查询过程中减少随机I/O访问,实现邻域的快速定位奠定了基础。在近似最近邻查询过程中,引入近邻图,通过查询点所在页面的近邻点进行收敛,从而达到局部近邻优化,提高返回值的准确度。本文通过在四个真实的高维数据集上大量的实验以及对比表明,与当前最新的LSH方法对比,证实NNG-LSH在近似最近邻查询中的准确性和空间需求方面是有优势的。