多媒体搜索引擎

1、多媒体搜索引擎,多媒体文档检索(2),2020年9月7日,Multimedia Search Engine,2,多媒体文档索引,相似性计算 为什么有这么多相似性计算方法？ 数学公式总是不符合人的感知 一个距离在某些情况下好，但在别的情况下不好 不同情况使用不同距离？ 如何确定该用哪个距离？ 如何解决？ 把特征空间变换到“感知均匀空间”,2020年9月7日,Multimedia Search Engine,3,多媒体文档索引,相似性计算 “感知均匀空间”（perceptually uniform） 欧氏距离与人的感知距离非常接近的空间,CIE XYZ CIE UGS(L*u*v*),CIE L*

2、a*b*,2020年9月7日,Multimedia Search Engine,4,多媒体文档索引,相似性计算 更高维、更复杂的特征 难以找到合适的变换 可变距离函数 距离函数可以有一些参数 例如：加权的绝对值距离，权为参数 参数通过相关反馈计算 各种相关反馈算法 各种回归算法,2020年9月7日,Multimedia Search Engine,5,多媒体文档索引,视觉信息快速索引 文字：倒排文件+索引结构 优点：存在精确匹配,华东师范大学,2020年9月7日,Multimedia Search Engine,6,多媒体文档索引,视觉信息快速索引 视觉信息：基本不存在精确匹配 必须实现相似性

3、查找 查找给定数量的最相似文档，或在某个距离阈值以内的所有文档 相似性索引,X1,X2,X3,Xq,2020年9月7日,Multimedia Search Engine,7,多媒体文档索引,相似性索引 支持范围查询和/或最近邻查询的索引,如何实现？,2020年9月7日,Multimedia Search Engine,8,多媒体文档索引,相似性索引 一维范围查询索引：B-树,查询：15,50,2020年9月7日,Multimedia Search Engine,9,多媒体文档索引,相似性索引 多维范围查询 高维空间具有非常特殊的性质，可能会导致在低维空间有效的算法在高维空间失效,克莱因瓶 Kl

4、ein bottle,莫比乌斯带 Mbius strip,2020年9月7日,Multimedia Search Engine,10,多媒体文档索引,相似性索引 多维范围查询 距离函数的影响 一维：L1=L2= 多维：均不相等 使用哪个距离函数？ 最容易实现： 效率最高 其它距离函数仍然可以实现,2020年9月7日,Multimedia Search Engine,11,多媒体文档索引,相似性索引 多维范围查询 K-d树, k-d-b树,2020年9月7日,Multimedia Search Engine,12,多媒体文档索引,相似性索引 多维范围查询 K-d树, k-d-b树,http:/d

5、/quadtree/index.html,2020年9月7日,Multimedia Search Engine,13,多媒体文档索引,相似性索引 多维范围查询 R-树及其变种,2020年9月7日,Multimedia Search Engine,14,多媒体文档索引,相似性索引 多维范围查询 更近似欧氏距离：SR-树 使用超球形节点 真的有效吗？ K-d(-b-), R-, SR-树的问题 性能与插入顺序有关 大量插入、输出等操作后性能可能下降 数据分割算法的通病 不是数据分割，使用空间分割,2020年9月7日,Multimedia Search Engi

6、ne,15,多媒体文档索引,相似性索引 多维范围查询 空间分割 空间等分成等大小的格子 量化 只保留有数据的格子 高维空间：稀疏 用简单索引结构索引格子,2020年9月7日,Multimedia Search Engine,16,多媒体文档索引,相似性索引 多维范围查询 空间分割 格量化(Lattice Quantization) 致密格：更接近球形，用较少格即可填满空间,Z2格,A2格,2020年9月7日,Multimedia Search Engine,17,多媒体文档索引,相似性索引 多维范围查询 空间分割 格索引 Hash: 查询时需要把邻接格全部查一遍，无论该格是否有数据 邻接格数量

7、越少效率越高,2020年9月7日,Multimedia Search Engine,18,多媒体文档索引,相似性索引 多维范围查询 空间分割 格索引 Trie：把每维当作一个符号，则可用Trie索引 Trie索引可以在每维上支持范围查询，所以无需遍历所有邻接格 可以处理任意高维数,2020年9月7日,Multimedia Search Engine,19,多媒体文档索引,相似性索引 多维范围查询 数据分割 可构造平衡数，层数浅，自适应数据分布 插入顺序影响性能，修改操作会显著降低性能 维数越高影响越大 空间分割 结构仅与所索引的数据有关 维数无关 不平衡，层数可能较大，量化步长难把握,2020

8、年9月7日,Multimedia Search Engine,20,多媒体文档索引,相似性索引 多维范围查询 各种结构可高效处理的维数 R-树、SR-树：10-15维 K-d(-b-)树：25维 空间分割：100维 更高的维数？ 线性扫描可能更快,2020年9月7日,Multimedia Search Engine,21,多媒体文档索引,相似性索引 最近邻查询 先用范围查询获得候选数据，然后线性扫描候选数据 利用范围查询的索引结构，配以优先级队列 计算节点和查询矢量的最小和最大距离，据此对节点进行排序处理 线性扫描 维数较高时的唯一选择,2020年9月7日,Multimedia Search Engine,22,多媒体文档检索,多媒体查询输入 关键字查询：文字输入 Google Image 无法输入视觉查询,2020年9月7日,Multimedia Search Engine,23,多媒体文档检索,多媒体查询输入 视觉查询：QBE 各种前期研究性演示系统 难以提交合适的查询样本 如果已经有精确的查询样本，则不再需要查询 如果样本不好，则查询效果不好 难以提交概念性查询 分类/随机浏览+QBE 找到合适样本的时间很长,2020年9月7日,Multimedia Search Engi