Silicon Soul -広告技術と広告のblog-

　昔のブックマークを整理していたところ、2005年にWebKDDというカンファレンスをブックマークしていたのを発見しました。WebKDDは、Webの知識発見(Knowledge Discovery on the Web) 関連のトピックを扱う会議で2008年で10周年になるようです。

　KDD2008で発表されている論文のタイトルをみていたところ、URLの標準化に関する発表がされているのを見つけました。（KDD2008のサイトではPDFがなかったので、タイトル、著者名でSearchしてPDFにたどり着きました。）
　

　
Anirban Dasgupta Ravi Kumar Amit Sasturkar, “De-duping URLs via Rewrite Rules”, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp.186-194,2008
　
ABSTRACT
A large fraction of the URLs on the web contain duplicate (or near-duplicate) content. De-duping URLs is an extremely important problem for search engines, since all the principal functions of a search engine, including crawl-ing, indexing, ranking, and presentation, are adversely impacted by the presence of duplicate URLs. raditionally, the de-duping problem has been addressed by fetching and examining the content of the URL; our approach here is different. Given a set of URLs partitioned into equivalence classes based on the content (URLs in the same equivalence class have similar content), we address the problem of mining this set and learning URL rewrite rules that transform all URLs of an equivalence class to the same canonical form. These rewrite rules can then be applied to eliminate duplicates among URLs that are encountered for the ¯rst time during crawling, even without fetching their content. In order to express such transformation rules, we propose a simple framework that is general enough to capture the most common URL rewrite patterns occurring on the web; in particular, it encapsulates the DUST (Different URLs with similar text) framework . We provide an effcient algorithm for mining and learning URL rewrite rules and show that under mild assumptions, it is complete, i.e., our algorithm learns every URL rewrite rule that is correct, for an appropriate notion of correctness. We demonstrate the expressiveness of our framework and the effectiveness of our algorithm byperforming a variety of extensive large-scale experiments.

　
　
　　
　URLの標準化(URL Normalizaion, de-duping)は、SearchEngine等に関連するトピックは、同一のコンテンツを指し示す複数のURLをどうやって纏め上げるのかという内容です。

たとえば、冗長構成のため、サーバが複数に分かれているケースでは、

　http://www-1.ibm.com
　http://www-2.ibm.com

と、異なるURLで同一のコンテンツを保持するケースがあります。

また、CGI等のパラメータの場合では

　http://example.com/show.php?a=10&b=20
　http://example.com/show.php?b=20&a=10

パラメータの順番が異なっているが実質同じ意味を持つケースがあります。

　このように表現は異なるが内容は同一というURLが世の中には非常に多くあるため、SearchEngineのように大量のURLのコンテンツを収集・解析するシステムでは、パフォーマンス上重要な議題になります。

この論文以前にも、URLの標準化に関しての議論は存在しており、以前の方法は主にページコンテンツの同一性を評価し、URLの標準化に取り組むという内容だったのに対して、著者らのアプローチは、

　1. DUST(Duplicate URL as Similar Text)を含むURL標準化のためのURL置換ルールを提案
　2. 類似したURLの形式から、URL置換ルールを導く学習アルゴリズムを提案
　3. 大量の実URLデータを使った計算機実験を通して有効性を検証

というもので、検証の結果DUSTルールでは20%のURL標準化が可能だったのに対して、著者らは60%のURL標準化を達成したとあります。
　　
　アルゴリズムの詳細については読み終わったらまとめたいと思います。
　
　
著者はYahoo! Researchの人のようですが、このような研究もBingに切替わると無くなってゆくのでしょうかね。。。