answersy.com Blog

基础设施构架

基础设施要好用、够用。这里着重要考虑的是总的数据量，进出流量以及增长率。换句话说，数据仓库最终要装多少数据，到底会承受怎样的输入输出压力，随着时间推移总量和输入输出的压力如何变化。通常用现成的Oracle RAC，按照OLAP来配置；也可以采用免费DBMS加中间件的方式组成系统；甚至连整个存储系统都自行构建，例如采用Hadoop。显然，Oracle搭建起来比较快，但成本相对高；后者需要相当的人力资源投入，但可以掌握实际技术，灵活性高。

原始数据清洗

主要是过滤噪音、打标签、补足缺失部分

数据导入

分布、存储、索引

数据归总

按照商业或者分析的需求计算统计值

数据仓库设计

明确商务流程

必须对具体的商务活动本身要有深入的了解和认知。

确认商务流程中的各元素和维度

理解系统中人、物、事件、活动以及之间的逻辑关系。确定如何用各种数据参数来描述每个元素和事件活动。好的数据仓库应该有一整套底层维度设计，上面的应用要尽可能地重复使用这些基本的维度定义。

确定商务流程的粒度

在怎样的宏观或者微观水平上描述这个商业流程

确定定量的事实

例如，营业额就是零售业的度量。

Let's talk about "real time." When we say real time, we mean to be able to serve new contents within several minutes or even less time after they are available.

In any database, search and data manipulation are a pair of conflicts. If one optimizes for search, insertion, updating and deletion will suffer, vise verse. Unless, the dataset is relatively small, it is very difficult to achieve good performance on both.

General web search serves billions of documents, therefore, it takes long to fully build the index; as a result, it is not feasible to serve "new" contents very quickly. To be able to maintain certain level of freshness, major web search engines often adopt a separated pipeline to handle a few frequently updated contents. This fastlane has much less documents and can be built several times a day. When search is conducted, proxy will blend results from main index with the ones from the fastlane.

However, for some transaction-oriented web sites, rebuilding indexed several times a day is still not acceptable. One might have heard this saying, "today's disk is yesterday's tape, today's RAM is yesterday's disk." We should really take advantage of new machine's large memory. If we can move the fastlane into memory, and stop worrying about the mechanical disk access, we shall have a better chance to achieve "real time" serving.

The key point is divide and conquer: handle different freshness requirements with a number of pipelines of different priority. We need a good algorithm to do the "divide" and a good strategy to merge. In the meanwhile, we want to take advantage of new hardware as well!

Everybody agrees that relevance is vital to information retrieval or a search engine. Hence, I would like to talk a little more on ranking here.

First of all, as an old Chinese saying says, “a brilliant housewife cannot prepare wonderful dinner without rice.” Content quality is absolutely a precondition to search relevance. The whole infrastructure must guarantee that statistically important high-quality documents are so arranged that they will be selected as the “rice” for the housewife to cook. :-)

Second, the housewife actually runs a team to do the job. Ranking function is a set of logics and models. (See figure 1 below)

If the set of all the possible queries is denoted as input space Q, usually, we need to slice Q into smaller sub-regions to handle them separately. Many have dreamed of having one single unified ranking module to handle all the queries, but soon or later, this will hit some bottleneck. The idea is to have a number of individual ranking modules which performance well in a sub-region of Q. The branching logic can be based on length, language, intention or other classification of the queries or user profiles.

Third, we need a merging logic to combine the outputs of different ranking modules. Sometimes we trust one ranking module so much that others won’t even be called. Sometimes we might want to run more than one ranking modules in parallel and blend their results. In general, the merging logic should be based upon the following heuristic: if ranking module i performs better than module j in a sub-domain of Q, for a given query q in this sub-domain, i’s output should have higher weight than j’s. This is to trust the experts’ domain knowledge. The final weights also need to be tuned either manually or by some statistical modeling procedure.

To summarize, content quality + committee of special ranking modules = solution.

A lot of web services talk about Personalization.

As we may know, matching contents with audiences' intention is the key value of any publishing site, especially web search.

Usually, web services use aggregated features to improve relevance. For example, Google's famous PageRank: if a lot of pages link to this one, it is important! Another example would be recommended posts on a BBS site or Blog RSS engagement service like feedburner.com. Usually, they are based on popularity: if a lot of people click on this, it is good; if a lot of people subscribe to this, it is cool!
In general, this aggregation approach will achieve "much-better-than-random-pick" results. However, for a given individual, this is NOT good enough: a lot of people like ipod, but I prefer zune. Hence, when searching for "mp3 player," I might want to see more zune results ;-)

The difficulty of personalization lies in two major factors: (1) huge possible combinations of different profiles (2) how to get and store users' profile.
So, how to address this issue?

I have to say, there is no out-of-package solution out there yet. But, the more you address this, the better position you are in the future competition! Hence, if you want to provide a serious web service to general audience, you want to think about personalization from the beginning of the system design.

Here are some preliminary thinkings:

(1) keep track of all the links a user clicks on your site

(2) have all the links classified based on some criteria
(3) aggregate over user, links classes, and time-frame, and keep the summarized data in user's cookie

(4) deliver contents using the summarized data as parameters

For example, if a search engine finds a user (cookie) clicks commercial links very often recently, it should really start to push more ads to him. If a user clicks sports links very often, showing sport-related ads will achieve better results.

Remember, Personalization is not about being perfect, it is about achieving competitive advance!

Let's consider ranking.

What is ranking? In information retrieval, ranking is to order "matched documents."

We need to define matching first. If user queries "mp3," can "ipod" in a document be considered as matched? In general, I feel so. But usually, most search engines will be very conservative in doing so.

Besides whether query terms match the document or not, we also need to consider where the matchings happen. They can happen at the title, header or body section, sometimes at anchor text or other meta information like "url" or "tag" sections. Of course, matching proximity is another important consideration. These are all standard information retrieval issues.

In my opinion, understanding query intention is the key to improve ranking. There is NO "general ranking algorithm" for all type of queries and it does not make sense to try to build one. As a result, overall, a good ranking function should be the combination of heuristic logics with data-trained logics. Namely, we can slice data into different categories to train special ranking models for each category, while at the same time develop algorithms to make decision on how to pick ranking modules for a given query.

From example, for English query, if the url string or host name matches the query terms, it can be a very strong indicator of "good matching", this may not be applicable at all for Asian languages. So we need a language detection module before applying ranking modules.

Query -> Language Detection -> English Logic, Chinese Logic ...
The key is how many manually maintained logic forks we can keep so that the data trained ranking module at the leaf can perform well enough. We also need to balance the cost of maintaining a list of such modules with the performance gain by going specialty.

Search is so nature when one is facing oceans of information.
Google dominates internet search for the following reasons

1. A well-recognized internet search service featuring
1. Good coverage on most of the web contents
2. Good user intention understanding and high query-results relevance
3. Freshness, discovery of new contents and fast indexing speed
4. High availability, and fast serving speed
5. Relatively stable and improving presentation of the results
2. Keeping close track of search users' behaviors to deliver relevancy online Ads
3. Share profit with other publishers/sites

In this document, I am going to present another approach to deliver good search experience.

There are too many different aspects in search. That is why it is so hard to start up a real functioning search service on the internet or even for a large corporation site.

As we all know, a search service include the following components:

1. a crawler and document repository
2. some content analyzer, to extract linkage information and other meta data from the crawled documents
3. an indexer to build keyword index for the documents
4. the search engine clusters to serve the indexed data
5. modern search engines always have a proxy layer to do load-balancing, caching and aggregation
6. A ranking module to order the matching results
7. frontend usually instruments some tracking code to monitor end user behaviors, which potentially will feedback to content system

As of now, the major challenge of build such a service lies in the following aspects:

1. scalability
2. meta information extraction in nonstructural data
3. user intention understanding, ranking
4. spam filtering
   
5. content updating

I will try to discuss these issues in this series :-)
References:
1. http://en.wikipedia.org/wiki/Index_(search_engine)