Search Engine

数据

• 结构化数据
  • 可用作数据库管理的数据
  • 可利用结构进行关系演算
  • json/html
• 非结构化数据
  • 文本
  • 图片
  • 音频

查询

• 数据库的查询
  • 精确
  • 快速
  • 功能多样
• 文档的查询
  • 模糊
  • 通用

布尔检索

用户的信息需求通过词和布尔代数表示

使用倒排索引

创建索引遇到的问题

1. 内存无法容纳所有的索引项
   • BSBI（Blocked sort-based Indexing）
   • 思想
     • 同时使用内存和磁盘
     • 把尽可能多的工作放到内存中完成
     • 对磁盘的访问尽量使用顺序读写
   • 方法
     • 将文档集分块，使得每块都能被内存容纳
     • 在内存中对每块的内容进行排序，并写回磁盘
     • 将各块的排序进行合并
2. 单个计算机无法容纳所有的索引项
   • Parittion by term
     • 造成单点压力过大
     • 相应更快
   • Partition by docs
     • 需要在每个节点中计算
     • 但更均衡
     • google使用
3. 文档在不断增加
   • 两个倒排索引
     • 位于磁盘的静态索引
     • 位于内存中的动态辅助索引
   • 可以规避动态增加索引对性能的影响

Indexing

对于人脸识别/图像查询/空间位置查询，可以转换为空间索引问题

KD Tree

Range Query

KNN Query

R Tree

• 可以自我平衡
• 允许空间划分重叠
• 可以实现不规则物体查询

Curse of dimensionality

在高维空间中，很多计算变得很困难或者没有意义

• 训练样本稀缺->过拟合
• 聚类无效
• 查询/索引无效
• 异常检测无效