高维空间中的数据检索和分析是信息检索领域里一个历史悠久且重要的部分。尤其是在当下的人工智能和大数据时代，机器学习领域内的表征学习技术得到长足发展。人们可以将自然世界中目标所蕴含的丰富语义信息嵌入到高维空间当中，进而得到该目标的以高维稠密向量表示的精确表达。在高维空间中进行数据分析和检索最大的挑战有两个:第一，大量高维向量之间进行距离计算所带来的计算量代价使得现有算法往往难以实用;第二，以往算法对高维空间中数据结构进行建模的方式不能高效表达数据点之间的相互关系。为了解决以上两个挑战带来的问题，为了使高维空间中的数据检索和分析算法可以真正达到实用的程度，本文开展了以下研究工作:
　　1.基于辐射伸展图的近似最近邻检索算法。基于近似近邻图(Approximate ProximityGraph，APG)的高维空间检索算法是近年来信息检索领域一个新兴的热点。尽管一些图算法在公开的测试基准上取得了良好的表现。但这些近似近邻图算法都存在以下问题:1)缺少时间复杂度理论保证，检索行为无法预测;2)索引结构庞大，内存消耗大;3)图结构的联通性没有保障，最差情况无法预测。为了解决以上问题，从理论层面出发，找到了一种检索行为可预测，计算复杂度有理论保证的新型近邻图结构，命名为单调相对近邻图(Monotonic Relative Neighborhood Graph，MRNG)。更进一步，这种理论图结构的索引构建复杂度过高，为了解决超大规模检索问题，提出了MRNG的近似结构——辐射伸展图(Navigating Spreading-out Graph，NSG)，并成功在多个公开数据集和上亿级别的数据集上实现了高效检索，超越了当时最高效的方法i并成功部署在淘宝网搜索引擎中。
　　2.基于卫星系图的近似最检索近邻算法。尽管NSG算法效果拔群，但在“基于辐射伸展图的近似最近邻算法”的研究过程中，仍然发现有以下几个问题可以进一步思考:1)对于NSG算法的理论模型MRNG，在证明其理论检索复杂度的时候，做了一个较强的假设，即待检索点(query)本身存在于数据库之中。而在实际应用场景中，query大多数时候无法在数据库内直接找到。比如，在图片搜索引擎中(以图搜图)，用户上传的图片很可能是刚刚拍下的照片，在数据库内很可能不存在完全一样的图片，其高维向量表示也很可能不存在于数据库内。在检索时，往往只能返回与其最近接的向量(即近邻)。发现，待检索点是否存在于数据库对基于近邻图的检索算法的表现有显著影响。2)NSG构建索引的复杂度高于O(NlogN)，其中N为数据集点总数。在超大规模数据集上，这样的索引构建和更新效率较为低下。从这两个问题出发，找到了一种新的图结构，命名为卫星系图(Satellite System Graph，SSG)。SSG不仅对存在于数据库的query的检索有理论保证，也对不存在于数据库内的query有理论保证，同时设计了SSG的近似结构Navigating SSG(NSSG)，极大地降低了索引构建过程的时间复杂度，同时也提升了检索效率。公开数据集的实验表明，NSSG性能显著优于现存所有算法。
　　3.基于分层锚点图的大规模数据可视化算法。高维空间中的向量可视化是数据分析的重要手段，其主要目的是将人无法直接观察和理解的高维空间数据投影到二到三维空间中，保持原始空间中的数据结构信息，方便人进行分析和理解。特别地，用可视化方法了解数据分布对于设计搜索引擎的索引结构有重要意义。当下的常用高维数据可视化方法有两个问题:1)算法鲁棒性差。不同的初始化对算法呈现的结果有明显影响;2)算法准确性差。算法所呈现的结果中常常出现同类别数据分裂为不同团块的情况。这些问题的出现与之前的算法丢失较远距离的信息有关。为了解决这些问题，提出了一种分层锚点图的近似近邻图结构，把通过聚类得到的中心点作为承载全局结构信息的“锚点”。通过维护锚点与锚点，锚点与普通点，以及普通点与普通点之间的关系来得到正确的低维空间结构布局。在大量公开数据集上的实验证明，我们的方法所呈现的可视化效果解决了上述问题并显著优于其他方法。