(57)【要約】データ保存およびデータ検索のためのデバイスおよび方法を開示する。このデバイスは、目標データを保存するように構成される少なくとも１つの磁気記憶媒体と、少なくとも１つの磁気記憶媒体に結合され、そこから目標データの連続的ストリームを読み取るように構成されるＦＰＧＡを含み、検索および検索データのタイプに合致するようにテンプレートまたはその他の所望の方法を用いて構成される、少なくとも１つの再構成可能論理デバイスとを含む。再構成可能論理デバイスは、データキーの形式をとる少なくとも１つの検索照会を受信し、データキーと少なくとも１つの磁気記憶媒体から読み取られる目標データの間でマッチを判定するように構成される。このデバイスおよび方法は、目標データに関して、正確マッチ検索、近似的マッチ検索、シーケンスマッチ検索、画像マッチ検索、データ削減検索を始めとする様々な検索を実行することができるが、これらに限定されるものではない。このデバイスおよび方法は、スタンドアロン型コンピュータの一部として提供することができ、ネットワーク接続記憶装置内で実施することができ、またはコンピュータＬＡＮまたはＷＡＮの一部として提供することができる。
2005527043.tif 000002
【特許請求の範囲】
【請求項１】
磁気データ記憶装置とＣＰＵの間を接続するデータ検索デバイスであって、前記磁気データ記憶装置に保存されたデータの検索を実行するために再構成可能であるＦＰＧＡを含むデータ検索デバイス。
【請求項２】
前記ＣＰＵは、前記ＦＰＧＡにテンプレートを送信して、それを再構成するように構成される請求項１に記載のデータ検索デバイス。
【請求項３】
前記ＣＰＵは、検索を実行する際、データ記憶装置から読み取られるデータとマッチングさせるため、前記ＦＰＧＡにキーを送信するように構成される請求項２に記載のデータ検索デバイス。
【請求項４】
データ記憶装置とＦＰＧＡの間に接続されるデータシフトレジスタをさらに含み、データ記憶装置は、データ記憶装置から読み取られる目標データを保存するように構成される請求項３に記載のデータ検索デバイス。
【請求項５】
前記デバイスは、ＦＰＧＡとその他のＣＰＵの間に接続される専用ＣＰＵをさらに含み、前記専用ＣＰＵは、前記ＦＰＧＡにテンプレートを送信して、それを再構成するように構成される請求項１に記載のデータ検索デバイス。
【請求項６】
前記専用ＣＰＵは、検索を実行する際、データ記憶装置から読み取られるデータとマッチングさせるため、前記ＦＰＧＡにキーを送信するように構成される請求項５に記載のデータ検索デバイス。
【請求項７】
データ記憶装置とＦＰＧＡの間に接続されるデータシフトレジスタをさらに含み、データ記憶装置は、データ記憶装置から読み取られる目標データを保存するように構成される請求項６に記載のデータ検索デバイス。
【請求項８】
前記ＦＰＧＡは、専用ＣＰＵと再構成可能論理デバイスとを含む請求項１に記載のデータ検索デバイス。
【請求項９】
前記ＦＰＧＡは、データシフトレジスタをさらに含む請求項８に記載のデータ検索デバイス。
【請求項１０】
ハードディスクドライブとプロセッサの間を接続するハードディスクドライブアクセラレータであって、処理能力を有するＦＰＧＡを含み、ハードディスクドライブから読み取られるデータがプロセッサに渡される前に処理のためにＦＰＧＡに送られるように構成されるハードディスクドライブアクセラレータ。
【請求項１１】
ＦＰＧＡに接続されるシフトレジスタをさらに含み、ハードディスクから読み取られるデータを受信するように構成される請求項１０に記載のハードディスクドライブアクセラレータ。
【請求項１２】
ＰＣボードをさらに含み、そこに前記ハードディスクドライブアクセラレータがマウントされる請求項９に記載のハードディスクドライブアクセラレータ。
【請求項１３】
前記ＦＰＧＡは、データプロセッサと、再構成可能論理デバイスと、データシフトレジスタとを含む請求項９に記載のハードディスクドライブアクセラレータ。
【請求項１４】
少なくとも一時的に目標データを保存する、少なくとも１つの大容量データ記憶装置と、少なくとも１つの大容量データ記憶装置に結合されるＦＰＧＡを含み、目標データの連続的ストリームを大容量データ記憶装置から読み取るように構成される、少なくとも１つの再構成可能論理デバイスとを含むデータ保存および検索デバイス。
【請求項１５】
大容量データ記憶装置は、ハードディスクである請求項１４に記載のデータ保存および検索デバイス。
【請求項１６】
再構成可能論理デバイスは、データキーの形式をとる少なくとも１つの検索照会を受信し、データキーと少なくとも１つの大容量データ記憶装置から読み取られる目標データの間でマッチを判定するように構成される請求項１５に記載のデータ保存および検索デバイス。
【請求項１７】
再構成可能論理デバイスは、アナログデータキーとアナログ目標データの間でマッチを検索するように構成される請求項１６に記載のデータ保存および検索デバイス。
【請求項１８】
再構成可能論理デバイスは、デジタルデータキーとデジタル目標データの間でマッチを検索するように構成される請求項１６に記載のデータ保存および検索デバイス。
【請求項１９】
各々が関連する再構成可能論理デバイスを有する複数の磁気記憶媒体をさらに含む請求項１４に記載のデータ保存および検索デバイス。
【請求項２０】
データキーは、複数の要素成分を有する列であり、再構成可能論理デバイスは、
列の要素成分と少なくとも１つの磁気記憶媒体から読み取られる目標データとに基づいて、複数のテーブルエントリを有するテーブルを生成するように構成されるテーブル生成器と、
各テーブルエントリを所定の閾値と比較し、それらの間の比較に基づいてマッチを判定するように構成される比較器とを含む請求項１４に記載のデータ保存および検索デバイス。
【請求項２１】
データキーは、複数のピクセルを有する画像であり、再構成可能論理デバイスは、複数のセルを有する少なくとも１つのアレイを生成するように構成されるアレイ生成器を含み、各セルは、データキーの１つのピクセルと少なくとも１つの磁気記憶媒体から読み取られる目標データの１つのピクセルとの間でマッチを判定するように構成される請求項１４に記載のデータ保存および検索デバイス。
【請求項２２】
アレイの各セルは、
データキーピクセルを格納するように構成されるデータキーピクセルレジスタと、
目標データピクセルをロードするように構成される目標データピクセルレジスタと、
データキーピクセルレジスタに格納されたデータキーピクセルを目標データピクセルレジスタに格納された目標データピクセルと比較して、それらの間でマッチが成立しているかどうかを判定する比較器とを含む請求項２１に記載のデータ保存および検索デバイス。
【請求項２３】
比較器はさらに、アレイのその他の近傍セルと通信を行い、各セルとその他の近傍セルの間でマッチを判定するように構成される請求項２２に記載のデータ保存および検索デバイス。
【請求項２４】
目標画像全体が目標データピクセルレジスタに格納された後で目標データピクセルレジスタのコピーを格納するように構成されるコピーレジスタをさらに含み、比較器は、目標データピクセルレジスタにロードされた最後の画像を目標データピクセルレジスタにロードされた現在の画像とパラレルに比較するように構成される請求項２２に記載のデータ保存および検索デバイス。
【請求項２５】
目標データピクセルレジスタへの目標データピクセルのロードと同時に、アレイのデータキーピクセルをロードするように構成されるロードデータキーピクセルレジスタをさらに含む請求項２２に記載のデータ保存および検索デバイス。
【請求項２６】
再構成可能論理デバイスは、任意の決定されたマッチに関して、集約データ削減を計算するように構成される請求項１４に記載のデータ保存および検索デバイス。
【請求項２７】
複数の再構成可能論理デバイスと、少なくとも１つの磁気記憶媒体から読み取られる目標データを格納するように構成される複数のデータシフトレジスタとをさらに含み、各データシフトレジスタは、少なくとも１つの磁気記憶媒体と各再構成可能論理デバイスの間を接続する請求項２６に記載のデータ保存および検索デバイス。
【請求項２８】
少なくとも１つの磁気記憶媒体からデータを検索するためのデバイスであって、前記少なくとも１つの磁気記憶媒体に結合され、前記少なくとも１つの磁気記憶媒体と処理のために検索データを求めているコンピュータネットワークとのインタフェースをとり、検索するよう求められているデータを表すデータキーと少なくとも１つの磁気記憶媒体から読み取られるデータを表す目標データとを比較するように構成されるＦＰＧＡを含む、再構成可能論理デバイスを含むデバイス。
【請求項２９】
コンピュータネットワークは、少なくとも１つのコンピュータを含み、その１つのコンピュータは、異なるタイプの検索プロトコル向けにＦＰＧＡを再構成するように構成される請求項２８に記載のデバイス。
【請求項３０】
ＦＰＧＡは、異なるタイプの検索プロトコル向けにＦＰＧＡを再構成するためのプロセッサ機能をさらに含む請求項２８に記載のデバイス。
【請求項３１】
異なるタイプの検索プロトコル向けにＦＰＧＡを再構成するためのデータプロセッサをさらに含む請求項２８に記載のデバイス。
【請求項３２】
少なくとも１つの磁気記憶媒体と、
少なくとも１つの磁気記憶媒体に結合される少なくとも１つの再構成可能論理デバイスとを含むネットワーク接続記憶装置であって、検索照会を受信し、それへの応答を返信するように構成されるネットワークアドレス可能入出力ポートを有するネットワーク接続記憶装置。
【請求項３３】
少なくとも１つの磁気記憶媒体からデータを検索する方法であって、
少なくとも１つの磁気記憶媒体と通信を行うプロセッサから、データキーの形式をとる検索照会を受信するステップと、
少なくとも１つの磁気記憶媒体から目標データを受信するステップと、
ＦＰＧＡを含む再構成可能論理デバイスを用いて、データキーを少なくとも１つの磁気記憶媒体から読み取られた目標データと比較するステップと、
それらの間の比較に基づいてマッチを判定するステップとを含む方法。
【請求項３４】
データキーは、複数の要素成分を有する列であり、前記方法は、
列の要素成分と少なくとも１つの磁気記憶媒体から読み取られる目標データとに基づいて、複数のテーブルエントリを有するテーブルを生成するステップと、
各テーブルエントリを所定の閾値と比較するステップと、
それらの間の比較に基づいてマッチを判定するステップとをさらに含む請求項３３に記載の方法。
【請求項３５】
データキーは、複数のデータキーピクセルを有する画像であり、目標データは、複数の目標データピクセルを有する画像であり、前記方法は、
データキーピクセルをデータキーピクセルレジスタに格納するステップと、
目標データピクセルを目標データピクセルレジスタにロードするステップと、
データキーピクセルと目標データピクセルとを比較するステップと、
それらの間の比較に基づいてマッチを判定するステップとをさらに含む請求項３４に記載の方法。
【請求項３６】
複数のセルを有する少なくとも１つのアレイを生成するステップをさらに含み、各セルは、請求項３３に記載の格納ステップ、ロードステップ、および比較ステップを実行するように構成される請求項３５に記載の方法。
【請求項３７】
目標画像全体が目標データピクセルレジスタに格納された後で目標データピクセルレジスタのコピーを格納するステップと、
目標データピクセルレジスタにロードされた最後の画像を目標データピクセルレジスタにロードされた現在の画像とパラレルに比較するステップとをさらに含む請求項３５に記載の方法。
【請求項３８】
目標データピクセルレジスタへの目標データピクセルのロードと同時に、データキーピクセルをロードするステップをさらに含む請求項３７に記載の方法。
【請求項３９】
任意の決定されたマッチに関して、集約データ削減を計算するステップをさらに含む請求項３８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、第０９／５４５４７２号の一部継続出願であり、同出願の開示は、参照により本明細書に組み込まれる。
【０００２】
本発明は、データ保存およびデータ検索のためのデバイスおよび方法に関する。
【背景技術】
【０００３】
平均的なデータベースのサイズおよび関連するソフトウェアサポートシステムは、プロセッサ性能の伸びを上回る速さで（すなわち、およそ１８ヶ月毎に２倍超）成長を続けるであろうという見通しが立てられている。これには複数の要因が絡んでおり、より詳細な情報を保存したいという要望、より長期間にわたって情報を保存したいという要望、異なる組織のデータベースをマージしたいという要望、および新たに出現した重要な適用分野から生じる新しい大規模なデータベースを運用したいという要望などが、その要因として挙げられるが、これらに限定されるものではない。例えば、大規模な急速に増大するデータベースを必要とする新たに出現した適用分野の２つの例として、遺伝学革命に関連する分野と、インターネット上での情報のカタログおよび情報へのアクセスに関連する分野がある。インターネットの場合、現在の業界推計では、１５０万を超えるページが日々インターネットに追加されている。物理的なレベルで言えば、過去５年にわたって磁気記憶密度がほぼ１年毎に倍増するというディスク記憶性能の著しい向上のおかげで、これが可能となっている。
【０００４】
情報に索引付けを施せば、探索および検索機能はより容易に実行される。例えば、金融情報を考えると、企業名、銘柄記号、価格によって索引付けることができる。しかし、検索しようとする情報が、類別も索引付けも難しいタイプの情報であったり、複数のカテゴリに含まれるタイプの情報であったりすることはよくあることである。その結果、情報検索の正確性は、そのために作成される索引の正確性および包括性と同程度にしか良くならない。しかし、インターネットの場合、情報には索引付けが施されていない。索引付けのボトルネックとなっているのは、妥当な時間でウェブページにアクセスするために必要な逆インデックスを作成するのに要する時間である。例えば、利用可能な検索エンジンは様々あるが、あまり詳しくない検索命令の組で検索すると膨大な数の「ヒット」が生成されるので、取り扱い可能な結果を返す検索をデザインすることは、ますます難しくなっている。そのため、ウェブ上には、Ｇｏｏｇｌｅなどいくつかの「知的」検索エンジンが提供されており、不要と思われる「ヒット」を除外するためのロジックを用いて、検索結果を絞り込むことが意図されている。
【０００５】
次世代インターネット、高速化し続けるネットワーク、およびインターネットコンテンツの増大を背景として、このボトルネックがクリティカルな問題になってきている。さらに、タイムリーに情報を索引付けることが、きわめて難しくなってきている。インターネットの場合、現在の業界推計では、１５０万を超えるページが日々インターネットに追加されている。その結果、逆インデックスの保守および更新は、継続的に莫大な作業量を要する作業となっており、それに起因するボトルネックが、既存の探索および検索システムの速度および正確性に対する大きな障害になってきている。一方で、利用可能な情報がその量を増し続けている現状を考えると、求める情報を正確かつ速やかに探索し検索する能力は、不可欠なものとなっている。
【０００６】
大規模データベースを運用するための連想メモリ装置が、従来技術において知られている。一般に、そうした連想メモリ装置は、コンピュータやネットワークなどとは非同期に動作する、コンピュータやコンピュータネットワークなどのための周辺メモリを含み、専門化した検索をより効率的に行えるようにする。さらに、こうしたメモリ装置が、周辺メモリへのアクセスに関してメインＣＰＵを支援する目的で一定の制限内で判断ロジックを含み得ることも、従来技術において知られている。高速ディスクまたはドラムなど回転式メモリと共に用いられるように特に構成されたそのような連想メモリ装置の一例は、米国特許第３９０６４５５号明細書に見出すことができ、同特許の開示は、参照により本明細書に組み込まれる。この特定の装置は、回転式メモリと共に用いるためのスキームを提供し、メモリ上で論理操作を実行する前にメモリを事前選別し、さらに選別するため、１つのメモリセクタに対して２つのパスが必要になることを教示する。したがって、この装置は、磁気テープなどの線形またはシリアルメモリと共に用いるには適していないことが教示される。
【０００７】
従来技術による装置のその他の例は、米国特許第３７２９７１２号明細書、第４４６４７１８号明細書、第５０５００７５号明細書、第５１４０６９２号明細書、および第５７２１８９８号明細書にも見出すことができる。これらの特許の開示は、参照により本明細書に組み込まれる。
【０００８】
一例として、米国特許第４４６４７１８号において、ディクソン（Ｄｉｘｏｎ）は、固定数のバイトについて固定比較を実行する。この比較は、データを全体的にスキャンし、任意に相互に関連させる能力を有していない。この比較は、一定のディスクシリンダの中でトラックに沿ってシリアルに検索を行うが、ディスクを横切るパラレル検索は、用意されていない。ディクソンの比較は、厳密に固定された数の標準的な論理操作タイプによって限定される。さらに、提示される回路は、そのような単一の論理操作しかサポートしない。近似的または曖昧マッチングに対するサポートは提供されない。
【０００９】
これらの従来技術による連想メモリ装置は、多くの場合は大容量メモリ装置である周辺メモリに対する情報の入出力を高速化することを試みるが、そのすべてが、メモリロケーションのデジタル形式のアドレスまたは内容を読み取り、解釈することによって、デジタル形式で保存されたデータにアクセスする古典的なアクセス方式に依存している。言い換えると、そのような装置の大部分は、データのアドレスによってデータにアクセスするが、一部の装置は、当技術分野でよく知られている内容アドレス方式の能力を利用している。それにもかかわらず、発明者らが知る従来技術はどれも、処理のためにデータを識別し選択するには、アドレスのデジタル値またはアドレスされたロケーションに含まれるデータのデジタル値を読み取り、それをデジタル形式で解釈しなければならない。このような方式だと、アドレスまたは内容によって表されるデジタルデータを読み取り、解釈するのに処理時間がかかるばかりか、保存データの構造に従ってアクセス回路でメモリを処理することがどうしても必要となる。言い換えると、データがオクテット単位で保存されるならば、アクセス回路は、オクテット単位でデータにアクセスし、増分式でデータを処理しなければならない。この「スタートおよびストップ」処理は、データにアクセスするのに必要とされる入出力時間を増加させるように作用する。また当技術分野でよく知られているように、この入出力時間は一般に、コンピュータまたはコンピュータネットワークの処理能力のボトルネックおよび実効限界となる。
【００１０】
さらに、検索対象として利用可能な情報が大量に与えられている場合、データ削減操作（すなわち、データを何らかの集約形式に要約する能力）が不可欠になる。データ削減機能を速やかに実行する能力はしばしば、企業に大きな競争上の利点を提供する。
【００１１】
同様に、デジタル画像技術における技術向上に伴い、画像上などで２次元マッチングを実行する能力も必要になってきた。例えば、警察当局は、２００１年９月１１日のテロリスト攻撃を踏まえてセキュリティ上の活動を強化しており、個々人の顔もしくは網膜など特徴的な像に対してまたは指紋に対してマッチングを行う能力は、警察当局にとって不可欠なものとなっている。画像マッチングは、軍隊にとっても自動目標認識の分野で重要となっている。
【００１２】
最後に、今のところ既存の検索装置は、アプリケーション要求の変化に対応して、速やかにかつ容易に再構成することができない。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、従来技術が抱える上記およびその他の問題を克服する、改良された情報探索および検索のためのシステムおよび方法が必要とされている。
【課題を解決するための手段】
【００１４】
従来技術が抱える上記およびその他の問題を解決するため、本発明の発明者らは、従来技術が抱える上記の制約に対する洗練された単純性をもつ解決法を提供する、大容量メモリに格納されたデータに対するアクセス時間を劇的に短縮する、複数の実施形態において、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を利用する連想メモリのための方法および装置を設計し開発することに成功した。以下で説明するように、本発明は、それぞれ独自の利点を有する複数の実施形態を有する。
【００１５】
本発明の親出願は、本発明の上記部分で利用可能な様々な種類のデバイスの選択に関して一般に特定的ではない、プログラム可能論理および回路の使用を開示し、主張する。本特許の出願において、発明者らは、様々な理由からＦＰＧＡを回路の一部で最良の実施形態として使用することについて、より具体的に開示している。ＦＰＧＡが最良の実施形態となるのには、いくつかの理由がある。第１の理由はスピードである。そして、スピードが大きな役割を果たす動作には、２つの異なる側面がある。スピードに関する第１の側面は、再構成のスピードである。ＦＰＧＡは、検索方法を最適化するためにテンプレートを用いて現場で素早くプログラムすることができ、テンプレートは、あらかじめ用意しておき、接続バスを介してＦＰＧＡに伝送しさえすればよいことが当技術分野で知られている。その後、異なる方法を用いて検索を行いたくなった場合、ＦＰＧＡは、別の用意されたテンプレートを用いて、最小のクロックサイクル数で速やかにかつ便利に再プログラムすることができ、第２の検索を直ちに開始することができる。したがって、再構成可能論理としてＦＰＧＡを使用した場合、１つの検索から別の検索への移行を、その他のタイプの再プログラム可能論理デバイスと比べて、非常に容易にかつ素早く行うことができる。
【００１６】
スピードに関する第２の側面は、プログラムを行った後で、検索に要する時間である。ＦＰＧＡはハードウェアデバイスであるので、例えば、マイクロプロセッサでの実測で、ソフトウェアの処理速度よりも数桁（ｏｒｄｅｒｓ  ｏｆ  ｍａｇｎｉｔｕｄｅ）高速なハードウェアの処理速度で、検索を実行することができる。したがって、ＦＰＧＡは、ほとんどの場合がそうであるようにスピードが考慮要件となる場面において、その他のソフトウェア実装よりも望ましい。
【００１７】
テンプレートの使用を考察する際には、少なくともいくつかの「汎用」テンプレートがあらかじめ用意されており、絶対検索、近似検索、またはブール代数論理機能を含む高等もしくは高度検索モードのいずれかによるテキスト検索、またはグラフィックス検索モードを実行するのに利用可能であることが企図されている。これらのテンプレートは、ＣＰＵのメモリに格納することができ、コマンドで呼び出して、または上記検索の１つを指示するソフトウェアキューに応答して自動的にロードして利用することができる。
【００１８】
考慮すべきさらに別の要因はコストであり、ＦＰＧＡの最近の価格低下によって、ＦＰＧＡは、検索アプリケーションのための好ましい実施形態を実装するのに、特にＰＣ市場向けのハードディスクドライブアクセラレータの一部を実装するのにより適したものとなった。さらなるコスト低下によって、上記実装および以下でより詳しく説明するその他の事項に対するＦＰＧＡの好ましさがより高まるであろうことが十分に予想される。
【００１９】
一般に、本発明は、検索用のテンプレートを含み、比較を行うＦＰＧＡを使用して、すべてハードウェア的に、基本的に配線速度で、データキーと連続的に読み込まれる大容量記憶媒体に保存されたデータとの近似マッチングを行うことによって、データを検索するための技法として説明される。ＦＰＧＡを利用することによって、一般に知られている多くの利点および特徴が利用できるようになる。これには、ＦＰＧＡを「パイプライン」状に並べて、「パラレル」に並べて、さらには複雑な検索アルゴリズムを可能にするために相互接続データパスをクモの巣状に複雑に交差させたアレイとして配置可能であることが含まれる。最も広範であり、おそらくは最も強力な実施形態においては、データキーは、アナログ信号とすることができ、一般的な読み取り／書き込み装置がそのヘッドを大容量記憶媒体面で動かす際に、当該装置によって生成されるアナログ信号とマッチングされる。言い換えると、大容量記憶媒体に保存されたデジタルデータのアナログ表現を読み込むだけでなく、その信号を比較に先立ってデジタル形式に変換するという、従来技術において必要であると教示されていたステップが取り除かれる。さらに、データが編成および保存される構造または形式を用いて、データを「フレーム化」したり、比較したりする必要はない。アナログ信号の場合、明確にする必要があるのは、「読み取り」信号の連続的に変化する対応する選択時間部分との比較に用いられる、アナログ信号の経過時間だけである。従来技術において知られている数多くの標準的な相関技法のいずれか１つを用いて、データ「キー」とデータ信号のスライディング「ウィンドウ」との近似マッチングを行って、マッチを判定することができる。注目すべきは、同じデータ量をはるかに高速にスキャンでき、さらに検索要求とマッチするデータをはるかに高速に決定できることである。例えば、発明者らは、現在の標準的な「ハイエンド」システム上で、２００メガバイトのＤＮＡ配列についてのＣＰＵベースの近似検索を行った場合、データベースを索引付けるためのオフライン処理がすでに完了しているという前提で、最大で１０秒かかることを見出した。発明者らは、本発明を利用すれば、同じ１０秒間で、１０ギガバイトのディスクを磁気的に検索して近似的マッチを探し出せることを見出した。これは性能的に５０倍の改善を見たことになる。さらに、標準的なハードディスクドライブには、４つの面があり、それらに対応する読み／書きヘッドが設けられているが、各ヘッドに本発明を装備すれば、４面すべてをパラレルに検索することができる。こうした検索はパラレルに進行するので、全体的なスピードの向上または改善は２００倍に達する。さらに、追加のハードディスクドライブにパラレルでアクセスできるので、追加ドライブを増減し、本発明によって提供される利点をさらに高めることができる。
【００２０】
適切な相関またはマッチング技法を選択することによって、また適切な閾値を設定することによって、希望信号に正確にマッチする検索を行うことができ、あるいは閾値を下げることで、より重要でおそらくはより強力な方法として、近似マッチング検索を提供することもできる。近似マッチング検索は一般に、データベースをスキャンして、データが探しているデータと近似的に一致するだけでも有効と見なされる「ヒット」を見つけるという点で、より強力な検索モードであると考えられている。これによって、破損したデータ、不正確に入力されたデータ、およびカテゴリと大まかに対応するだけのデータを見つけるための検索、また多くの適用分野で強く望まれているその他のタイプのデータ検索を行うことができる。例えば、ＤＮＡ配列のライブラリを検索して、残基の希望配列と近似的にマッチすることを示すヒットを見つけ出すことが求められる場合がある。これによって、希望配列に近い配列を、残基のミスマッチが許容できる数であれば相違があっても捨て去らずに、確実に見つけ出すことができる。検索を行いたい情報の量およびタイプが増加の一途を辿っている状況に鑑み、より複雑な検索技法が必要とされている。このことは分子生物学の分野で特に真実であり、「遺伝子（または遺伝子によって符号化されたタンパク質）の生物学的機能を推論するための最も強力な方法の１つは、タンパク質およびＤＮＡ配列データベース上で行われる配列の類似性検索によるものである」。Ｇａｒｆｉｅｌｄ、「Ｔｈｅ  Ｉｍｐｏｒｔａｎｃｅ  ｏｆ  （Ｓｕｂ）ｓｅｑｕｅｎｃｅ  Ｃｏｍｐａｒｉｓｏｎ  ｉｎ  Ｍｏｌｅｃｕｌａｒ  Ｂｉｏｌｏｇｙ」、２１２〜２１７ページ。同文献の開示は、参照により本明細書に組み込まれる。配列マッチングのための現在の解決手法は、ソフトウェアまたは再構成不可能ハードウェアとしてのみ利用可能である。
【００２１】
また別の適用分野として、インターネット検索エンジンによって提供されるインターネット検索が挙げられる。そのような検索では、近似マッチングのおかげで、スペル誤りの単語、スペルの異なる単語、およびその他の変化形でも、検索を失敗させることなく、または特殊化した検索を複数回組み合わせる必要なく、検索することができる。この技法によって、検索エンジンは、任意の与えられた検索に対してより多くのヒットを提供することができ、その検索においてより多くの適合性のあるウェブページを確実に見つけ出し、カタログすることができる。しかし、先に述べたように、この近似検索は、より多くの「ヒット」を生成するより広い網を投げることになるので、そのことが独自の問題を生むことになる。
【００２２】
本発明のさらに別の可能な適用分野に、サイズ的に巨大となることがあるデータベースまたはアナログ表現で保存されることがあるデータベースにアクセスする分野がある。例えば、われわれの社会では、音声記録装置が実現され、訴訟手続きを含む数多くの討論において、それが使用されているのを目にする。最近の歴史においては、大統領執務室で録音されたテープ記録が、弾劾尋問に関係して、重要な意味をもつに至った。理解できるであろうが、大統領の在任期間にわたって録音されたテープ記録は、蓄積されて膨大なデータベースとなり、それを実際に聞いて、重大な意味をもつ特定の言葉が話された箇所を見つけるには、多数の人を必要とする。本発明を利用すれば、その話された言葉のアナログ表現をキーとして用い、データベースを連続的かつ高速にスキャンしながら、マッチする言葉を探すことができる。したがって、本発明は、大容量アナログデータベースおよび大容量デジタルデータベース向けの強力な検索ツールを提供する。
【００２３】
上で説明したように、本発明によってテキストベースの検索が提供されるが、画像、音声、およびその他の表現を含む記憶媒体を検索するほうが、テキストを検索するよりも伝統的に難しい。本発明によって、そのようなコンテンツまたはその一部分を格納する大規模データベースを検索することができる。例えば、この場合のキーは、検索対象の画像を表すピクセルの列または象限とすることができる。キー信号との近似的マッチを判定する際、キーとのマッチまたは近いマッチをマッチと見なすことができる。さらに別の画像関連適用分野においては、同じ地理的場所の画像の比較が、装備または部隊の移動を示すものとして重大な意味をもつ場合、ピクセルまたはピクセルグループの相違を検索し、その結果、衛星画像にとってどれが重要であり得るかを指摘することができる。
【００２４】
本発明は、以下でより詳細に言及するような複数の構成のいずれかで実施することができる。しかし、重要な一実施形態はおそらく、ハードディスクドライブとシステムバスの間のインタフェースとして任意のＰＣに簡単にインストールされる、ディスクドライブアクセラレータの形態をとるものであろう。このディスクドライブアクセラレータは、１組の標準化されたテンプレートを備えることができ、ＣＰＵによってドライブからデータがアクセスされるスピードを劇的に向上させるための「プラグアンドプレイ」ソリューションを提供する。このディスクドライブアクセラレータは、ＰＣの大きな設置基盤に向けて販売される付属デバイスまたは増強用デバイスとすることができる。このディスクドライブアクセラレータは、新しいディスクドライブの一部として、外付けドライブ用のドライブケースまたは筐体内にパッケージして提供することもでき、内蔵ドライブのアダプタとしてＰＣカードの増設プラグに装着して提供することもできる。様々なタイプのデータベースで様々なタイプの検索を行うための追加のテンプレートは、ＣＤ上に符号化されるなどしたものをアクセラレータの購入時に入手することができ、またはインターネットを介して必要に応じてダウンロードすることによって入手することもできる。
【００２５】
本発明の主要な利点および特徴について、上で簡潔に説明したが、本発明についてのより完全な理解は、図面および以下に示す好ましい実施形態の説明を参照することによって得られるであろう。
【発明を実施するための最良の形態】
【００２６】
図１に示すように、本発明は、スタンドアロンコンピュータまたはコンピュータシステムに容易に実装される。概略的に言えば、本発明は、少なくとも１つの磁気大容量媒体２６に結合される少なくとも１つの再構成可能論理デバイス２１から構成され、前記再構成可能論理デバイスはＦＰＧＡとする。図１に示すように、再構成可能論理デバイス２１はそれ自体が、データシフトレジスタや場合によってはマイクロプロセッサを始めとする複数の機能論理要素を含むことができる。または機能論理要素は、別個のチップ上に存在することができ、または個々の機能論理要素は、本明細書の別のいくつかの図面に示すように、パイプラインを形成して、またはパラレルに配置して構成することができる。いずれの場合も、再構成可能論理とは、製造工程後の現場で形態および機能を大幅に変更（すなわち、再構成）することができる任意の論理技術のことを指す。再構成可能論理デバイスの例として、プログラム可能論理デバイス（ＰＬＤ）があるが、これに限定されるものではない。ＰＬＤという用語は、プログラム可能な様々なチップを一括して呼んだ包括的な用語である。一般に、ＰＬＤの物理的構造には３つのタイプが存在する。第１のタイプは、永久ヒューズタイプであり、アルミニウムの線または絶縁体を電気的に溶かして、配線を切断したり、接続したりする。これは、「プログラム可能アレイ論理」またはＰＡＬとして知られる第１のタイプのＰＬＤである。第２のタイプのＰＬＤは、ＥＥＰＲＯＭまたはフラッシュメモリを使用し、メモリセルの内容に応じて、それに関連付けられたトランジスタを開いたり、閉じたりする。第３のタイプのＰＬＤは、（ＰＬＤを動的かつ揮発性にする）ＲＡＭベースのもので、その内容は起動のたびにロードされる。ＦＰＧＡは、任意の方式で相互接続できる論理ユニットのアレイを含む集積回路（ＩＣ）である。これらの論理ユニットのことを、ある製造元（Ｘｉｌｉｎｘ社）では、ＣＦＢすなわち構成可能論理ブロックと呼んでいる。各論理ユニットに特有な機能および論理ユニット間の配線を、ＩＣ製造後、現場でプログラムすることができる。ＦＰＧＡは、最も普及しているＰＬＤチップの１つである。ＦＰＧＡは、３つの構造のすべてで利用することができる。本発明の好ましい実施形態では、再構成可能論理デバイス２１は、Ｘｉｌｉｎｘ社のＦＰＧＡ技術を用いて構成され、その構成は、Ｍｅｎｔｏｒ社の統合ツールおよびＸｉｌｉｎｘ社の配置配線ツールを用いて開発される。これらのツールはすべて、当業者に知られているように、現在市販されている。
【００２７】
再構成可能論理デバイス２１は、システムまたは入出力バス３４とインタフェースをとり、また、一構成においては、存在してもよい任意のディスクキャッシュ３０ともインタフェースをとる。再構成可能論理デバイス２１は、ＣＰＵ３２またはネットワークインタフェース３６から検索要求または照会を受信し、それらを処理する。さらに、再構成可能論理デバイス２１は、照会の結果を（バス３４を介して）ディスクキャッシュ３０とＣＰＵ３２の一方または両方に受け渡すための支援を行う。
【００２８】
大容量記憶媒体２６は、以降本明細書で目標データと呼ぶ大量の情報を保存するための媒体を提供する。「大容量記憶媒体」という用語は、大量のデータを保存するのに使用され、一般にコンピュータまたはコンピュータネットワークで使用するよう指示される任意の磁気装置を意味するものと理解されたい。その例として、ハードディスクドライブまたは単一ディスク面などのサブユニットがあるが、これらに限定されるものではなく、これらのシステムは、回転式、線形、シリアル、パラレル、またはそれらの様々な組合せとすることができる。例えば、ラック１つ分のハードディスクドライブユニットをパラレルに接続し、それらのパラレル出力をトランスデューサのレベルで１つまたは複数の再構成可能論理デバイス２１に提供することができる。同様に、バンク１つ分の磁気テープドライブを使用し、それらのシリアル出力をそれぞれパラレルに１つまたは複数の再構成可能論理デバイス２１に提供することができる。媒体に保存されるデータは、アナログ形式またはデジタル形式とすることができる。例えば、データを音声記録とすることができる。したがって、本発明は拡張性があり、パラレルな再構成可能論理デバイスの数を増やすか、または再構成可能論理デバイスを複製することによって性能を保ちながら、パラレルな大容量記憶媒体の数を増やすことによって、保存データ量の増加に対応することができる。
【００２９】
従来技術では図１の上側部分に示すように、ＣＰＵ３２によるそのシステムまたは入出力バス３４を介したアクセスのために、一般にディスクコントローラ２８および／またはディスクキャッシュ３０を従来の意味で使用することができる。再構成可能論理デバイス２１は、１つまたは複数のデータシフトレジスタ２４を介して大容量記憶媒体２６内の目標データにアクセスし、選別およびアクセスのためにメモリの大きなブロックを大容量記憶媒体２６からシステムバス３４を介してＣＰＵ３２の作業用メモリ３３に移送することなく、使用のために目標データをシステムバス３４に提供する。言い換えると、以下でより詳しく説明するように、ＣＰＵ３２は、検索要求または照会を再構成可能論理デバイス２１に送信することができ、再構成可能論理デバイス２１は、大容量記憶媒体２６内の目標データに非同期にアクセスし、それを選別し、ＣＰＵ３２によるさらなる処理を必要としないで、またはＣＰＵの作業用メモリ３３を使用しないで、従来技術で知られているようにディスクキャッシュ３０に、または直接システムバス３４に、使用のために目標データを提供する。したがって、本発明によって検索およびマッチング動作が実行されている間、ＣＰＵ３２は、自由にその他のタスクを実行することができる。代替的に、制御マイクロプロセッサが、検索照会およびテンプレートまたはプログラミング命令をＦＰＧＡ２１に提供することができ、次に検索を実行し、ＣＰＵ３２によるアクセスおよび使用のためにデータをシステムバス３４に提供することができる。
【００３０】
先に説明したように、本発明は、様々な異なるタイプのマッチングまたはデータ削減操作を目標データに対して実行するために利用することができる。これらの操作について１つずつ、以下で詳しく説明する。しかし、すべての操作において、目標データは磁気大容量記憶媒体２６に十分なフォーマット情報を付して書き込まれており、目標データの論理構造を取得可能であることが仮定される。正確な文字列マッチングおよび近似的な文字列マッチングについて、図２〜図５を参照しながら説明する。しかし、本発明が、単一の文字列マッチングに限定されるものではなく、複合クエリマッチング（すなわち、互いに一定の論理関係を有する複数のテキスト文字列を含むか、またはブール代数論理を用いるクエリ）にも等しく適していることは理解できよう。図２においてポイントＡとして示された、マッチングがアナログ比較器と相関技法を用いて実行されるアナログ領域で、正確なマッチングを再構成可能論理デバイス２１によって実行する場合、正確なマッチングは、データキーと大容量記憶媒体２６内のアナログ目標データとのマッチングを判定するための十分に高い閾値を設定することに相当する。アナログ領域における近似マッチングは、適切な（より低い）閾値を設定することに相当する。近似マッチの成功は、再構成可能論理デバイス２１に設定された相関値によって、またはスキャンされた目標データ中の対応ビットと等しいデータキー中のビットの数など、再構成可能論理デバイスに保存された複数のマッチング成績測定基準の１つを用いることによって判断することができる。
【００３１】
より具体的には、従来の柔軟性の乏しいディスクドライブは、ディスクにアクセスするトランスデューサをディスク毎に備えた複数の回転ディスクを有する場合がある。一般にこれらのトランスデューサは各々、増幅器などの出力供給アナログ信号回路１８を有する。これはポイントＡに表されている。図２にさらに示すように、一般にアナログ回路の出力は、そのような出力の１つを処理する単一のデジタル復号器２３に選択的に提供される。これはポイントＢに表されている。一般にこのデジタル出力は、誤り訂正回路（ＥＣＣ）２５に送られ、その出力Ｃにおいてバス３４またはディスクキャッシュ３０に渡される。本発明の目的にとっては、複数のデジタル復号器およびＥＣＣを提供することによって、複数のパラレルパスを目標データに提供したほうが望ましい場合もある。デジタル領域における正確なマッチングは、事前誤り訂正信号、事後誤り訂正信号にそれぞれ対応する、ポイントＢまたはポイントＣで実行される。
【００３２】
結果は、複合または混成検索照会に関連するロジックを実行するため、ＦＰＧＡの一部として構成してもしなくてもよい制御マイクロプロセッサ２２に送ることができる。最も一般的な場合においては、複合検索照会４０は、図３に示す変換プロセスを通過する。具体的には、ＣＰＵ３２上に存在するソフトウェアシステム（図示せず）が、複合検索照会４０を生成する。この照会は、コンパイラ４２を通過し、検索照会を解析する役割を担ったＣＰＵ３２上にやはり配置される。この解析からは、３つの主な結果が得られる。すなわち、（１）再構成可能論理デバイス２１内の比較レジスタに存在するデータキーが決定され、（２）制御マイクロプロセッサ２２で実施しなければならない合成ロジックが決定され、（３）再構成可能論理デバイス２１に対する合成コマンド４６を生成するのに用いるハードウェア記述４４が標準的なハードウェア記述言語（ＨＤＬ）形式で生成される（または可能であればライブラリから１つが取得される）。市販されているＨＤＬ、関連コンパイラ、および合成ツールのうち任意のものを使用することができる。結果の論理機能は、正確なもしくは不正確なマッチ、またはワイルドカード操作、および「ａｎｄ」や「ｏｒ」など簡単な単語レベルの論理演算に対応することができる。この合成情報は、再構成可能論理デバイス２１またはＦＰＧＡを設定するために動作する制御マイクロプロセッサ２２に送られる。複雑な論理演算の場合、マイクロプロセッサ２２に対する適切な合成コマンドを生成するため、ＣまたはＣ＋などの高水準言語４８がコンパイラ５０と併せて用いられる。
【００３３】
図３に示すパスは、発生し得る広い範囲の検索照会を処理することができるが、検索プロセスに導入される待ち時間が長くなり過ぎることがあるという難点を有している。検索照会において、図３に示す変換を終えるのに必要な時間が、検索を実行するのに必要な時間と同じオーダとなる場合、検索自体ではなく、コンパイルプロセスが性能のボトルネックとなる。この問題は、広い範囲の予期される検索照会については、最も一般的なケースを取り扱う１組の事前コンパイルされたハードウェアテンプレートを維持することによって対処することができる。これらのテンプレートは、ＣＰＵ３２のメモリにおいて提供し、維持することができ、またはＣＤなどのオフライン記憶媒体を介して利用可能とすることができ、さらには大容量記憶媒体２６自体で保持することができる。さらに、こうしたテンプレートは、ネットワークやインターネットなどを介してＣＰＵ３２に伝送することができる。
【００３４】
図４に、このようなハードウェアテンプレート２９の一実施形態を示す。具体的には、データシフトレジスタ２７は、１つまたは複数のディスク１９のヘッド（図示せず）からストリーム送信された目標データを含む。比較レジスタには、ユーザがマッチさせたいデータキーを格納する。図示の例では、データキーは「Ｂａｇｄａｄ」である。微小比較論理デバイス３１が、データシフトレジスタ２７内の要素成分と比較レジスタ３５内の要素成分の間で、要素成分同士の比較を実行する。微小比較論理デバイス３１は、大文字と小文字を区別するように（ｃａｓｅ  ｓｅｎｓｉｔｉｖｅ）、または区別しないように構成することができる。単語レベル比較論理３７は、世界レベルでマッチが生じたかどうかを決定する役割を担っている。複合検索照会の場合、単語レベルのマッチ信号は、評価のために制御マイクロプロセッサ２２に送られる。複合検索照会についてのマッチは、さらなる処理のためにＣＰＵ３２に報告される。
【００３５】
図５に、近似マッチングを実行するハードウェアテンプレートの一実施形態を示す。具体的には、データシフトレジスタ２７’は、１つまたは複数のディスク１９’のヘッド（図示せず）からストリーム送信された目標データを含む。比較レジスタ３５’には、マッチさせたいデータキーを格納する。図示の例では、データキーは再び「Ｂａｇｄａｄ」である。微小比較論理デバイス３１’が、データシフトレジスタ２７’内の要素成分と比較レジスタ２１’内の要素成分の間で、要素成分同士の比較を実行する。やはり、微小比較論理デバイス３１’は、大文字と小文字を区別するように、または区別しないように構成することができる。テンプレート２９’は、微小比較論理デバイス２１’の個々のセルに通じる代替経路を、データシフトレジスタ２７’内の要素成分に提供する。具体的には、比較レジスタ２１’が、「Ｂａｇｈｄａｄ」という一般に使用されているスペルでも、「Ｂａｇｄａｄ」という代替スペルでも、共用ハードウェアでマッチングを成立させることができるように、微小比較論理デバイス３１’の各セルは、データシフトレジスタ２７’の２以上の位置とマッチング比較を行うことができる。単語レベル比較論理３７’は、単語レベルでマッチが生じたかどうかを決定する役割を担っている。複合検索照会の場合、単語レベルのマッチ信号は、評価のために制御マイクロプロセッサ２２に送られる。複合検索照会についてのマッチは、さらなる処理のためにＣＰＵ３２に報告される。
【００３６】
もちろん、ハードウェアテンプレートの実際の構成は、検索照会のタイプに応じて変化する。ハードウェアテンプレートに僅かな柔軟性を与えることによって（例えば、目標データの比較レジスタへの格納、データシフトレジスタおよび比較レジスタ要素成分からの信号の微小比較論理デバイスのセルへの転送、単語レベル比較論理の幅）、そうしたテンプレートは、多様な単語マッチをサポートすることができる。その結果、図３に示した検索照会変換をすべて行わなければならない頻度が減少し、延いては、検索速度が向上する。
【００３７】
「近似的」マッチ検索で一致が確認されたデータエントリが、「正確な」検索の結果である「正確な」ヒットを含むことに留意されたい。この点を明確にすれば、「マッチ」という言葉が使われる場合、この言葉には、近似的な検索または正確な検索によって見つけられた検索結果またはデータ結果が含まれることを理解されたい。「近似的なマッチ」という語句または単に「近似的」という語が使われる場合、近似的な検索として上で説明した２つの検索のいずれかを意味することが、さらに言えば、検索照会または特にデータキーに緩やかに関連する目標データを集めるための十分大きな網をもつその他のタイプの「曖昧な」検索を意味することができることを理解されたい。もちろん、正確なマッチは、まさに正確なものであり、高度な相関を有する検索照会の正確なマッチ以外のどのような結果も含まない。
【００３８】
図１には、本発明とネットワーク３８とを相互接続するネットワークインタフェース３６も示されている。ネットワーク３８は、ＬＡＮ、ＷＡＮ、インターネットなどとすることができ、その他のコンピュータシステム４０を接続することができる。このような構成とした場合、その他のコンピュータシステム４０も、本発明２１によって大容量記憶媒体２６に保存されたデータにアクセスできれば都合がよい。より具体的な例を以下に示す。図１にさらに示すように、要素２０〜２４は、一緒にパッケージして、本発明の利点を有する独自のディスクドライブを有する既存ＰＣを構成するための改良用デバイスとして独立に提供できる、ディスクドライブアクセラレータを形成することができる。代替として、ディスクドライブアクセラレータは、ハードドライブのオプションとして提供して、外付けドライブと一緒に同じ筐体内にパッケージすることができ、または内蔵ドライブ用のコネクタインタフェースを有する独立のＰＣボードとして提供することができる。さらなる代替として、ディスクドライブアクセラレータは、消費者、企業、またはその他のエンドユーザによって注文されたＰＣの部品として、ＰＣ供給元によってオプションで提供することもできる。さらに別の実施形態として、ディスクドライブアクセラレータは、より大規模な磁気大容量記憶媒体の部品として提供することができ、またはそのようなアプリケーションもしくは既存インストールのアップグレードキットもしくは改良用キットとして提供して、アプリケーションもしくは既存インストールにおいて、向上したデータ処理能力をその利点を活かして利用できるようにすることができる。
【００３９】
図６〜図８に示すように、本発明は、様々なコンピュータおよびネットワーク構成において実施することができる。図６に示すように、本発明は、システムバス４５に接続されたＣＰＵ４３を含むスタンドアロン型コンピュータシステム４１の一部として提供することができ、ＣＰＵ４３は、本明細書で開示される発明を有する大容量記憶媒体４７にアクセスする。
【００４０】
図７に示すように、本発明と結合された大容量記憶媒体５１は、ネットワーク５２に直接接続することができ、複数の独立したコンピュータまたはＣＰＵ５４は、ネットワーク５２を介して大容量記憶媒体５１にアクセスすることができる。大容量記憶媒体５１は、ＲＡＩＤ、ディスクファーム、または著しく短縮されたアクセス時間で膨大な量のデータにアクセスし、近似マッチングを実行する能力を提供するその他の何らかの超並列メモリ装置構成を含む、ハードディスクドライブのバンクから構成することができる。
【００４１】
図８に示すように、本発明と結合された大容量記憶媒体５６は、複数のスタンドアロン型コンピュータ６０がネットワーク５８を介してアクセスできるように、ネットワーク接続記憶装置（ＮＡＳＤ）としてネットワーク５８に接続することができる。そのような構成とした場合、説明のためだけにディスク５７として示した各大容量記憶媒体は、ネットワークに接続された任意のプロセッサからアクセスできることが企図されている。そのような構成の１つでは、一意のＩＰアドレスまたはその他のネットワークアドレスを、各大容量記憶媒体に割り当てる。
【００４２】
図１および図６〜図８に示す構成によって例示された構成は、本発明と互換性があり、本発明が非常に役立つ様々なコンピュータおよびネットワーク構成の例を示したに過ぎない。その他の構成も当業者には明らかであろう。本発明は、本明細書に示された例によって限定されるものではなく、そうした例はむしろ、本発明の汎用性を示すことを目的としている。
【００４３】
図９に示すように、正確なまたは近似的なマッチングで利用される本発明の方法は、アナログデータ領域が検索されるか、デジタルデータ領域が検索されるかに応じて、二者択一的に説明される。しかし、この方法を開始する最初に、ＣＰＵは、一定の機能を実行し、その実行中に、大容量記憶媒体に保存された目標データにアクセスことを選択することができる。一般にＣＰＵは、ＤＮＡ検索、インターネット検索、アナログ音声検索、指紋検査、画像検索、または目標データとの正確なまたは近似的なマッチが求められるその他の何らかの検索に相当し得る、検索照会アプリケーション６２を実行する。検索照会は、データキーを大容量記憶媒体２６から正しく取得するために、ディスクコントロールユニット２８および再構成可能論理デバイス２０がもたなければならない様々なパラメータを指定する指令を含む。パラメータの例として、記憶装置のスキャンを開始するロケーション、（マッチが生じなかった場合に）スキャンを終了させる最終ロケーション、スキャンに使用されるデータキー、マッチングの近似性の詳細、およびマッチが生じた際にどのような情報を返すかといったものが挙げられるが、これらに限定されるものではない。返すことのできる情報としては、マッチが生じた情報のアドレス、またはマッチした情報を含むセクタ、レコード、レコードの部分、もしくはその他のデータ集合体が挙げられる。データ集合体は、マッチしたデータが含まれる有界な領域を限定する上限および下限データの間の範囲によって、マッチの際に返すデータを指定することができるという意味で、動的に指定することもできる。図５を例にとると、文字列テキストの中から単語「ｂａｇｄａｄ」を探す操作は、スペルミスに起因する近似的マッチの単語「Ｂａｇｈｄａｄ」を見つけ、周囲の文によって定義されるデータフィールドを返すことができる。別のクエリパラメータでは、返された情報をシステムもしくは入出力バス３４に送るべきか、それともディスクキャッシュ３０に送るべきかが指定される。
【００４４】
図９に戻ると、検索照会は一般に、結果として１つまたは複数のオペレーティングシステムのユーティリティを実行する。ＵＮＩＸ（登録商標）オペレーティングシステムの場合の高水準ユーティリティを例にとれば、これらのユーティリティは、ｇｌｉｍｐｓｅ、ｆｉｎｄ、ｇｒｅｐ、ａｐｒｏｐｏｓなどの修正版とすることができる。ＣＰＵは、これらの機能からの指示で、検索、近似検索などのコマンド６６を再構成論理デバイス２１に送り、また例えば、大容量記憶媒体から目標データを正しく読み取るために後で必要とされる大容量記憶媒体の位置付け動作６９を起動するために、これらのコマンドの関連部分をディスクコントローラ２８にも送る。
【００４５】
この段階で、本発明の具体的な実施形態において実施されることが望まれる具体的な方法に応じて、アナログデータキーまたはデジタルデータキーを決定することが必要である。テキスト検索のための正確なキーまたは近似的なキーとすることができるこのデータキーは、検索対象のデータに対応する。アナログデータキーの場合、データキーは、大容量記憶媒体などに事前保存しておくか、専用回路を用いて作成するか、または生成するよう要求することができる。アナログデータキーを事前保存しておく場合、事前保存データキー送信ステップ６８が、マイクロプロセッサ２２（図１参照）によって実行され、マイクロプロセッサ２２は、ステップ７０に示すように、データキーをデジタルサンプル形式で再構成可能論理デバイス２０に送信する。代替として、アナログデータキーを事前保存しておかない場合、データキーは、複数ある機構の１つを用いて作成することができ、図９には、それらの機構のうちの２つが示されている。２つの機構の一方では、マイクロプロセッサ２２が、ステップ７２に示すように、磁気大容量記憶媒体にデータキーを書き込み、次にステップ７４で、データキーのアナログ表現を生成するために、そのデータキーを読み取る。２つの機構のもう一方では、ステップ７１に示すように、ＣＰＵから受け取ったデータキーのデジタル表現を、適切なデジタル／アナログ回路を用いてアナログ信号表現に変換し、次にそれを適切にサンプリングする。データキーは次に、ステップ７０に示すように、データキーのデジタルサンプルとして保存される。デジタルデータキーが使用される場合、マイクロプロセッサ２２は、ステップ７６に示すように、デジタルデータキーを再構成可能論理デバイスの比較レジスタに保存しさえすればよい。各再構成可能論理デバイスに含まれることが望まれる具体的な構造に応じて、データキーは、これらの構成要素のいずれかまたはすべてに存在することができ、好ましくは、比較および相関のため、適切なデジタル形式でデータキーを最終的に再構成可能論理デバイス２１に取り込めさえすればよいことを理解されたい。
【００４６】
次に、ステップ７９に示すように、大容量記憶媒体２６がその開始ロケーションに到達すると、ステップ７８に示すように、大容量記憶媒体に保存されている目標データが連続的に読み取られて、目標データを表す連続的なストリーム信号が生成される。アナログデータキーが使用される場合、ステップ８０に示すように、このアナログデータキーを、大容量記憶媒体２６から読み取った目標データのアナログ表現と相関させることができる。
【００４７】
発明者らは、従来技術による多くの比較器および相関回路が使用できることを企図しているが、本発明の目的にとって、アナログ信号およびデータキーのデジタルサンプリングが、以下で説明するような比較を実行し、相関係数を計算するのに非常に役立ち得ることを提案する。大容量記憶媒体２６から目標データを読み取ることによって生成されるこのアナログ信号は、従来技術の装置によってアナログデータまたはデジタルデータを読み取ることから都合よく生成することができ、デジタルデータキーを使用して、大容量記憶媒体２６に保存されているデジタル目標データとマッチングを行う必要はないことに留意されたい。代替として、デジタルデータキーを大容量記憶媒体２６から読み取ったデジタル目標データのストリームとマッチングさせることによって、相関ステップ８２を実行することができる。データキーが近似的情報の包含を反映し得ること、または同様なことが可能となるように再構成可能論理デバイス２１をプログラムできることに留意されたい。したがって、データキーを大容量記憶媒体から読み取った目標データと相関させることによって、近似マッチング機能が可能になる。
【００４８】
図９に戻ると、次に判断ロジック８４が、目標データの一部がデータキーと近似的にマッチしているか、または近似的にもマッチしていないかについて知的な判断を行う。マッチが見つかった場合、ステップ８６に示すように、目標データは処理され、検索照会によって要求されたキーデータが、ディスクキャッシュ３０にもしくは直接システムバス３４に送られ、またはバッファされ、または図１および図６〜図８に示すようにＣＰＵ３２、ネットワークインタフェース３６などから利用可能にされる。「ｄｏ」ループなどを示す論理ステップ８８が、大容量記憶媒体２６から目標データを連続的に読み取るステップに復帰するために好ましくは含まれる。しかし、これは連続的プロセスであり、目標データは、大容量記憶媒体２６からのストリームとして処理され、個々の塊り、フレーム、バイト、またはデータのその他の所定部分として処理されるのではないことを理解されたい。このようなことは不可能ではないが、本発明は好ましくは、大容量記憶媒体２６から目標データを読み取る際に滞りが起きないように、連続的に変化する目標データ読み取り信号の上でデータキーを実質的に「滑らせる」ことを可能にする。どのようなマルチビットデータ構造の開始または終了とも読み取りを同期させる必要はなく、または目標データが大容量記憶媒体２６から読み取られて、「オンザフライ」で連続的に比較されるときに実行する必要があるその他のどのような中間ステップとも同期させる必要はない。最終的に、データアクセスはステップ９０で完了し、プロセスが完了する。
【００４９】
発明者らは、本明細書において、本発明をアナログ領域で事前にテストした。事前テストから得られたデータによって、本発明の動作性および有効性を実証する。具体的には、図１０は、読み／書きヘッドが１０ビットのデジタルデータキーを保存する磁気媒体を読み取った際に、読み／書きヘッドからのアナログ信号出力を測定したグラフ表現である。グラフに示されているように、アナログ信号には、当技術分野で知られているように、目標データがハードディスクなどの磁気媒体から読み取られる際に、読み／書きヘッドによって生成される真のアナログ信号を表すいくつかのピークがある。図１０に示す目盛りは、縦軸がボルトであり、横軸がマイクロ秒の１０分の１である。図１１には、目標データが磁気媒体のテスト部分に保存された疑似ランダムバイナリ列から読み取られる際に、やはり読み／書きヘッドによって生成されるアナログ信号を示す。読み取り信号は、このレベルで試験を行ったときには、理想的な方形波出力を提供しない。
【００５０】
図１２は、８ビットデータキーの約２ビットとディスクまたは磁気媒体の異なるロケーションに符号化された疑似ランダムバイナリ列から見つけ出した目標データの対応する２ビットとの間の重なりをより明確に示すために、横軸を拡大したグラフ表現である。
【００５１】
図１３は、データキーとハードディスクから連続的に読み取られる目標データとの比較を行う際に、連続的に計算される相関係数のグラフ表現である。この相関係数は、アナログ信号を高速でサンプリングし、従来技術の信号処理相関技法を用いることによって計算される。そのような技法の一例は、Ｈｏｉｎｖｉｌｌｅ、Ｉｎｄｅｃｋ、Ｍｕｌｌｅｒ、「Ｓｐａｔｉａｌ  Ｎｏｉｓｅ  Ｐｈｅｎｏｍｅｎａ  ｏｆ  Ｌｏｎｇｉｔｕｄｉｎａｌ  Ｍａｇｎｅｔｉｃ  Ｒｅｃｏｒｄｉｎｇ  Ｍｅｄｉａ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍａｇｎｅｔｉｃｓ、Ｖｏｌｕｍｅ  ２８、Ｎｏ．６、１９９２年１１月の中に見出すことができ、同文献の開示は、参照により本明細書に組み込まれる。読み取り、比較、および相関計算のための方法および装置の先行実施例は、米国特許第５７４０２４４号明細書など、共同発明者の１人の１つまたは複数の先行特許の中に見出すことができ、同特許の開示は、参照により本明細書に組み込まれる。上記特許は、本発明を実施するのに利用することができる装置および方法の例を示すが、本明細書の別の箇所で述べたように、その他の類似の装置および方法を同じように利用して、本発明の目的を達成することもできる。
【００５２】
図１３を参照すると、３２５マイクロ秒付近で、２００マイクロ秒付近で、１ボルトに達しようとする際立ったピークが現れており、データキーと目標データとの非常に近いマッチを示している。図１０にも、本発明の強力な態様であると考えられる、近似マッチングが発生した機会が示されている。図１３を詳しく眺めると、その他のより低いピークが相関係数に現れていることに留意されたい。したがって、判定ポイントとして閾値を０．４ボルトに設定した場合、１に達しようとする発生ピークがマッチまたは「ヒット」を表すばかりでなく、別の５つのピークも「ヒット」を表す。このようにして、特定の検索パラメータに適するように、係数値を望ましく調整または事前決定することができる。例えば、大量のテキストの中から特定の単語を検索する場合、より低い相関値は、当該単語は存在するが、スペルが誤っていることを表すことができる。
【００５３】
図１４に、先と同じ８ビットデータキーと先と異なる目標データセットとの間の相関係数の連続的計算を示す。再び、ピークが１ボルトに達しようとする１つのマッチが、２００マイクロ秒付近で見つかる。閾値をより低く設定した場合、さらなるヒットが目標データ中に見つかることにも留意されたい。
【００５４】
先に述べたように、本発明は、シーケンスマッチング検索を実行することもできる。図１５を参照すると、そうした検索を行うために再構成可能論理デバイス２０によって生成されるテーブル３８が示されている。具体的には、ｐ１、ｐ２、ｐ３、ｐ４は、データキーｐまたは所望の検索対象シーケンスを表す。図１５に示すデータキーは４文字であるが、説明の目的でそのようにしたに過ぎず、シーケンス検索用の一般的なデータキーサイズは、５００〜１０００のオーダ、またはそれ以上になることを理解されたい。シンボルｔ１、ｔ２、ｔ３、．．．、ｔ９は、大容量記憶媒体２６からストリーム送信される目標データｔを表す。やはり、高々９文字からなる目標データが示されているだけだが、大容量記憶媒体２６の一般的サイズ、したがって、そこからストリーム送信される目標データの一般的サイズは一般に、数１０億文字の範囲となり得ることを理解されたい。シンボルｄｉ，ｊは、データキー内の位置ｉと目標データ内の位置ｊとの編集距離を表す。データキーは目標データに比べて短いことが仮定されているが、必ずしもそうである必要はない。図１５には示されていない追加の行（ｄ０，ｊ）と列（ｄｉ，０）のために、１組の既知の（定数）値があってもよい。
【００５５】
ｄｉ，ｊの値は、ｄｉ，ｊが次の文字、すなわち、（１）ｐｉ、（２）ｔｊ、（３）ｄｉ−１，ｊ−１、（４）ｄｉ−１，ｊ、（５）ｄｉ，ｊ−１の関数に過ぎないという事実を用いて、再構成可能論理デバイス２０によって計算される。このことは、位置ｄ３，６を例にとり、それのｄ２，５、ｄ２，６、ｄ３，５の値、およびｐ３、ｔ６に対する依存性を示すことによって、図１５に図示されている。本発明の一実施形態では、ｄｉ，ｊの値は、以下のようにして計算される。
ｄｉ，ｊ＝ｍａｘ［ｄｉ，ｊ−１＋Ａ；ｄｉ−１，ｊ＋Ａ；ｄｉ−１，ｊ−１＋Ｂｉ，ｊ］
【００５６】
ただし、Ａは定数であり、Ｂｉ，ｊはｐｉとｔｊの表関数である。しかし、関数の形式は、まったく任意とすることができる。生物学関連の文献では、Ｂは評価関数と呼ばれる。よく利用されるデータベース検索プログラムＢＬＡＳＴでは、評価は単にｐｉ＝ｔｊであるかどうかの関数である。アミノ酸配列など、別のコンテキストでは、Ｂの値はｐおよびｔの中の具体的な文字に依存する。
【００５７】
図１６に、図１５のテーブル３８内の値を計算するために本発明によって使用される、シストリックアレイ構成の一実施形態を示す。データキーの文字は、データレジスタ５３の列に格納され、一方、大容量記憶媒体２６からストリーム送信される目標データの文字は、データシフトレジスタ５５に格納される。ｄｉ，ｊの値は、好ましくはＦＰＧＡとするシストリックセル５９に格納される。
【００５８】
図１６のアレイの動作について、図１７と図１８を用いて、次に説明する。図１７に示すように、システムのクロックサイクルの第１の（すなわち、組合せ）パートにおいて、下線を引いた４つの値が計算される。例えば、新しい値ｄ３，６は、図１５で先に説明したのと同じ５つの値に依存することが示されている。図１８に示すように、クロックサイクルの第２の（すなわち、ラッチ）パートにおいて、ｄｉ，ｊ内およびｔｊ内のすべての文字が、右隣の位置にシフトさせられる。比較器６１は、ｄアレイの各対角セルに配置され、閾値が超えられたかどうかの判定を行う。
【００５９】
シーケンスマッチング動作について、図１９〜図２２を参照し、以下の例を用いて、次に説明する。
【００６０】
キー＝ａｘｂａｃｓ
目標データ＝ｐｑｒａｘａｂｃｓｔｖｑ
Ａ＝１
Ｂ＝２、ｉ＝ｊの場合
Ｂ＝−２、ｉ＝ｊの場合
これらの変数から、図１９のテーブルが、再構成可能論理デバイス２０によって生成される。事前決定された閾値を「８」と仮定すると、再構成可能論理デバイス２０は、ｄ６，９でマッチを認識する。
【００６１】
図１６〜図１８に示す合成アレイの部分に、上記の例の値を当てはめた図を、図２０〜図２２にそれぞれ示す。マッチは、いずれかの列の値が所定の閾値を超えた場合に、再構成可能論理デバイス２０によって識別される。閾値は、データキーと大容量記憶媒体２６に保存された目標データとにどの程度の類似性を求めるかに基づいて設定される。例えば、正確なマッチ検索の場合、データキーと目標データとは一致しなければならない。マッチは、図１９のテーブルを用いたトレースバック操作を介して、ＣＰＵ３２によって検査される。具体的には、マッチが識別されると、トレースバック操作を支援するため、テーブルの「スナップショット」が、所定の時間間隔でＣＰＵ３２に送られる。時間間隔は、ＣＰＵ３２に負荷を掛け過ぎないよう、あまり頻繁でないのが好ましいが、テーブルの再生成に多くの時間と処理が必要とならないよう、あまり低頻度にもしない。ＣＰＵ３２がトレースバック操作を実行できるようにするため、閾値を超えるテーブル内のエントリを取り巻く領域でｄアレイを再生成できなければならない。この要件を支援するため、シストリックアレイは、定期的にｄの完全な列の値（「スナップショット」）をＣＰＵ３２に出力することができる。これによって、ＣＰＵ３２は、スナップショットのインデックスｊよりも大きなｄの必要部分を再生成できる。
【００６２】
多くのマッチングアプリケーションは、画像など２次元エンティティを表すデータに対して機能する。図２３に、２次元データでマッチを可能にする、好ましくはＦＰＧＡとする、再構成可能論理デバイス２０のシストリックアレイ１２０を示す。個々のセル１２２はそれぞれ、ユーザがマッチさせたい画像（画像キー）の１つのピクセルと、検索対象画像（目標画像）の１つのピクセルを保持する。十分に大きなサイズの画像の場合、おそらく画像の全部は、１つの再構成可能論理チップ１２４に収まらないであろう。そのような場合に、セルをチップに区分化した一例を破線で囲って示してあり、各チップ１２４には、セルの長方形のサブアレイが含まれる。チップ間の接続数は、正方形のサブアレイ（すなわち、縦横同数のセル）を用いることによって、最小にすることができる。その他のより複雑な構成を以下に示す。
【００６３】
アレイ１２０への目標画像のロードについて、図２４を用いて説明する。一般にポイントＡとして示される大容量磁気媒体２６からストリーム送信される各目標画像の個々の行は、各セルを接続する水平リンク１３４を介して、アレイの最上部の行１３０にロードされる。こうした構成を用いた場合、最上部の行１３０は、データシフトレジスタとして動作する。行１３０の全体にロードが行われると、この行は、各列に示された垂直リンク１３６を介して、次の行１３２にシフトダウンされる。画像全体がアレイにロードされた後、近傍セル間での任意の通信を必要とする比較操作が実行される。これは、図２３に示された水平双方向リンク１２６および垂直双方向リンク１２８によって支援される。
【００６４】
簡略化の目的で、図２３および図２４では、個々の双方向リンク１２６、１２８は簡単に示されているが、図２８には、はるかに複雑な双方向リンクの組を柔軟に実装可能であることが示されている。図２８に示すように、データは、大容量記憶媒体１８０から伝送され、複数のセル１８２からなる第１の行に入力される。第１の行の各セルは、セルからなる第２の行の中の下側の対応セル１８４への直接リンクを単純なリンク１８６によって有し、このような関係は、セルからなるアレイ１８８の全体に及ぶ。セルからなるアレイ１８８は、中間セルを介した送信を必要とせずにアレイ内の任意の２つのセルを直接接続する、コネクタウェブ１９０によって覆われる。アレイ１８８の出力は、アレイ１８８の下部における、出口リンク１９２の和として表される。アレイ内の各セルは、ＦＰＧＡで構成することができ、その各々が、図１の要素２０に対応する再構成可能論理要素を有し、またはそのいずれか１つが、再構成可能論理要素２０およびデータシフトレジスタ２４を有することができ、またはそのいずれか１つが、再構成可能論理要素２１の全体を有することができることを理解されたい。
【００６５】
図２５に、アレイ１２０の個々のセルに関する一実施形態を示す。セル１４０は、現在アレイにロードされている目標画像のピクセルを格納する、ピクセルレジスタ１４２  ＬＯＡＤＴｉ，ｊを含む。レジスタ１４４  ＣＭＰＴｉ，ｊは、目標画像が完全にロードされた後に、ピクセルレジスタ１４２のコピーを格納する。この構成によって、最後にロードされた目標画像を次の目標画像とパラレルに比較することができ、ロード、比較、ロード、比較といったパイプライン化されたシーケンスが実質的に確立される。レジスタ１４６  ＣＭＰＰｉ，ｊは、比較の目的で使用される画像キーのピクセルを格納し、比較ロジック１４８は、レジスタ１４４とレジスタ１４６の間でマッチング操作を実行する。比較ロジック１４８は、複雑なマッチング機能が可能となるように、一般に１５０、１５２、１５４、１５６でそれぞれ示される左、右、上、下の近傍セルと通信を行う能力を備えている。
【００６６】
図２６に、図２３のアレイ１２０の個々のセルに関する別の実施形態を示す。画像キーおよび目標画像の同時ロードを支援するため、図２５のセル１４０が増強されている。具体的には、セル１６０は、セル１４０と同じ構成要素を含むが、その他に、画像キーをロードするのに使用される、レジスタ１４２と同じように動作する新しいレジスタ１６２  ＬＯＡＤＰｉ，ｊが追加される。こうした構成を用いた場合、大容量記憶媒体２６の第１のディスク読み取りヘッドが、画像キーの上に位置付けられ、第２のディスク読み取りヘッドが、目標画像の上に位置付けられた場合、その両方をパラレルにディスクから読み出して、同時にアレイ１６０にロードすることができる。
【００６７】
比較論理ブロック内で実行される操作は、目標画像と画像キーの間に著しい相違があるかどうかに関する判断を提供する、任意の機能とすることができる。その一例として、Ｊｏｈｎ  Ｃ．  Ｒｕｓｓ、「Ｔｈｅ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ  Ｈａｎｄｂｏｏｋ，  ３ｒｄ  ｅｄｉｔｉｏｎ」、ＣＲＣ  Ｐｒｅｓｓ、１９９９年に記載されているような、画像全体または画像の部分領域にわたる相互相関を挙げることができ、同書は、参照により本明細書に組み込まれる。
【００６８】
本発明は、データ削減検索を実行することもできる。そのような検索は、本明細書で先に説明したマッチング機能を含むが、その他に、マッチしたデータを何らかの集約形式に要約する機能も含む。例えば、金融業界においては、株式の最安値、最高値、および最新価格を識別する金融情報を検索したいことがある。図２７に、そのような集約データ削減を計算するための再構成可能論理デバイス１００を示す。この図において、データシフトレジスタ１０２は、株価情報を格納する大容量記憶媒体から目標データを読み取る。図示の例では、３種類のデータ削減検索、すなわち、最安値、最高値、および最新価格の計算が示されている。目標データがデータシフトレジスタ１０２に供給されると、判断ロジックが、所望のデータ削減操作を計算する。具体的には、株価が最安値比較器１１０および最高値比較器１１２に供給され、そこに格納される。株価が比較器１１０に供給されるたび、比較器１１０は、最後に格納した株価と今供給された株価とを比較して、より安い価格をデータレジスタ１０４に格納する。同様に、株価が比較器１１２に供給されるたび、比較器１１２は、最後に格納した株価と今供給された株価とを比較して、より高い価格をデータレジスタ１０６に格納する。最新価格を計算するには、株価をデータレジスタ１０８に供給し、現在時刻を比較器１１４に供給する。時刻値が比較器１１４に供給されるたび、比較器１１４は、最後に格納した時刻値と現在時刻とを比較して、より新しい時刻値をデータレジスタ１１６に格納する。計算が行われる所望の時間間隔の最後に、最新価格が決定される。
【００６９】
図２７に示す非常に簡単な金融の例に関して、データ削減検索を説明したが、本発明が、そのような機能を必要とする様々な複雑性をもつ様々な異なる適用分野で、データ削減検索を実行できることは理解されよう。再構成可能論理デバイスは、必要な機能を実行するように、ハードウェアおよび／またはソフトウェアによって構成しさえすればよい。
【００７０】
ディスクの回転速度でデータ削減検索を実行する能力を、過小に評価することはできない。情報の最も価値ある側面の１つは、適時性である。人々は、物事にインターネットのスピードを期待するようになっている。集約データ削減を素早く計算できる企業は、それができない他企業に対して、明らかに競争的優位に立つことができる。
【００７１】
本発明に様々な変更および修正を施し得ることは、当業者には明らかであろうが、それでも、それらが本発明の主旨から逸脱することはない。好ましい実施形態によって、本発明の実施を説明してきたが、その説明は、単なる例示を意図したものに過ぎない。複数の代替形態も上で提示した。例えば、アナログ処理によって例示された操作のすべては、デジタル領域にも等価の対応する操作をもつ。したがって、各タイプの近似マッチングおよび相関処理は、アナログビットパターンの標準的なデジタル表現に対して実行することができる。これはまた、既成のデジタルロジック、マイクロプロセッサ、およびデジタル信号プロセッサ、またはそれらの選択的組合せを用いて、連続的に実現することもできる。したがって、本発明は本明細書に添付の特許請求の範囲およびその法的均等物によってのみ限定されることを、発明者らは意図している。
【図面の簡単な説明】
【００７２】
【図１】本発明の一実施形態による情報探索および検索システムを示すブロック図である。
【図２】本発明を接続するための異なる挿入ポイントを示した従来の柔軟性の乏しいディスクドライブシステムを示す概略図である。
【図３】図１のシステムによって処理される検索照会の変換の一実施形態を示すブロック図である。
【図４】デジタル領域で正確なマッチ検索を行うのに使用される本発明のハードウェア実装の一実施形態を示すブロック図である。
【図５】デジタル領域で近似マッチ検索を行うのに使用される本発明のハードウェア実装の一実施形態を示すブロック図である。
【図６】スタンドアロン構成における本発明の実装を示すブロック図である。
【図７】ネットワークを介する共用リモート大規模記憶装置として実装される本発明を示すブロック図である。
【図８】ネットワーク接続記憶装置（ＮＡＳＤ）として実装される本発明を示すブロック図である。
【図９】磁気記憶媒体からデータを探索および検索するための本発明の方法における論理ステップの詳細を示すフローチャートである。
【図１０】データキーとして使用されうるアナログ信号を示すグラフ表現である。
【図１１】データキーが存在する磁気記憶媒体から連続的に読み取られたデータを表すアナログ信号を示すグラフ表現である。
【図１２】図１１の信号に図１０の信号を重ね、マッチングさせた様子を示すグラフ表現である。
【図１３】磁気記憶媒体中の目標データをスキャンし、データキーと比較する際に連続的に計算された相関関数を示すグラフ表現である。
【図１４】磁気記憶媒体から読み取られた、やはりデータキーを含む目標データの異なる組による信号とデータキーを連続的に比較した際の相関関数を示すグラフ表現である。
【図１５】シーケンスマッチング操作を実行する際に使用される、本発明によって生成されたテーブルの一実施形態を示す図である。
【図１６】図１５のテーブルの値を計算するために本発明によって使用される、シストリックアレイ構成の一実施形態を示すブロック図である。
【図１７】図１のシステムのクロックサイクルの組合せパートで動作中の図１５のシストリックアレイ構成を示すブロック図である。
【図１８】図１のシステムのクロックサイクルのラッチパートで動作中の図１５のシストリックアレイ構成を示すブロック図である。
【図１９】具体的なシーケンスマッチング例を示した図１５のテーブルを示す図である。
【図２０】図１９の例の下で図１６のシストリックアレイ構成を示すブロック図である。
【図２１】図１のシステムのクロックサイクルの組合せパートで動作中の図２０のシストリックアレイ構成を示すブロック図である。
【図２２】図１のシステムのクロックサイクルのラッチパートで動作中の図２０のシストリックアレイ構成を示すブロック図である。
【図２３】画像マッチング操作を実行する際に本発明によって使用されるシストリックアレイ構成の一実施形態を示すブロック図である。
【図２４】画像マッチング操作を実行するシストリックアレイ構成の別の構成を示すブロック図である。
【図２５】図２３に示すシストリックアレイの個別セルの一実施形態を示すブロック図である。
【図２６】図２３に示すシストリックアレイの個別セルの別の実施形態を示すブロック図である。
【図２７】データ削減操作を実行するために本発明を用いた一例を示すブロック図である。
【図２８】ＦＰＧＡのより複雑な構成を示すブロック図である。
【図１】
2005527043.tif 000003
【図２】
2005527043.tif 000004
【図３】
2005527043.tif 000005
【図４】
2005527043.tif 000006
【図５】
2005527043.tif 000007
【図６】
2005527043.tif 000008
【図７】
2005527043.tif 000009
【図８】
2005527043.tif 000010
【図９】
2005527043.tif 000011
【図１０】
2005527043.tif 000012
【図１１】
2005527043.tif 000013
【図１２】
2005527043.tif 000014
【図１３】
2005527043.tif 000015
【図１４】
2005527043.tif 000016
【図１５】
2005527043.tif 000017
【図１６】
2005527043.tif 000018
【図１７】
2005527043.tif 000019
【図１８】
2005527043.tif 000020
【図１９】
2005527043.tif 000021
【図２０】
2005527043.tif 000022
【図２１】
2005527043.tif 000023
【図２２】
2005527043.tif 000024
【図２３】
2005527043.tif 000025
【図２４】
2005527043.tif 000026
【図２５】
2005527043.tif 000027
【図２６】
2005527043.tif 000028
【図２７】
2005527043.tif 000029
【図２８】
2005527043.tif 000030
【国際調査報告】
2005527043.tif 000031
2005527043.tif 000032
2005527043.tif 000033
2005527043.tif 000034
2005527043.tif 000035
2005527043.tif 000036
2005527043.tif 000037