海量数据处理专题(一)——开篇

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。

本贴从解决这类问题的方法入手,开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。

  1. Bloom Filter
  2. Hash
  3. Bit-Map
  4. 堆(Heap)
  5. 双层桶划分
  6. 数据库索引
  7. 倒排索引(Inverted Index)
  8. 外排序
  9. Trie树
  10. MapReduce

在这些解决方案之上,再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。

Top K算法详细解析—百度面试

问题描述:

这是在网上找到的一道百度的面试题:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。


问题解析:

【分析】:要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。下面分别给出这两步的算法: 继续阅读

从lucene的文件结构看它的性能

Lucene是一个apache项目,完全使用java语言编写(废话,谁都知道apache主要是做java项目的,不过,已经有人对Lucene进行了迁移,比如CLucene),它提供了一个基本的索引文档后进行搜索的功能。目前版本是2.0,具体信息可以直接看http://lucene.apache.org/官方网站。同时,http://www.lucene.com.cn/about.htm提供了一个很不错的介绍(同时介绍了CLucene项目)。

本文不打算介绍它的使用,因为它的使用实在是过于简单,而且,太多的人写了关于它的使用方法。本文试图从一个更高的层次来分析一下lucene的文件结构及其性能,所以,需要读者已经对搜索引擎的工作原理有较深入的了解(推荐学习MIT的开放课程中的Information Extraction)。

本文的内容主要参考了http://lucene.apache.org/java/docs/fileformats.html,这是lucene的文件结构页面。 继续阅读