« 乱読日記[68] | トップページ | [弁理士試験]判例案内(2) »

2007年11月15日 (木)

ノースイースタン大学の特許と google のはなし

やっぱり更新が遅れちゃいました。スミマセン。
予定通り、google が訴えられているという、米国特許、5694593に関する話題をお送りしたいと思います。

▽ もっとも google 、わりと泰然自若としているようで、訴訟に動じない構えを見せている。さて。

■ google の窓
 いまや殆どの web browser についている google 窓。皆さまはここへ毎日、何語の検索キーワードを入れておられるだろうか。
 私などは google を使わない日が年に何日あるか、という勢いだと思うのだけど。

 この窓に入力された検索キーワードは、ほとんどそのまま google のシステムへの検索命令(クエリ:query)の一部となる。「ほとんど」と言ったのは、"a" や "the" のようなどのドキュメントにも現れる語だとかを除く処理はしているらしいので、そういった場合はそのままクエリの一部とはならないからだ。

 さて、今回訴訟の原因となっている特許権であるが、既にご案内の通り、USP5694593 である。出願人はノースイースタン大学、出願日は 1994 年10月5日。技術的には分散データベースに関するもので、その第1クレイムは、次の通り。

□ 1. A method for information retrieval using fuzzy queries in a non-relational, distributed database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of:
randomly selecting a first one of said plurality of home nodes;
fragmenting, by said selected home node, a query from a user into a plurality of query fragments;
hashing, by said selected home node, each said query fragment of said plurality of query fragments, said hashed query fragment having a first portion and a second portion;
transmitting, by said selected home node, each said hashed query fragment of said plurality of query fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed query fragment;
using, by said query node, said second portion of said respective hashed query fragment to access data according to a local hash table located on said query node; and
returning, by each said query node accessing data according to said respective hashed query fragment, an object identifier corresponding to said accessed data to said selected home node.

 例により、私が仮に訳してみる。

□ 1. 互いにネットワークで接続された、複数のホーム・ノードと、複数のクエリ・ノードとを有し、リレーショナルでない、分散データベースシステムにおける曖昧なクエリを用いて情報を取得する方法であって、
 第1の前記複数のホーム・ノードの一つをランダムに選択するステップと、
 前記選択されたホーム・ノードによって、ユーザから受けたクエリを、複数のクエリ・フラグメントに分割するステップと、
 前記選択されたホーム・ノードによって、前記クエリ・フラグメントの各々をハッシュして、当該ハッシュされたクエリ・フラグメントが第1部分と第2部分とを有するようにするステップと、
 前記選択されたホーム・ノードによって、前記ハッシュされたクエリ・フラグメントを、前記複数のクエリ・ノードのうち前記ハッシュされたクエリ・フラグメントの第1部分によって特定されるクエリ・ノードの一つへ送信するステップと、
 前記クエリ・ノードによって、対応する、ハッシュされたクエリ・フラグメントの第2部分を用い、前記クエリ・ノードのローカル・ハッシュ・テーブルに従って、データにアクセスするステップと、
 対応する、ハッシュされたクエリ・フラグメントに基づいてデータにアクセスしたクエリ・ノードの各々から、前記アクセスしたデータに対応するオブジェクト識別子を、前記選択されたホーム・ノードへ返送するステップと、
 を有する方法。

 今回のクレイムは、わりかし分かりやすい(私個人としてまともに(仕事上の)専門分野に近いからかも知れない)。ただ詳しくは、明細書を検討しないとわからないこともある。いま明細書を検討している余裕がないのだけど、どうやらクエリ・データのハッシュ値を生成し、その一部でクエリを処理するコンピュータを決め、残りの一部を用いて、当該クエリを処理すると決めたコンピュータ内部でクエリ処理を行うということか。

 ハッシュ値について馴染のない方のために、もうちょっとかみ砕いて言うと、特定のデータに対して殆ど一意の数値を割り当てるハッシュ値というものが知られているのである。実は、特許出願の作業でも使われている
 出願の内容についてのハッシュ値を出願端末側で演算して取っておく。特許庁サーバでは出願の内容を受け取ると、そのハッシュ値を端末と同じようにして演算し、当該演算の結果を端末へ送り返す。端末側では、取っておいたハッシュ値と、特許庁サーバから送り返されたハッシュ値とを比較する。一致していれば、こちらにある内容と同じ内容が送られたと判断する。一致していない場合は、何らかの理由で特許庁で受け入れたものが、こちらと違うということになる。内容の一文字、図の1ピクセルでも違えば異なるハッシュ値となるような関数なので、こういう確認に使える、というわけである。
 ここではハッシュ値のそういう擬一意性(ちょっとでも違えば違う値になる)を利用して、そのハッシュ値の一部を使って検索を行うデータベースを選択しようとしているみたい。

■ google 技術
 一方の google 。その原形となる BackRub がスタンフォード大学で立ち上がったのは 1996 年の1月だという。本件特許出願の後のことになる。開発者のラリー・ページらは、その2年後、SUN microsystems のアンディ・ベクトルシャイムから10万ドルの出資を得て google を創業している。
 こうやっていきなり出資金が(著名人から)出てくるあたりが米国ベンチャーの羨ましいところだ。弊所も出資金でも募ってみるか---おっと、脱線した。話を元へ戻す。

 google を特徴づけているのは、秀逸な PageRank(商標)技術である。この技術については、京都大学の馬場肇先生のページに詳しい解説がある(http://www.kusastro.kyoto-u.ac.jp/~baba/)ので、ここで私の拙い解説は控えることにする。
 しかし今回、侵害と目されているのはその技術のことではない。google でのクエリ処理というもっと基本的な部分での話だ。
 ラリー・ページらの論文である、"The Anatomy of a Large-Scale Hypertextual Web Search Engine(http://infolab.stanford.edu/pub/papers/google.pdf)" の図4、「google クエリ評価法」を参照すると、google のクエリ処理は次のように解説されている。

1. Parse the query.
2. Convert words into wordIDs.
3. Seek to the start of the doclist in the short barrel for every word.
4. Scan through the doclists until there is a document that matches all the search terms.
5. Compute the rank of that document for the query.
6. If we are in the short barrels and at the end of any doclist, seek to the start of the doclist in the full barrel for every word and go to step 4.
7. If we are not at the end of any doclist go to step 4.
Sort the documents that have matched by rank and return the top k.

これも私訳してみる。

1.クエリを解析
2.語をワード識別子へ変換
3.各語について、ショート・バレル中の doclist の先頭を探索
4.doclist を走査して、検索語のすべてに一致するドキュメントを検索
5.当該クエリに対するドキュメントのランクを算出
6.もし、ショート・バレル中にいて、いずれかの doclist の末尾に至っていれば、全ての語について全体バレル中の doclist の先頭を探索して、ステップ4へ移行。
7.もし、どの doclist の末尾に至っていなければ、ステップ4へ移行
8.マッチするドキュメントをランク順にソートし、その先頭kを返す。

たぶん、最後の "Sort the documents..." の行は、ステップ8とするのが正しいと思うので、直してみた。えーと、それで耳慣れない単語のうち、doclist というのは、どうやらドキュメント識別子(web ページごとに固有の識別子)と、そこでの出現単語とを関連づけたテーブルであると解釈できるとして、残る「ショート・バレル」、「フル(全体)バレル」という単語が曲者だ。
 同論文("The Anatomy of a Large-Scale Hypertextual Web Search Engine")の、図1を参照すると、インデックスのつけられたデータが多数のバレル(barrels)に分散して格納されているかのような図が示されている。
 説明文はあっさりとしていて、これが分散データベースなのかどうかまではわからないし(多分そうだろうけど)、まして分散方式としてハッシュ値を使っているかどうかまでは判らない
 google のシステムが、分散データベース技術にいわゆる、水平分割方式が採用されていることはまぁ有り得べきことであるとして、そのデータ振り分けがハッシュ値をベースにして行われているのかどうか。さらに、本件特許ではクエリ・ノードにおいてハッシュの第2部分が使われているというが、上記論文の解説を真に受けると、google では検索語の全体を使っている可能性もあり、そのあたりの相違点判断も可能性としてあり得る。
 さらに今回ノースイースタン大学らが訴訟に踏み切ったのは、google のやり方について何らかの情報を得てのことであろうが、分散処理の一般的技術に関していえば、本件特許に先行する技術がいくらでもあるのであり、うまい訴訟対応をしていかないと、この特許権だけではなかなか勝ち目は難しいのじゃないかと思うけれども。今後の展開がちょっと楽しみである。

■なお、14日に投稿するべき記事がこの時間になってしまったので、本来15日付けの記事については、また15日の午後にでもしようとおもいます。軽めのネタを狙っております

|

« 乱読日記[68] | トップページ | [弁理士試験]判例案内(2) »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: ノースイースタン大学の特許と google のはなし:

» ホームページ制作個人 [ホームページ制作個人]
ホームページ制作個人 [続きを読む]

受信: 2007年11月18日 (日) 21時53分

« 乱読日記[68] | トップページ | [弁理士試験]判例案内(2) »