Probabilistic Nearest-Neighbor Query on Uncertain Objects
Probabilistic Nearest-Neighbor Query on Uncertain Objects
复制标题
DOI：
10.1007/978-3-540-71703-4_30
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
H. Kriegel;Peter Kunath;M. Renz
中科院分区：
文献类型：
--
作者：
H. Kriegel;Peter Kunath;M. Renz
最近邻查询是常用特征数据库的重要查询类型。在许多不同的应用领域，例如传感器数据库、基于位置的服务或人脸识别系统，物体之间的距离必须基于模糊和不确定的数据来计算。一种成功的方法是通过概率密度函数来表示两个不确定对象之间的距离，概率密度函数为每个可能的距离值分配一个概率值。通过将完整的概率距离函数作为一个整体直接集成到查询算法中，可以利用这些函数提供的完整信息。这种概率查询算法的结果由包含结果对象和指示该对象满足查询谓词的可能性的概率值的元组组成。在本文中，我们介绍了一种处理概率最近邻查询的有效策略，因为这些概率值的计算非常昂贵。在详细的实验评估中，我们展示了概率查询方法的好处。实验表明，我们可以以相当低的计算成本获得高质量的查询结果。
Nearest-neighbor queries are an important query type for commonly used feature databases. In many different application areas, e.g. sensor databases, location based services or face recognition systems, distances between objects have to be computed based on vague and uncertain data. A successful approach is to express the distance between two uncertain objects by probability density functions which assign a probability value to each possible distance value. By integrating the complete probabilistic distance function as a whole directly into the query algorithm, the full information provided by these functions is exploited. The result of such a probabilistic query algorithm consists of tuples containing the result object and a probability value indicating the likelihood that the object satisfies t he query predicate. In this paper we introduce an efficient strategy for processing probabilistic nearest-neighbor queries, as the computation of these probability values is very expensive. In a detailed experimental evaluation, we demonstrate the benefits of our probabilistic query approach. The experiments show that we can achieve high quality query results with rather low computational cost.