置顶文章

5.8k 字 5 分钟

# 动机 每个故事都会有一个开头，为什么我放着 cnblog 这样的傻瓜式的 blog 不用，非要自己折腾一个 blog。我想还是羡慕，每当看到 dalao 们各种或花式或简约的个人博客，就有自己创建一个 blog 的冲动，刚好周六花了一天时间把这个事情完成了。 # 基础环境搭建 # 安装 Nodejs sudo apt-get install nodejssudo apt-get install npmsudo npm config set registry https://registry.npm.taobao.orgsudo npm install -g n # 一定要升级，不然不兼容...

精选分类

琐事

14 篇文章

xlab

10 篇文章

AI

11 篇文章

数据库

13 篇文章

Go

13 篇文章

linux

13 篇文章

分布式

12 篇文章

文章列表

3k 字 3 分钟

vespa 公司也是一个造向量数据库的，并且受欢迎的程度和 milvus 不相上下？这篇博客主要是对 vespa 的 billion vector 的方案进行解析 Billion-scale vector search using hybrid HNSW-IF。我看完了第一遍后，第一想法是没准真能行，这个方案有点 spann 的意思，但是比 spann 更加精炼。 # Spann spann 这个算法我之前看过但是没有写博客，原因就是我觉得这玩意太啰嗦了，很难被工程化。我这里简单提一下这个算法： 层次 kmeans，进行质心的选取，质心用 SPTAG 建立索引。 非质心节点 assign...
253 字 1 分钟

趁着周末，久违的看看之前的 embedding 相关知识。 deepWalk 代码： def deepwalk_walk(self, walk_length, start_node): walk = [start_node] while len(walk) < walk_length: cur = walk[-1] cur_nbrs = list(self.G.neighbors(cur)) if len(cur_nbrs) > 0: walk.append(random.choice(cur_nbrs)) else: break return walk
1.7k 字 2 分钟

这个实验我只是做了 Uthread 。后面关于 pthread 部分并没有做，一来是懒，二来现在 Pthread 用的不多了，主要还是用 OpenMP 来进行多线程编程。 thread 数据结构： struct thread { char stack[STACK_SIZE]; /* the thread's stack */ int state; /* FREE, RUNNING, RUNNABLE */ char context[4096]; //for context save. 这里的 context 实际上是 char * 类型，也就是 4096...
88 字 1 分钟

用于记录自己在 ANNS 学习中使用到或者可能会使用到的数据集，他们的参数设置以及如何该存储。 # SIFT 数据集 官方地址：http://corpus-texmex.irisa.fr/
1.2k 字 1 分钟

# 线程的概念 说实话即使是现在我对线程也不能说完全懂了。进程时系统资源分配的最小单位，线程时 cpu 操作和调度的最小单位，本质是一组寄存器的状态，是操作系统对寄存器状态的抽象。XV6 每个进程只有一个页内存用于栈，也就是每个线程只对应一个线程。所以线程的切换等价于进程的切换。在 xv6 中所有的内核进程是共享内存的，而用户进程是完全内存隔离的。进程的切换和之前 trap 很类似，但是不同的是 trap 结束后返回的是同一个进程，而 switch 要切换到另一个进程。 内核进程和用户进程到底什么关系我之前也思考了很久，我想对 CPU 来说用户进程和内核进程或许差不多，它们都是相同的...
2k 字 2 分钟

# 代码阅读 把 Index 部分读完了，挺有意思的。做了个 Index 流程图： NSG 的代码 search 做了一些非常有意思的优化，但是它们的论文中却没有提到。 1）对于每个 point，把它的全精度向量和它的邻居存放在一起。这样可以尽可能保证局部性。 2）使用 _mm_prefetch 进行预取数据 _mm_prefetch(opt_graph_ + node_size * id, _MM_HINT_T0); //fetch 到所有缓存级别中_mm_prefetch 代码的作用其实很简单，就是把当前地址的数据 fetch 到特定的缓存级别中，fetch 的数据大小是 cache...
4.1k 字 4 分钟

# COW cow 就是 copy on write 的简称，当进程通过 fork 创建子进程时候，因为子进程和父进程的数据还有文件描述符等数据结构都是一样的，所以需要把父进程的所有数据拷贝到子进程，就必须申请和父进程相同的内存。但是比如说 sh 进程，它首先 fork 生成了一个子进程，子进程接着去执行 exec，exec 会清除进程数据然后 load 新的数据和指令。原来 fork 操作的数据拷贝就显得浪费了，所以就有了 cow 技术。 当 fork 的时候并不执行新的内存申请，而是页表项映射到 parent...
810 字 1 分钟

EFANNA 这篇文章我本来不是很想读，一来太老，二来性能也不是特别出色。但是看到 nsg 代码库使用 efanna 来初始化得到 KNN graph，所以还是捡起来看了看。 # 作者的动机 EFANNA 最大的创新点在于它同时使用了 KD-Tree 和 Graph 两种数据结构，KD-Tree 作为辅助数据结构可以更好地帮助 KNN graph 的构建和后续的查询。作者提出 EFANNA 的动机就是希望能同时使用到 tree 和 graph 两种数据结构的优点。这种辅助数据结构值得思考。 # 算法拆解 # 树构建算法 和传统的 KD-tree 最大的不同就是它的叶子结点中包含多个...