2013 年文章归档
共 4 篇文章
最短路径Mapreduce实现
¢A map task receives lKey: node n lValue: D (distance from start); points-to (list of nodes reachable from n) ¢p \in points-to: emit (p, D+1) ¢The reduce task gathers possible distances to a given p and selects the minimum one input文件格式为: <node id><distance to the start node><[node id it can reach]…
2013-01-17 15:10 · big data
Apriori 关联规则算法
关联项的求解问题非常常见,最典型的例子如“牛奶面包”问题。然而常常需要通过对具体数据的分析来获悉一些不是很明显的关联对。例如我们熟知的“啤酒尿布”关联。如果不是事先听说过这两者之间微妙的关联,我想很多人是很难想像到其中的关联的。相信还有许多微妙的关联关系只有通过对具体数据的分析才能被发现。 求解关联pair或者更大的关联集合的最朴素的想法就是列举并统计所有可能的pair的出现频数,判断其是否足够大。但是组合结果通常过大,而使得计算量过大。可以发现#{K-子集合}>...>#{triple}>#{pair},其中K>N/2,N表示所有物品的个数。 “Mining of massive data…
2013-01-16 21:03 · 大数据
FlajoletMartin
FlajoletMartin 算法 原始算法: "Mining Massive dataset"中介绍的改进过程: 3-4. 构造m组hash函数,每组n个函数。对每个字符计算hash值,h11,...,h1n, h21,...,h2n,..., hm1,...,hmn 4. for each hij, get its 0-tailing length: <!--WizRtf2Html Charset=0 -->private int rho(long v) { int rho = 0; for (int i = 0; i < m_bitmapSize; i++) { // size of …
2013-01-15 13:39
bloom filter
Bloom Filter m=|bit array|, n=|S|, k=# of hash functions. false positive= Given m and n, will results the minimum false positive. k=-log2 eps. y=D(expression((1-exp(c*x))^x),'x') > y (1 - exp(c * x))^x * log((1 - exp(c * x))) - (1 - exp(c * x))^(x - 1) * (x * (exp(c * x) * c)) let y=0, we get k let…
2013-01-15 13:02