许多新出现的数据库应用,如CAD、多媒体、医学图像、时间序列、分子生物学和科学数据库,将它们的数据表示为多/高维特征向量。每个特征向量由d个值组成,可以解释为d维空间中的坐标以及一些相关内容的数据。通常使用两个特征向量之间的距离表示原始高维对象之间的(不)相似性。在许多应用中,需要结合两个数据集中的点对,该操作本质上是高维连接(高维数据空间中各种相似连接的统称)。到目前为止,对高维连接的大多数研究主要集中在基于磁盘的大量数据的高维连接。目前计算机可用主存的容量越来越大且价格逐渐低廉,以及对高维连接的有效处理的需求表明,一大类问题的高维连接能够在主存中处理。△-tree是一种新提出的多层索引,能够加速主存环境中的高维查询,已被证实优于其它主存索引。因此,本文以△-tree为基础,设计了几种类型的高维连接及查询算法,以满足不同应用的需求。本文的主要工作可概括为以下5点：(1)研究了高效的主存索引△-tree及相似连接的特性,分析了△-tree中节点的修剪策略。充分利用△-tree的特性,为单个数据集提出了主存自相似连接算法△-tree-Join。充分利用聚类重合的特性,以△-tree中各节点的中心为聚类中心,设计了主存索弓△-tree-S,基于△-tree-S采用自顶向下的模式为两个不同的数据集提出了主存相似连接算法△-tree-Join*,在这两个算法中使用较少的维数计算节点之间的距离及数据点与节点之间的距离,通过该距离过滤掉不必要的节点和数据点,减少计算量,从根本上提高主存相似连接的效率,实验结果表明这两种连接算法均具有较高的连接效率。(2)分析了kNN查询的搜索半径未知的特点,对主存中的高维k最近邻(kNN)查询算法进行了研究。基于△-tree提出了三种用于高维数据的主存kNN查询算法,通过性能分析和实验证明它们比已有的算法具有更高的查询效率,其中以第三种查询算法BU_DF_knn_Search效率最高。该算法首先通过隶属节点的定义确定查询点在△-tree中的隶属叶子节点,并在该节点中进行kNN搜索,利用较优的kNN候选尽快缩小修剪距离,然后按自底向上的顺序对以隶属叶子节点的各祖先节点为根的子树进行深度优先遍历。(3)分析了kNN连接的性质,对主存中的kNN连接算法进行了研究。根据需求提出了主存kNN连接的索引结构△-tree-R,该索引对生成的每个节点进行了编码。基于△-tree-R和△-tree-S提出了主存kNN连接算法,该算法利用△-tree-R中的编码在△-tree-S中进行解码,快速定位位置对应节点,利用其中的近优kNN候选,并采用自底向上和深度优先搜索相结合的遍历策略,快速缩小kNN修剪距离。实验结果显示A-tree-KNN-Join是一种有效的主存kNN连接算法。(4)分析了RkNN查询的解决方法及高维RkNN查询的特点,得出选择自修剪方法解决高维RkNN查询的结论。基于△-tree-R提出了△-Rdknn-tree索引结构,通过在该索引结构上进行△-tree-KNN-Join的自连接算法,预处理数据集中点的kNN距离信息,并将这些距离扩展到索引△-Rdknn-tree的各层节点中,基于该索引给出了主存反向k最近邻(RkNN)查询算法。(5)研究了主存环境中面向集合的RkNN查询即主存RkNN连接问题。为进行RkNN连接的两个数据集分别构建索引△-Rdknn-tree和△-tree,利用△-Rdknn-tree中各节点具有的RyNN搜索距离信息,基于相似连接算法△-tree-Join*设计了主存RkNN连接算法,通过性能分析证明该算法是有效的。本课题提出的所有主存查询和连接算法均经理论和实验证明,具有实用价值,为主存中高维数据的各种查询及连接算法的研究提供了理论和实践基础。