8、不确定时空数据相似性搜索与聚类排列列表技术解析

不确定时空数据相似性搜索与聚类排列列表技术解析

1. 引言

在现代应用中，如模式识别和多媒体检索，相似性检索系统至关重要，用于在查询时找到相关对象。这类搜索问题常涉及在大型数据库中对两个对象进行昂贵的比较。问题可映射到度量空间 $(X, d)$，其中度量 $d$ 比较宇宙 $X$ 中的对象，揭示对象间的接近程度，且需满足正定性 $d(x, y) ≥ 0$、对称性 $d(x, y) = d(y, x)$ 和三角不等式 $d(x, y) ≤ d(x, z) + d(z, y)$。给定数据集 $U ⊂ X$，查询基本可分为范围查询和 $k$ 近邻查询。

2. 相关技术回顾

• 精确与近似搜索方法 ：相似性搜索问题可通过精确或近似方式解决。精确搜索旨在检索满足相似性查询的所有对象，主要算法家族包括基于枢轴的索引和基于紧凑分区的索引；近似搜索则是为了加快查询速度，接受错过一些相关元素，已有一些非精确方法。
• 列表聚类（List of Clusters，LC） ：
  • 构建方式 ：使用 $O(n)$ 空间，在高维空间有出色性能，但构建需要 $O(n^2)$ 次距离评估。首先从数据库中选择一个中心 $c$ 并给定桶大小 $b$，$c$ 选择其 $b$ 个最接近的元素组成集合 $I$，记录 $c$ 到 $I$ 中最远邻居的距离 $crc$，形成聚类 $(c, I, crc)$，递归处理剩余非聚类对象。
  • 查询方式 ：将查询对象与所有聚类中心比较，若聚类中心到