小朱读稿件之Hot Storage12[workshop]

小朱读文章之Hot Storage12[workshop]
Onyx: APrototype Phase Change Memory Storage Array

这篇文章用PCM和FPGA做的控制器做了一个原型系统，为什么叫（a prototype high-performance solid-statedrive based on first-generation phase-change memory）

最后与SSD的性能做了比较，说明性能优势。 

本文提出了一个新的数据结构，可以scaleoutside of main memory

有趣的数据结构：以错误率换取存储空间

Bloom Filter概念和原理

http://blog.csdn.net/jiaomeng/article/details/1495500

Bloom Filter概念和原理

焦萌 2007年1月27日

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。   

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive

然而这篇文章的大意可以从下面的图中很容易的看出。

没看懂啊没看懂