红黑树原理[转载]
http://dev.firnow.com/course/6_system/linux/Linuxxl/20100531/206576.html
一个很好的NOSQL介绍
摘要：
日前国内没有一套比较完整的NoSQL数据库资料，有很多先驱整理发表了很多，但不是很系统。不材尝试着将各家的资料整合一下，并书写了一些自己的见解。
本书写了一些目前的NoSql的一些主要技术，算法和思想。同时列举了大量的现有的数据库实例。读完全篇，相信读者会对NoSQL数据库了解个大概。
另外我还准备开发一个开源内存数据库galaxydb.本书也是为这个数据库提供一些架构资料。
Hadoop增加trash回收站功能
功能介绍
空间的回收-文件的删除和恢复
用户或者应用删除某个文件，这个文件并没有立刻从HDFS中删除。相反，HDFS将这个文件重命名，并转移到/user/hadoop/.Trash/Current目录。当文件还在/user/hadoop/.Trash/Current目 录时，该文件可以被迅速地恢复。文件在/user/hadoop/.Trash/Current中保存的时间是可配置的，当超过这个时间，Namenode就会将该文件从namespace中删除。 文件的删除，也将释放关联该文件的数据块。注意到，在文件被用户删除和HDFS空闲空间的增加之间会有一个等待时间延迟。
当被删除的文件还保留在/user/hadoop/.Trash/Current目录中的时候，如果用户想恢复这个文件，可以检索浏览/user/hadoop/.Trash/Current目录并检索该文件。/user/hadoop/.Trash/Current目录仅仅保存被删除 文件的最近一次拷贝。/user/hadoop/.Trash/Current目录与其他文件目录没有什么不同，除了一点：HDFS在该目录上应用了一个特殊的策略来自动删除文件，目前的默认策略是 删除保留超过6小时的文件，这个策略以后会定义成可配置的接口。
配置
在每个节点(不仅仅是主节点)上添加配置 hadoop/conf/core-site.xml,
<!-- enable dfs trash -->
<property>
<name>fs.trash.interval</name>
<value>60</value>
<description>Number of minutes between trash checkpoints. If zero, the trash feature is disabled.
</description>
</property>
Google新闻个性化推荐的Bayes原理
论文[2010.IUI]Personalized News Recommendation Based on Click Behavior
1。预测用户对新闻文章的真实兴趣
用户对Category [tex]C_i[/tex]类文章的真实兴趣表示为用户点击属于Category [tex]C_i[/tex]的文章概率，其定义成
[tex]P(click|category=C_i)=\frac{P(category=C_i|click)P(click)}{P(category=C_i)}.......\(3\)[/tex]
其中
[tex] P(category=C_i|click)[/tex] 是用户点击的文章属于Category [tex] Ci[/tex] 的概率。
可以使用某个用户一段时间内用户的点击在所有Category上的分布来表示，即
[tex] P(category=C_i|click)= N_i/N[/tex] 。
P(click)是用户点击新闻文章的概率，不计新闻类别。
[tex] P(category=C_i)[/tex] 是一篇新闻文章属于Category [tex] C_i[/tex] 的先验概率,
可以使用一段时间内所有用户的点击分布来表示。
1.1 公式（3）的隐含意义
它 代表了用户对Category Ci的新闻文章有别于其他人的兴趣程度。当大量存在属于Category Ci（例如体育）的文章时，即当其他用户也大量阅读该热点类别文章时，被考查用户点击体育类的文章的次数很可能也越多，但这不一定不代表真正喜欢该类文章。相反，如果用户阅读了异常多的 体育文章，代表了该用户对体育类文章的真实兴趣。
2。结合过去不同时段的用户兴趣预测
公式（3）是某个特定时间段内对用户兴趣度的预测。文章认为可以结合过去更多时间段来更好地预测用户的兴趣，即如公式（4）所示，它假设是用户点击次数越多(即[tex]N^t[/tex]越大)，预测越准确（体现为权重,即[tex] N^t/\sum_{t}{N^t}[/tex] ,越大）。
[tex] interest(category=C_i)[/tex]
[tex] =\frac{\sum_{t}{(N^t*interest^t(category=C_i))}}{\sum_{t}{N^t}} ......\(4\)[/tex]
其中Nt为第t各时间段内的点击次数，
[tex] interest^t(category=C_i))[/tex] 是第t时间段内使用公式（3）计算的用户对类别category=Ci的兴趣度预测，
使用贝页斯公式得到
[tex] interest^t(category=C_i)=P^t(click|category=C_i) [/tex]
[tex] =\frac{P^t(category=C_i|click)P^t(click)}{P^t(category=C_i)}[/tex]
假设用户点击任何文章的先验概率不变，即Pt(click）=P(click).
则用户的兴趣预测可以进一步表示为公式（5）：
[tex] interest(category=C_i)=P^0(click|category=C_i)[/tex]
[tex] =\frac{P(click)* \sum_{t}{(\frac{N^t*P^t(category=C_i|click)}{P^t(category=Ci)}})}{\sum_{t}{N^t}}.......\(5\)[/tex]
3。预测用户的当前新闻兴趣
3.1 用户的新闻兴趣
可以分为两部分：用户的真实兴趣和大众用户的新闻趋势.
前者可以使用公式（5）计算， 后者可以使用当前很短时间内(例如最近几个小时内)大众用户在所有类别上的点击分布近似计算，即由
[tex] P^0(Category=C_i)[/tex]表示。
3.2 预测当前的兴趣
使用Bayes公式，可以得到
[tex] P^0(category=C_i|click) [/tex]
[tex] =\frac{P^0(click|category=C_i)P^0(category=C_i)}{p(click)} .......\(6\)[/tex]
其中
[tex] P^0(click|category=C_i)[/tex] 表示用户的真实兴趣，由公式（5）计算得到。
[tex] P^0(category=C_i)[/tex] 表示大众用户的新闻趋势。
把公式（5）代入（6），得到
[tex] P^0(category=C_i|click) = \frac{P^0(click|category=C_i)P^0(category=C_i)}{P(click)}[/tex]
[tex] = \frac{P(click)* \sum_{t}{\frac{ N^t*P^t(category=C_i|click)}{P^t(category=C_i)}}*P^0(category=C_i)}{\sum_{t}{(N^t)*P(click)}}[/tex]
[tex] = \frac{\sum_{t}{\frac{N^t*P^t(category=C_i|click)}{P^t(category=C_i)}}*P^0(category=C_i)}{\sum_{t}{N^t}} ......\(7\)[/tex]
注：原文用的是正比于符号，其实P(click)可以约除，直接使用等号就可以了。
3.3 平滑化(Smoothing)
当 用户没有点击某个Category的文章，并不代表他对给类的兴趣概率为0，就像那个经典的硬币正反面预测试验一样。 所以可以在公式（7）的基础上增加虚拟点击次数G（论文取10，其实取平均比较合理，论文没有透露怎么得到，应该和平均次数点击比较接近），最后得到平滑 后的预测公式：
[tex] P^0(category=C_i|click) [/tex]
[tex] = P^0(category=C_i)*\frac{\sum_{t}{\frac{N^t}{P^t(category=C_i)}+G}}{\sum_{t}{N^t}+G} ......\(8\)[/tex]
当[tex]N^t =0[/tex] 时，
[tex] P^0(category=C_i|click) = \frac{P^0(category=C_i) * G}{G} =P^0(category=C_i)[/tex] ， 即使用当前大众新闻兴趣趋势作为对用户当前对类别[tex]C_i[/tex]兴趣度的预测值。
读后感：
1. 直接使用用户点击某类新闻的概率表示用户对该类新闻的兴趣是使用了MLE估计，没有考虑一些热点新闻趋势，例如亚运会的召开，可能不准确。 Bayes也许更加合理.
2. 论文对时间特性建模教简单， 也许可以扩充一下很好地预测的用户长期兴趣变化：利用Bayes模型结合不同时间段的数据预测用户兴趣，以及发现新闻热点。
推荐阅读
