随着计算机技术广泛应用于各行各业,许多应用程序已经能够收集到大量的数据。如何高效地处理大数据具有重大挑战。一个常用的应对手段是采用近似方法。这样做的动机是近似计算结果在许多应用场景中是可以接受的。本文关注多维数据上的两类重要查询——聚集查询和最近邻查询。简单来说,聚集查询就是返回一个或多个聚集值（比如均值AVG、总和SUM等等）的SQL查询。聚集查询处理作为联机分析处理的一个基本组成部分,被广泛运用于决策支持系统。最近邻查询就是要找到距离一个任意给定的查询点最近的数据点。它是众多应用的基础,比如图像检索、产品推荐、模式识别等等。当数据基数很大时,为了减少需要处理的数据量,通常运用随机抽样来高效地处理聚集查询;而当数据维数很大时,为了消除“维数灾难”,通常使用对称局部敏感哈希（简称LSH）或非对称局部敏感哈希（简称ALSH）方法来高效地执行最近邻查询。本文研究了四个与基于随机抽样的近似聚集查询处理和基于LSH或ALSH的近似最近邻查询处理相关的问题。本文的研究内容和贡献总结如下。首先,本文在样本方差等于数据总体方差的假设下研究了基于在线随机抽样的有误差保证的近似聚集查询处理问题。事实上,绝大部分相关的研究工作都需要样本方差等于数据总体方差这个假设。为了解决这个问题,本文首次深入研究了按位抽样范式以用于近似计算AVG聚集和SUM聚集。相较于传统的按数据项抽样范式,按位抽样范式在比特位这个比数据项更细的粒度上进行抽样,因此更加灵活。本文提出了一个称为DVBM的基于按位均匀抽样的近似聚集方法作为这个问题的解决方案。DVBM方法的优化目标是在保证聚集结果满足一个给定的误差界的同时最小化抽样量。在理论上,本文证明了DVBM方法所需的抽样量比按数据项均匀抽样方法所需的抽样量更少。进一步,大量实验结果表明DVBM中的基于按位均匀抽样的近似聚集算法比通常的基于按数据项均匀抽样的近似聚集算法效率高数倍,并且得到的近似聚集结果也更加准确。但是它们在数据倾斜度较高时都很难保证给定的误差界,因为此时样本方差严重偏离数据总体方差,导致上述假设不成立。其次,本文研究了基于在线随机抽样的有强误差保证的近似聚集查询处理问题。为了解决这个问题,本文提出了一个称为DVFM的基于按位均匀抽样的近似聚集方法。为了提供强误差保证,DVFM方法不依赖于样本方差等于数据总体方差这个假设。不过,相较于DVBM方法,DVFM方法会导致一个更大的抽样量。DVFM方法包含两个基于按位均匀抽样的近似聚集算法——一次估计算法和多次估计算法。通过大量实验,本文验证了它们的效率。具体来说,与现有多个同样能够为近似聚集结果提供强误差保证的算法相比,一次估计算法和多次估计算法通常能够取得高得多的效率。此外,实验结果还表明它们确实能够绝对保证给定的误差界。这两个算法需要先验地设置不同的参数,而这些参数值会直接影响到它们的效率。在实践中可以更容易地设置多次估计算法的参数以取得高效率。第三,本文研究了在一个关于lp距离的加权距离函数集合上的近似最近邻查询处理问题,其中集合是预先给定的,是输入参数且它的取值范围是(0,2]。这个问题出现在许多应用场景中,比如个性化产品推荐。本质上,它是要为一个给定的集合中的每个加权lp距离函数支持近似最近邻查询。在这个问题中,本文假设与一个加权lp距离函数关联的权向量的每个元素都是正数。为了解决这个问题,本文提出了首个基于LSH的方法——WLSH。WLSH是现有的唯一适用于任意∈(0,2]的情况且能提供近似比保证的方法。WLSH基于本文为加权距离函数提出的两种LSH函数族——加权LSH函数族和导出加权LSH函数族。WLSH的优化目标是在确保处理查询的效率足够高且查询结果的近似比可以得到保证的同时最小化所需哈希表总数。此外,本文还为WLSH提出了两个优化技术以平衡WLSH的查询效率、查询精度和空间开销。本文在生成数据和真实数据上进行了大量实验,验证了WLSH在查询效率、查询精度和存储空间开销三方面的性能。最后,本文研究了在广义加权曼哈顿距离上的近似最近邻查询处理问题。这个问题不仅出现在个性化产品推荐中,而且还出现在KNN分类器的训练中。简单来说,广义加权曼哈顿距离的距离函数是这样一个加权l1距离函数:与其关联的权向量的元素被当作变量而非常数,它们的值可以是任意实数且随着每个查询一同给定。容易知道,广义加权曼哈顿距离不满足三角不等式,因此不是一个度量。本文首先证明了当数据点和查询点位于整个空间Rd时不存在解决这个问题的LSH方案和ALSH方案。然后,本文证明了当数据点和查询点都位于一个有界空间时仍然不存在解决这个问题的LSH方案。从而,本文在有界空间上提出了两个适合于广义加权曼哈顿距离的ALSH函数族并基于它们提出了两个ALSH方案——(dwl1,l2)-ALSH和(dwl1,θ)-ALSH。这是现有唯二的能在亚线性时间内解决这个问题的方法。本质上,这两个ALSH方案将这个问题归约到它的一个判定版本:在广义加权曼哈顿距离上的R1,R2-NN查询处理问题。通过变化参数R1和R2可以得到一个足够好的近似最近邻。本文用大量实验论证了这两个ALSH方案的性能。