1 背景

在实际工作中，我们经常涉及判断一个对象或者数据是否存在于内存或者数据库。往往大家会想到HashMap，但是这时候有一个问题,存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，可行性就差了。
另一方面，如果很多请求是在请求数据库根本不存在的数据,那么数据库就要频繁响应这种不必要的IO查询,如果再多一些,数据库大多数IO都在响应这种毫无意义的请求操作,为了解决这一个问题，过滤器由此诞生！

2 布隆过滤器

过滤原理：布隆过滤器(Bloom Filter)大概的思路就是，当你请求的信息来的时候，先检查一下你查询的数据我这有没有，有的话将请求压给数据库,没有的话直接返回。

1 引言

向量检索普遍应用于搜索、推荐、以及CV领域，往往候选集合两集都在千万甚至上亿规模。那么，速度很容易成为瓶颈，这时候就需要牺牲一定的精度来换取速度。于是诞生了许多ANN（近邻检索）算法，例如HNSW就是其中一种。但是，不同的ANN具有各自的优劣势，本文主要介绍faiss这一工业界普遍使用的向量检索框架。

Faiss的是由FaceBook的AI团队公开的项目Facebook AI Similarity Search，是针对大规模相似度检索问题开发的一个工具，使用C++编写，有python接口，对10亿量级的索引可以做到毫秒级检索的性能。

其核心思想：把候选向量集封装成一个index数据库，加速检索TopK相似向量的过程，尽量维持召回率，其中部分索引支持GPU构建。

1 背景

一致性哈希算法(Consistent Hashing)在分布式系统的应用还是十分广泛的。例如随着业务的扩展，流量的剧增，单体项目逐渐划分为分布式系统。对于经常使用的数据，我们可以使用Redis作为缓存机制，减少数据层的压力。因此，重构后的系统架构如下图所示：

1 引言

在向量检索领域，HNSW算法算是有比较重要的一席之地，很多地方都会用到，那么本文主要是对其具体构建的细节逻辑和背后的思想进行一个阐述和介绍。

Hierarchical Navigable Small World Graphs (HNSW) 是Yury A. Malkov提出的一种基于图索引的方法，它是Yury A. Malkov在他本人之前工作NSW上一种改进。通过采用层状结构，将边按特征半径进行分层，使每个顶点在所有层中平均度数变为常数，从而将 NSW 的计算复杂度由多重对数(Polylogarithmic)复杂度降到了对数(logarithmic)复杂度。

2 朴素思想

这里我们以一个小的场景为例来开始，假设我们现在有13个2维数据向量，我们把这些向量放在了一个平面直角坐标系内，隐去坐标系刻度，它们的位置关系如下图所示。

1 基础知识

1.1 背景

在深度学习大兴的时代，embeding无处不在，不论是在搜索推荐领域还是 cv 领域亦或 nlp 领域。俗话说得好，万物皆可embeding，那么对于 embeding 化后的对象我们在做 topk 检索/召回的时候怎么提效呢？毕竟候选集往往都是在千万级或者亿级的时候，计算量是相当大的。这时候，向量检索算法就发挥了作用。

向量检索一般可以分为两个方向:

• 一种是精确化检索，需要遍历每个样本，计算量往往很大，基本上被淘汰了。
• 另一种就是近似检索，学术上对应的专有名词叫 Approximate Nearest Neighbor Search (ANNS)，即近似最近邻搜索。

为什么是近似，而不是我们想要的精确？

这就是精度与时间、算力资源的折中，采用了牺牲精度换取时间和空间的方式，从海量的样本中实时获取跟查询最相似的样本。

1 位运算简介

• & 与运算 两个位都是 1 时，结果才为 1，否则为 0，如：
  10011&11001=10001

• | 或运算 两个位都是 0 时，结果才为 0，否则为 1，如 10011 | 11001 = 11011

• ^ 异或运算，两个位相同则为 0，不同则为 1，如 10011 ^ 11001 = 01010

• ~ 取反运算，0 则变为 1，1 则变为 0，如~ 10011 = 01100

• << 左移运算，向左进行移位操作，高位丢弃，低位补 0，如

-

1 背景

在企业的深度学习项目中，Sparse稀疏矩阵这个词想必大家都不陌生。在模型的矩阵计算中，往往会遇到矩阵较为庞大且非零元素较少。由其是现在深度学习中embedding大行其道，稀疏矩阵成为必不可少的基建。而这种情况下，如果依然使用dense的矩阵进行存储和计算将是极其低效且耗费资源的。Sparse稀疏矩阵就称为了救命稻草。在拜读多篇优秀博客后，这里做一些自己的汇总和填补。

2 稀疏矩阵

2.1 定义

原始论文：Deep & Cross Network for Ad Click Predictions

深度和交叉网络的广告点击预测

摘要

特征工程已经成为许多预测模型成功的关键。然而，这个过程是不平常的并且经常会要手动特征工程或者穷举搜索。DNNs能够自动地学习特征交叉项；然而，它们都是隐式地生成所有交叉项，并且学习所有类型的交叉特征不一定有效。在本文中，我们提出深度和交叉网络(DCN)，它保持了深度模型的优势，并且又超越了这，它是一种在学习某种边界程度特征交叉项中更为有效的新奇网络。此外，DCN显示地在每一层应用特征交叉，不要求做人工程特征工程，同时也只是给DNN模型增加了一些可以忽略不计的复杂度。我们的实验结果已经证明它在CTR预测数据集和密集的分类数据集上，相对于其他高级模型在模型准确性和记忆方法上都具有优越性。

1 介绍

点击率（CTR）预测是一个大规模的问题，它对数十亿美元的在线广告业来说至关重要。在广告业中，广告商会想发布商付费以在发布商的网站上展示他们的广告。一个普遍的付费模式是平均点击成本（CPC）模型，即广告商仅在点击发生的时候才会付费。因此，出版商的收入很大程度上依赖于能够准确预测CTR。

显著性计算（uv based）

这里以实验目标为提升CR（Conversion Rate）为例说明

名词解释

显著性： 显著：新版和老版的CR有明显差异，不显著: 新版和老版没有明显差异。
上升幅度：(新版CR-老版CR)/老版CR
功效: 一般功效（即power值）达到0.8, 我们认为样本量即实验UV充足，可下结论。

1. 前言

RF,GBDT,XGBoost,lightGBM都属于集成学习（Ensemble Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善基本学习器的泛化能力和鲁棒性。

根据基本学习器的生成方式，目前的集成学习方法大致分为两大类：即基本学习器之间存在强依赖关系、必须串行生成的序列化方法；以及基本学习器间不存在强依赖关系、可同时生成的并行化方法。前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。

本文主要从下面四个广泛讨论和使用的方法进行了对比分析总结：
RF（随机森林）,GBDT（梯度提升决策树）,XGBoost,lightGBM