在信息检索和数据库应用中,一种常见的查询方式是从一组数据对象(如文档,图像)中返回符合条件的成对对象,例如,在数据库应用中经常需要根据相似度将两个相似的文档或者网页作为结果返回给用户,这样的操作在最近的研究工作中定义为相似性连接。在本文中,我们将这一类典型的查询形式进一步扩展为对偶连接问题。对应的问题描述为,给定一组数据对象和操作在对象上的关系度量(如相似度或相关性系数)找到所有符合关系度量阈值条件的对象对。由于问题定义的简单性和其中所定义的关系度量的多样性,对偶连接问题在各种不同领域的问题中扮演核心的角色,例如,副本检测,关联规则挖掘,统计相关性分析,协同过滤等。同时,在技术上的挑战性也使这一问题在以往的研究工作中得到广泛的关注。基于避免对所有对象的两两比较的动机,一系列适用于不同数据类型和关系度量的启发式剪枝算法被开发出来,其中有代表性的如倒排表索引,前缀／后缀过滤,准单调性剪枝等等。然而,这一类基于启发式的方法在解决问题时,其执行性能仍然收到一些内在缺陷的负面影响,例如剪枝的效果得不到保证,无法针对不同特征的数据集优化算法性能,以及缺乏一种通用的算法模型等。进一步的优化在确定性的算法框架下难以达到。近来,很多研究发现仅仅得到近似的结果在现实中很多查询应用中可以被接受,并且这种做法可以大幅度降低查询的时间。这样的原则也同样适用于对偶连接问题,因此,本文重点关注利用一组随机算法高效的处理“近似版本”的对偶连接问题。在这样的情况下,一组值得关注的问题是：(1)在面对大规模数据时,是否可以将原始数据通过随机模式转化为规模小到可以装入内存的“概要”,并且通过处理概要来执行关系度量下的查询；(2)能否以较小的代价(如通过概要)足够精确地估计对象之间的关系度量的值；(3)怎样在解决问题时尽可能避免对象之间的两两比较,或者说是否可以采用一种剪枝方法将不符合条件的结果尽可能地去除。本文中发现在空间最近邻中广泛使用的Locality-sensitive Hashing(LSH)思想为对偶连接问题的解决提供了一个很好的借鉴。类似的哈希映射模式在对偶连接问题中成为从原始数据生成概要的理想选择。在此基础上,本文为了高效执行对偶连接查找提出了一组基于随机模式的解决方案,其中所有的算法模型均基于哈希模式生成的概要进行操作,因此称之为哈希算法。总结起来,本文工作在理论模型方面主要的贡献包括：(1)研究了所定义的哈希模式的存在性与关系度量之间的关系,给出了哈希模式对于度量存在的一组必要条件。这一部分的结论实际上也给出了哈希算法的适用范围。具体地说,我们首先从以往研究中的抽样技术和扰动算法中抽象出一组针对常用关系度量的哈希模式,并根据这些典型的实例归纳和证明出一组哈希模式对于度量存在性的必要条件。(2)提出了一个对关系度量的区间估计模型。区间估计模型与早期工作中的期望估计模式相比,具有在分析上可证和执行上可控的估计精度,并且可以通过调整参数优化整体剪枝算法的效率。在分析方面,我们证明区间估计模型在解决对偶连接问题所需哈希演算的次数(代表主要的时空代价)为O(ε-2 log n)(n代表对象总数)；在执行方面,我们讨论了估计模型所需的数据结构并对算法整体的时间和空间复杂度进行了分析,并且通过在真实数据集上的执行结果揭示了区间估计模型与之前工作中的期望估计模型比较在性能上的优势。(3)设计一个高效的随机过滤器模型。这类模型相比估计模型在执行上具有更小的时间／存储需求。这里首先归纳和分析了移植自最近邻问题中LSH技术的原始过滤器模型(称为Basic LSH,简称B-LSH),指出了其在处理对偶连接问题时的不足。随后,我们提出了具有更高效率的近似随机过滤器模型ApproximationLSH,简称A-LSH),使得所需的哈希演算次数从B-LSH模式的(?)级降低至O(ε-2 log n)级。并且,我们证明A-LSH过滤器模型所具有的性质使其克服了原始B-LSH模式的性能瓶颈。在应用方面,我们将提出的通用估计模型和通用过滤器模型分别置于一组实际应用问题中,针对每一个具体问题对随机模型进行扩展和调整,使之适用于具体的问题环境,并藉此揭示不同随机模型在执行时的内部行为和性能特性。这部分工作所涉及的主要内容包括：(1)置信度估计和快速挖掘置信度关联规则。从不频繁的项中挖掘具有高置信度的关联在很多实际应用中扮演重要的角色。通过对估计模型进行扩展和变型可以设计一个适用与置信度的区间估计模式并由此得到一个高效的剪枝算法进行快速的置信度关了规则挖掘。通过在真实和人工数据上执行的实验表明,由此得到的剪枝算法在执行时间,可扩展性等各项性能指标上明显优于基于树计数结构的确定性算法。对这一应用问题的解决体现了通用估计模型的理论适用范围可通过在原有基础上设计新模式得到有效的扩展。(2)在Pearson统计相关系数下识别高度相关项。在统计相关性度量下发现具有高度相关性的项在机器学习、数据库等领域具有重要的现实意义。通常使用的基于上界准单调性的启发式剪枝方法的执行效果不尽理想。我们发现Pearson系数可被随机过滤器模型处理,特别地,根据问题本身的特点使用A-LSH模式构造的算法在执行时间以及数据规模的适应性上均明显优于启发式方法和B-LSH过滤器算法,特别是在B-LSH方法出现瓶颈的低阈值条件下,效率提升更为明显。对此问题的解决过程体现了对随机过滤器模型适用条件的进一步扩展,并从执行上体现了A-LSH模式带来的显著的性能提升。(3)加权集合相似度下的相似性连接。在描述查找对象时附加权重信息通常会显著增加查询的精度,但同时也加大了技术上的挑战性。针对加权集合相似度,我们构造对应的哈希模式从而得到区间估计模型;同时提出一个执行更加简单且具有更高时间空间效率的随机算法,即通过基于Cauthy的分布LSH函数得到的过滤模式算法,实验证明后者与基于估计模型的算法相比具有更高的执行效率。对该应用问题的处理体现了在可以同时适用估计模型和过滤器模型时使用不同哈希模式以及相应的不同模型对于执行效率的影响。总而言之,本文重点关注在信息检索、数据库以及数据挖掘等领域中广泛存在的一类查询形式——对偶连接查询以及对该问题的基于随机模式的解法。为此,我们得到一组基于哈希模式的算法模型,并在此过程中讨论了哈希模式的适用范围。同时,针对一组具体的应用问题,我们分别扩展和实施了理论上的两类通用模型以获得有效处理实际问题的算法,通过在不同的真实和人工数据上进行的一系列实验表明,在不同的应用环境下,基于所提出的随机模型的算法在执行时间,扩展性以及成本效益等性能上均超过相应的确定性算法以及以往研究工作中出现的随机算法。