(57)【要約】ここに開示するのは、連想式で近似式の、データベースのアナログ又はデジタル走査のための方法とデバイスであり、これによって、大容量記憶媒体からデータを非同期式でアクセスできる。本発明は、大容量記憶媒体レベルにおける専用のアナログ／デジタル回路及び判断論理を提供するが、これによって、関心のあるデータを識別するキーを決定するステップと、近似整合又は正確整合回路でこのキーを大容量記憶媒体からのデータの読み取り値に基づいて発生された信号と連続的に比較して、パターンの整合を決定するステップと、キーとデータとの間の相関値を、このデータが連続的に読み出されるにつれて決定するステップと、この相関値に対する事前選択されたしきい値に基づいて整合を決定するステップと、を含む。このパターン整合技法は、データを、その真性の構造体又は値に基づいて比較するいかなる必要性をも解消し、その代わりに、アナログパターン又はデジタルパターンに基づいて比較する。これらのキーとデータは、アナログ値であってもデジタル値であってもよい。このデバイスと方法は、ネットワーク接続型記憶デバイスとして実現されるスタンドアローン型コンピュータシステムの１部として、さもなければ、コンピュータＬＡＮ又はＷＡＮの１部として提供されるものである。
2004502996.tif 000002
【特許請求の範囲】
【請求項１】
記憶媒体に接続された近似整合／プリフェッチプロセッサを備えたデータ記憶デバイス。
【請求項２】
前記近似整合／プリフェッチプロセッサが、前記記憶媒体に接続された近似整合ユニットと、前記近似整合ユニットに接続された論理デバイスとを含む請求項１に記載のデータ記憶デバイス。
【請求項３】
前記論理デバイスがデータプロセッサを含む請求項２に記載のデータ記憶デバイス。
【請求項４】
前記論理デバイスがデジタルデータプロセッサを含む請求項３に記載のデータ記憶デバイス。
【請求項５】
前記デジタルデータプロセッサが、別のデジタルデータプロセッサからの検索照会を受け入れ、前記検索照会を解釈して翻訳し、これによって関連するキーを決定し、検索照会と前記決定されたキーを前記近似整合ユニットに送信するようにプログラムされたマイクロプロセッサを含む請求項４に記載のデータ記憶デバイス。
【請求項６】
前記デジタルデータプロセッサが、別のデジタルデータプロセッサからの検索照会を受け入れ、前記検索照会を解釈して翻訳し、これによって関連するキーを決定し、検索照会と前記決定されたキーを前記近似整合ユニットに送信するようにプログラムされたプログラム可能論理デバイスを含む請求項４に記載のデータ記憶デバイス。
【請求項７】
前記近似整合ユニットが、前記決定されたキーを前記記憶媒体から読み出されたデータと比較して、それらの間の整合を決定する比較器を含む請求項５に記載のデータ記憶デバイス。
【請求項８】
前記近似整合ユニットが、前記決定されたキーを前記記憶媒体から読み出されたデータと比較して、それらの間の整合を決定する比較器を含む請求項６に記載のデータ記憶デバイス。
【請求項９】
大容量記憶媒体からデータを検索する検索デバイスであり、前記検索デバイスが、検索されることが求められるデータを表す決定済みキーを、前記大容量記憶媒体から読み出されたデータから成る連続ストリームを表すデータ信号と比較する整合回路を含み、前記決定済みキーが、前記データ自身を表すアナログ信号であり、前記データ信号もまたアナログ信号である検索デバイス。
【請求項１０】
前記検索デバイスに接続されて、別のプロセッサによってアクセスされる前記検索されたデータを記憶するメモリをさらに備える請求項９に記載の検索デバイス。
【請求項１１】
前記検索デバイスが前記大容量記憶媒体と直接カップリングされ、また、前記大容量記憶媒体をプロセッサとインタフェースさせて前記検索済みデータの処理を所望する請求項９に記載の検索デバイス。
【請求項１２】
大容量記憶媒体からデータを検索する検索デバイスであり、前記検索デバイスが前記大容量記憶媒体と直接カップリングされ、また、前記大容量記憶媒体をプロセッサとインタフェースさせて前記検索済みデータの処理を所望し、前記検索デバイスが、検索されることが求められるデータを表す決定されたキーと前記大容量記憶媒体から読み出されたデータから成る連続ストリームを表すデータ信号との間のパターン比較を実行する整合回路を備える検索デバイス。
【請求項１３】
前記検索デバイスに接続されて、前記プロセッサによってアクセスされる前記検索されたデータを記憶するメモリをさらに備える請求項１２に記載の検索デバイス。
【請求項１４】
前記整合回路がデジタルキーをデジタルデータ信号と整合させるように構成されている請求項１２に記載の検索デバイス。
【請求項１５】
前記整合回路にカップリングされた複数の大容量記憶媒体をさらに備える請求項１４に記載の検索デバイス。
【請求項１６】
前記整合回路がアナログ信号キーをアナログデータ信号と整合させるように構成されている請求項１２に記載の検索デバイス。
【請求項１７】
前記整合回路にカップリングされた複数の大容量記憶媒体をさらに備える請求項１６に記載の検索デバイス。
【請求項１８】
大容量記憶媒体からデータを検索する検索デバイスであり、前記検索デバイスが前記大容量記憶媒体と直接カップリングされ、また、前記大容量記憶媒体をコンピュータネットワークとインタフェースさせて、前記検索済みデータの処理を所望し、前記検索デバイスが、検索されることが求められるデータを表す決定されたキーと前記大容量記憶媒体から読み出されたデータから成る連続ストリームを表すデータ信号との間のパターン比較を実行する近似整合回路を備える検索デバイス。
【請求項１９】
前記検索デバイスに接続されて前記コンピュータネットワークによってアクセスされる前記検索されたデータを記憶するメモリをさらに備える請求項１８に記載の検索デバイス。
【請求項２０】
主プロセッサと、作業メモリと、補足メモリと、近似整合／プリフェッチプロセッサとを有するコンピュータにおいて、前記プリフェッチプロセッサが前記補足メモリと直接カップリングされ、前記補足メモリから検索されることを求められるデータを表す決定されたキーを前記補足メモリから読み出されたデータから成る連続ストリームを表すデータ信号と整合させるように構成されている、コンピュータ。
【請求項２１】
主プロセッサと、作業メモリと、補足メモリと、前記補足メモリにカップリングされて、キーを前記補足メモリから読み出されたデータから成る連続ストリームとパターン整合させる回路とを有するコンピュータ。
【請求項２２】
ネットワーク接続型大容量記憶デバイス（ＮＡＳＤ）であり、前記ＮＡＳＤが近似整合／プリフェッチプロセッサにカップリングされた大容量記憶デバイスを備え、また、前記ＮＡＳＤが、データ照会を受信し、それに対して応答するネットワークアドレス指定可能入力／出力ポートを有するＮＡＳＤ。
【請求項２３】
ネットワーク接続型大容量記憶デバイス（ＮＡＳＤ）であり、前記ＮＡＳＤがキーを後出の大容量記憶メモリから読み出されたデータから成る連続ストリームとパターン整合させる回路にカップリングされた大容量記憶デバイスを備え、また、前記ＮＡＳＤが、データ照会を受信し、それに対して応答するネットワークアドレス指定可能入力／出力ポートを有するＮＡＳＤ。
【請求項２４】
大容量記憶媒体からデータを検索する方法であり、前記方法が、
前記大容量記憶媒体用のプロセッサから検索コマンドを受信するステップと、
前記大容量記憶媒体から検索されることが所望されるデータを表すキーを決定するステップと、
前記キーと前記大容量記憶媒体から読み出されたデータから成る連続ストリームを表すデータ信号とのパターン比較を実行するステップであり、前記キーは、いかなる特定のデータ構造体をも表すことはなく、また、前記データが前記大容量記憶デバイス中に記憶されているのと同じ構造体であるとは必ずしも限らないステップと、
どのデータが前記キーと整合するかを決定するステップと、
を含む方法。
【請求項２５】
どのデータがキーと整合するかを決定する前記ステップが、前記データと前記キーとの近似整合を決定するステップから成る請求項２４に記載の方法。
【請求項２６】
前記キーを前記データ信号と連続的に相関させて整合を決定するステップをさらに含む請求項２４に記載の方法。
【請求項２７】
キーを決定する前記ステップが、記憶媒体上で前記キーに対応するデータを書き込む及び読み出すステップをさらに含む請求項２４に記載の方法。
【請求項２８】
前記キーがアナログ信号である請求項２４に記載の方法。
【請求項２９】
前記キーがデジタル信号である請求項２４に記載の方法。
【請求項３０】
キーを決定する前記ステップが前記キーに対応する信号をデジタル化するステップをさらに含む請求項２４に記載の方法。
【請求項３１】
インテリジェント型大容量記憶媒体デバイスであり、前記デバイスが、キーとデータ記憶媒体からの連続的読み出しデータを表す信号との間でパターン比較する回路を有するデバイス。
【請求項３２】
前記パターン比較回路が近似整合ユニットにカップリングされた近似整合／プリフェッチプロセッサを含む請求項３１に記載のデバイス。
【請求項３３】
前記検索デバイスに接続されて、別のプロセッサによってアクセスされる前記検索されたデータのデジタル表示内容を記憶するメモリをさらに備える請求項９に記載の検索デバイス。
【請求項３４】
大容量記憶媒体からデータを検索する検索デバイスであり、前記検索デバイスが、検索されることが求められるデータを表す決定済みキーを、前記大容量記憶媒体から読み出されたデータから成る連続ストリームを表すデータ信号と比較する整合回路を含み、前記決定済みキーが前記データ自身のデジタル表示物であり、前記データ信号もまたデジタル信号である検索デバイス。
【請求項３５】
前記検索デバイスに接続されて、別のプロセッサによってアクセスされる前記検索されたデータを記憶するメモリをさらに備える請求項３４に記載の検索デバイス。
【請求項３６】
前記検索デバイスが前記大容量記憶媒体と直接カップリングされ、また、前記大容量記憶媒体をプロセッサとインタフェースさせて前記検索済みデータの処理を所望する請求項３４に記載の検索デバイス。
【請求項３７】
前記近似整合／プリフェッチプロセッサが近似整合ユニットを含み、前記記憶媒体が少なくとも１つの記憶表面を含み、デジタルデコーダが前記表面の出力部を持つ回路内にあり、前記近似整合ユニットが前記記憶表面と前記デジタルデコーダ間に接続される請求項１に記載のデータ記憶デバイス。
【請求項３８】
前記近似整合／プリフェッチプロセッサが近似整合ユニットを含み、前記記憶媒体が少なくとも１つの記憶表面を含み、デジタルデコーダが前記表面の出力部を持つ回路内にあり、前記近似整合ユニットが前記デジタルデコーダの出力部に接続される請求項１に記載のデータ記憶デバイス。
【請求項３９】
前記近似整合／プリフェッチプロセッサが近似整合ユニットを含み、前記記憶媒体が少なくとも１つの記憶表面を含み、デジタルデコーダが前記表面の出力部を持つ回路内にあり、誤差補正回路が前記デジタルデコーダの出力部を持つ回路内にあり、前記近似整合ユニットが前記誤差補正回路の出力部に接続される請求項１に記載のデータ記憶デバイス。
【請求項４０】
前記整合回路がデジタルキーをデジタルデータ信号に近似的に整合させるように構成される請求項１２に記載の検索デバイス。
【請求項４１】
前記整合回路がアナログ信号キーをアナログデータ信号に近似的に整合させるように構成される請求項１２に記載の検索デバイス。
【請求項４２】
主プロセッサと、作業メモリと、補足メモリと、近似整合／プリフェッチプロセッサとを有するコンピュータにおいて、前記プリフェッチプロセッサが前記補足メモリと直接カップリングされ、前記補足メモリから検索されることを求められるデータを表す決定されたキーを前記補足メモリから読み出されたデータから成る連続ストリームを表すデータ信号と近似的に整合させるように構成されているコンピュータ。
【発明の詳細な説明】
【０００１】
連想メモリデバイスが先行技術において周知である。一般に、これらの連想メモリデバイスには、コンピュータやネットワークなどに同期して動作し、また、特殊化された検索の効率を増大させる、コンピュータ、コンピュータネットワークおよびそれに類するもののための周辺メモリが含まれる。加えて、先行技術においては、これらのメモリデバイスは、周辺メモリにアクセスするに際して主ＣＰＵに対する支援としてある種の制限された意志決定ロジックを含むことがあることも知られている。高速のディスクやドラムなどの回転メモリと共に使用するのに特に適しているこのような連想メモリデバイスの例が米国特許第３，９０６，４５５号に見受けられ、その開示内容は参照してここに組み込まれる。この特定のデバイスは回転メモリと共に使用するスキームを提供し、このデバイス上でのいかなる論理演算の実行にも先だってメモリを事前ソーティングし、次にソーティングするためにはメモリセクタ上で２つのパスが必要であることを教示している。したがって、このデバイスは、磁気テープやそれに類するものなどの線形メモリ又は直列メモリと共に使用するには適していないことが教示される。
【０００２】
先行技術によるデバイスの他の例はまた米国特許第３，７２９，７１２号、第４，４６４，７１８号、第５，０５０，０７５号、第５，１４０，６９２号、及び第５，７２１，８９８号に見受けられ、その開示内容は参照してここに組み込まれる。
【０００３】
例えば米国特許第４，４６４，７１８号では、ディクソン（Ｄｉｘｏｎ）は、固定されたバイト数に対して固定比較を実行している。これは、データに対して任意に走査して相関させる機能を有していない。それは、所与のディスクシリンダ中のトラックに沿って直列に検索するが、ディスク全体にわたって並行に検索する機能はない。ディクソンの比較は、一定の変化し得ない数の標準論理演算のタイプの数により制限される。加えて、そこに提示されている回路は、これらの単一の論理演算しかサポートしない。近似整合やファジー整合は何らサポートされていない。
【０００４】
これらの先行技術による連想メモリデバイスは、多くの場合大容量記憶メモリデバイスである周辺メモリとの間での情報の入力と出力の速度を増す試みを提示するものではあるが、これは全て、メモリロケーションのデジタル式のアドレスか又は内容を読み出して解釈することによってデジタル形式で記憶されているデータに古典的な手法でアクセスするという操作に依存している。言い換えれば、このようなデバイスは、ほとんどが、データをそのアドレスでアクセスするが、技術上よく知られているように内容をアドレス指定するという能力を利用するデバイスも存在する。にもかかわらず、本発明者に知られているこれらの先行技術の全てにおいて、アドレス又はアドレス指定されたロケーションに蓄えられているデータのデジタル値は、そのデータを識別して次にそれを処理するように選択するためには、そのデジタル形態で読み出して解釈しなければならない。そうすると、そのアドレス又は内容が表すデジタルデータを読み出して解釈する処理時間が必要となるだけではなく、アクセス回路が、記憶されているデータの構造体に従ってメモリを処理する必要性が必然的に生じる。言い換えれば、データがオクテットで記憶されていれば、アクセス回路は、データにオクテットでアクセスしてそれを増分式に処理しなければならない。この「スタートストップ」処理は、データのアクセスに要する入力／出力時間を増す作用がある。また技術上よく知られているように、この入力／出力時間は、一般的には、いかなるコンピュータ又はコンピュータネットワークにおいても処理能力の妨げであり実効的な制限となっている。
【０００５】
先行技術におけるこれらの問題及び他の問題を解決するために、本発明者はここに、連想メモリのための方法と装置の設計と開発に成功したが、そのいくつかの実施形態は、これらの先行技術の限界に対する洗練された簡単な解決策を提供し、また、大容量記憶メモリに記憶されているデータのアクセス時間を大幅に減少させるものである。既述したように、本発明は、個々が固有の利点を持ついくつかの実施形態を有するものである。
【０００６】
一般的に、本発明は、データをそれが大容量記憶媒体上に記憶されている状態で連続的に読み出された内容とデータキーを近似的に整合させることによってデータを検索する技法として説明される。その最も広範囲にわたる、そしてたぶん最も強力な実施形態において、このキーは、アナログ信号であり、それは、一般的な読み出し／書き込みデバイスが、自身が大容量記憶媒体を走査しながら発生したアナログ信号を整合される。言い換えれば、先行技術では必要であると教示される、大容量記憶媒体に記憶されているデジタルデータのアナログ表示を読み出すだけではなくその信号を比較する前にそのデジタル形式に変換するステップが解消される。さらに、そのデータを、データが編成されて記憶されていた構造又は形式を利用することによって「フレーミング」したり比較したりする必要がない。アナログ信号の場合、指定する必要があるのは、「読み出し」信号のそれに対応する、そして連続的に変化する選択された時間部分との比較に用いられるその信号の経過時間だけである。先行技術で知られている多くの標準の相関技法の内のどの１つを用いても、データ「キー」は、整合していることを判断するためにデータ信号が滑る「ウインドウ」に近似的に整合される。重要なことは、同じ量のデータを、遙かに迅速に走査可能であり、また、検索要求と整合するデータをこれまた遙かに迅速に決定することが可能であるという点である。本発明者は、２００メガバイトのＤＮＡシーケンスをＣＰＵベースで近似検索すると、データベースを索引するオフライン処理が既に完了していると仮定しても、一般的な現在の「ハイエンド」システムでは最大で１０秒かかりかねないことを発見した。この同じ１０秒で、本発明を用いると、１０ギガバイトのディスクを磁気的に検索して近似的に整合させることが可能であることを発見した。これは、性能が５０：１倍に向上したことを意味する。さらに、一般的にハードディスクドライブでは、４つの表面とそれに対応する読み出し／書き込みヘッドが存在するが、これらは、ヘッドが個々に本発明を装備していればすべてを並行して検索することが可能である。これらの検索はすべて同時並行に進行し得るので、速度や性能という点では総合的に２００：１倍という利点となる。さらに、ハードディスクドライブを追加しても、それを並行にアクセスして拡張することによって、本発明による利点をさらに向上させることができる。
【０００７】
適切な相関技法又は整合技法を選択することによって、また、適切なしきい値を設定することによって、検索を実行して所望の信号を正確に整合させることが可能であり、また、より重要でおそらくより効果的なことには、このしきい値を下げて近似的整合検索が可能となることである。これは一般的にはより効果的な検索モードと考えられているが、それは、データベースを走査して、データが単に捜索されているものと近似しているだけでも有効である「ヒット」を発見し得るからである。これによって、改竄されたデータや、不正確に入力されたデータや、単に概略的にカテゴリに対応するだけのデータを発見するための検索や、多くの応用分野で高度に必要とされている他の種類のデータ検索が可能となる。例えば、ＤＮＡシーケンスのライブラリはその検索が望まれており、所望の残余シーケンスに近似的に整合するヒットが発見されることが望まれている。これによって、所望のシーケンスに近いシーケンスが発見されて捨てられることがなく、残余の不整合の誤差も許容範囲内の数値であるようにすることが保証される。別の応用分野では、インターネットがインターネット検索エンジンで検索される。このような検索においては、含まれていることが予想されるミススペルされた語や、別のスペルの語や、その他の変形に対する近似検索が、検索を無効にすることなく、また、組み合わせ数回の特殊検索を必要とすることなく実行されることになる。この技法によって、検索エンジンは、任意の検索に対してより多くのヒットを提供し、また、より多くの関連Ｗｅｂページが検索によって発見されてカタログ化されることが保証される。
【０００８】
本発明による別の考えられる応用分野は、膨大なサイズと成りかねない又はアナログ表示内容となりかねないデータベースにアクセスする場合である。例えば、我々の社会は、音声記録デバイスの実現と、裁判議事録を含む多くのフォーラムにおけるその使用の歴史であった。最近でも、米国大統領執務室でなされたテープ記録が、弾劾公聴会におけるその重要性が増している。理解され得るように、大統領任期の数年間にわたるテープ記録は、巨大なデータベースとして蓄積され、これが、多くの人間を要して実際に聞かせて、関心事となりかねない特定の言葉が話された事例を発見する必要性が生じ得る。本発明を利用すれば、データベースを連続して、また、高速で走査しながら、話された言葉のアナログ表示内容をキーとして用いて、整合するかどうか調査することが可能である。したがって、本発明は、大容量のアナログデータベース及び大容量のデジタルデータベースのための強力な検索ツールを提供する。
【０００９】
テキストベースの検索は、上記のように本発明によって対処されるが、映像、音声及び他の表示内容を含む記憶媒体は、従来テキストより検索するのが難しかった。本発明は、大きいデータスペース内にこのような内容やその断片がないかどうかを検索することを可能とするものである。例えば、この場合におけるキーは、捜索されている画像を表す画素の行や象限であったりする。この場合、キーの信号を近似整合させることによって、このキーに対する整合又は近似整合が識別される。
【００１０】
本発明の主要な利点と特徴は、すでに簡単に説明したが、以下の図面を参照し、好ましい実施形態を読めば本発明をより徹底的に理解することが可能であろう。
【００１１】
（発明を実施するための最良の形態）
図１に示すように、本発明は、スタンドアローン型のコンピュータ又はコンピュータシステムとして容易に実現される。広い意味では、本発明は、近似整合ユニット２４にカップリングされたプログラム可能なデジタル論理デバイス又はマイクロプロセッサ２２を自身が含む近似整合／プリフェッチプロセッサ２０から成る。大容量記憶媒体２６は近似整合ユニット２４に接続されていて、データの多量記憶用の媒体となっている。「大容量記憶媒体」という用語は、多量のデータを記憶するために使用され、また、一般的にコンピュータ又はコンピュータネットワーク中で使用されるように設計されたなんらかのデバイスを意味するものと理解すべきである。その例には、ＣＤ　ＲＯＭなどの光学システム、ハードディスクドライブなどの磁気システム、又は信号ディスク表面などのサブユニットが含まれ、これらのシステムは、回転型、線形型、直列型、並列型又はこれらの様々な組み合わせ型であり得る。例えば、ハードディスクドライブユニットのラックは、並列に接続して、その並列出力をトランスジューサレベルで、１つ以上の近似整合ユニット２４に提供するようにしてもよい。同様に、バンクを成す磁気テープドライブを用いて、その直列出力を個々に、１つ以上の近似整合ユニット２４に並列に提供するようにしてもよい。媒体上に記憶されているデータは、アナログ形態でもデジタル形態であってもよい。例えば、データは、上記のようなテープ記録例におけるような音声記録物であったりする。したがって、本発明は拡張可能であり、（並列近似整合ユニットの数を増すことによって又は近似整合／プリフェッチプロセッサを複製することによって）性能を保持しながらも、大容量記憶媒体中に記憶されるデータの量を（並列記憶ユニットの数を増すことによって）増すことが可能となる。
【００１２】
図１の上部に示すような先行技術においては、一般的に、ディスクコントローラ２８及び／又はディスクキャッシュ３０を従来的な意味で用いて、ＣＰＵ３２がそのシステム又は入力／出力バス３４上でアクセスするようにする。本発明においては、近似整合／プリフェッチプロセッサ２０は、大容量記憶媒体２６中のデータをアクセスして、それを、ソーティング及びアクセス目的でメモリの大ブロックを大容量記憶媒体２６からシステムバス３４を介して又はＣＰＵ３２の主メモリ（分離して図示していない）中に移動させることなく、システムバス３４で使用されるように提出する。言い換えれば、以下に詳述するように、ＣＰＵ３２は、データの要求又は照会を近似整合／プリフェッチプロセッサ２０に送出し、これが次に、このデータを非同期式に大容量記憶媒体２６中でアクセスしてソーティングして、それを、先行技術で周知なようにディスクキャッシュ３０中で使用されるように提出するか、又は、ＣＰＵ３２によって必要とされるさらなる処理やその主メモリを使用することなくシステムバス３４上に直接に提出するようにする。したがって、このプロセッサは、本発明によって検索と整合の活動が実施されている間に自由に他のタスクを実行することが可能である。
【００１３】
近似整合ユニット２４は、自身が、走査、相関、一般的論理／近似整合機能を、照会指令のキー情報のデジタル表示物又はアナログ表示物と共に記憶媒体から受信された信号に基づいて実行するように編成されたデジタル論理回路又はアナログ回路の集合を備えている。これらの機能は、専用の論理及び回路、プログラム可能論理及び回路によって又はデジタル信号プロセッサ（ＤＳＰ）などのプログラム可能なプロセッサを用いて実行され得る。本発明者は、ハードウエアデバイス又はプログラムされたソフトウエアデバイスの多くの様々な変形物を用いて、利点を仮想的に等化させて本発明を実現し得ると考察しており、したがって、現在のところ、本明細書で特に別記されていないかぎり、なんらかの特定の実現形態が他の実現形態より良好なモードであるとは考察していない。さらに、本発明は、いかなる特定のデータ構造体又は応用分野に結びついていると考慮すべきではなく、これらは、本明細書では、むしろ、図示的な目的だけのものであると見るべきである。本開示内容をテンプレートとして用いれば、当業者には、本発明の目的を実施するに必要な機能と動作を実行するようなデバイスを容易に構築できることが考察されよう。
【００１４】
上に説明したように、本発明を用いれば、正確な整合と近似的な整合の双方を実行することが可能である。アナログドメインにおいて正確な整合を実施する場合においては、アナログ比較器と相関技法を用いて整合が実行される図１ＡにおけるポイントＡでは、正確な整合が、キーを記憶媒体上のアナログソースデータに整合させるために十分に高いしきい値を設定することに対応する。このアナログドメインにおける近似整合は、適切な（より低い）しきい値の設定に相当する。デジタルドメインにおける正確な整合を実施する場合においては、正確な近似は、現在の技術で提案されているデジタル比較器と論理を用いて実行されるが、この場合、デジタルキーを記憶媒体からのデジタルソースデータと比較する。このような整合は、図１Ａに示すポイントＢ又はポイントＣで実行可能であるが、これらのポイントは、誤差補正前のデジタル信号と誤差補正後のデジタル信号にそれぞれ対応する。このドメインにおける近似整合は、記憶媒体から得られたデジタルソースデータとのデジタルキーの比較又はデジタル相関に対応する。デジタルキーは、「ワイルドカード」又は「ドントケア」デジタルビット又はデータ形式を含み得る。近似整合が成功したか否かは、相関値を設定するか又は、走査されたソースデータ中の対応するビットに等しいキー内のビット数などの多くの整合性能測定基準の内の１つを用いることによって決定され得る。また、注意すべきは、「近似した」整合検索で識別されたデータエントリには、「正確な」検索に起因する「正確な」ヒットが含まれることである。分かりやすく言えば、「整合」という語が用いられていたら、それを読む人は、それは検索すなわち近似検索もしくは正確な検索のどちらかによって発見されたデータ結果を含むものと理解すべきである。「近似整合」又は単に「近似の」という句が使用されていた場合でさえも、それを読む人は、それは、近似検索として上述された２つの検索の内のどちらか、すなわち検索判断基準に緩やかに関連したデータエントリを収集するに十分大きい正味を有する他の何らかの種類の「ファジーな」検索であり得るということを理解すべきである。もちろん、正確な整合とはまさにそれであり、そして、高度の相関を持つ検索判断基準の正確な整合以外のどんな結果をも含まない。
【００１５】
マイクロプロセッサ又はプログラム可能な論理デバイス２２は、自身が、１つ以上のマイクロプロセッサ、プログラム可能な論理ユニット、専用論理回路及び関連の回路を含み得る。このユニットは、システム又は入力／出力バス３４とインタフェースし、また、ある１つの構成では、また、存在し得るなんらかのディスクキャッシュ３０ともインタフェースする。このユニットは、ＣＰＵ３２又はネットワークインタフェース３６からの要求と照会を受信して処理し、これらの要求を適切な形態で近似整合ユニット２４に提出する。加えて、このユニットは、要求の結果を、ディスクキャッシュ３０とＣＰＵ３２のどちらか又は双方に対して（バス３４を介して）通過させる支援をし得る。
【００１６】
より特定的には、図１Ａに示すように、会話型で剛性のディスクドライブは、各ディスクにアクセスする複数のトランスジューサを有する複数の回転ディスクを有し得る。これらトラスジューサは各々が、一般的には、増幅器などの、自身の出力供給用のアナログ信号電子系を有している。これは、図中ではポイントＡに提示されている。近似整合／プリフェッチプロセッサ（ＡＭＰＰ）２０、すなわちＡＭＵ２４は、アナログ整合目的でポイントＡに設置され得る。図１Ａにさらに示すように、一般的には、アナログ回路の出力は、単一のデジタルデコーダに選択的に提供され、次に、このデコーダが、このような出力を１つ処理する。これは、図中ではポイントＢで表されている。次に、このデジタル出力は、一般的には、誤差補正回路（ＥＣＣ）中を通って送出され、次に、その出力部Ｃでバス３４又はディスクキャッシュ３０上に送り出される。本発明の目的上、複数のデジタルデコーダとＥＣＣを提供することによってデータ用の複数の並行経路を備えるのが望ましい。近似整合／プリフェッチプロセッサ（ＡＭＰＰ）２０，すなわちＡＭＵ２４は、デジタル整合の目的上、ポイントＢとポイントＣのどちらに設置してもよく、また、多重データ出力目的のためには、複数のＡＭＰＰ又はＡＭＵも備えてもよい。
【００１７】
図１にはまた、本発明２０、ＬＡＮやＷＡＮやインターネットなどてあったりする他のコンピュータシステム４０などが接続され得るネットワーク３８を相互接続するネットワークインタフェース３６が示されている。この配置によって、他のコンピュータシステム４０は、本発明２０を介して大容量記憶媒体２６上に記憶されているデータにアクセスするのが便利であり得る。より特定的な例を以下に示す。
【００１８】
図２〜４に示すように、本発明は、コンピュータとネットワークとから成る様々な構成として実現される。図２に示すように、本発明は、システムバス４６に接続されたＣＰＵ４４を備え、このシステムバスが、本明細書に開示するような本発明を有する大容量記憶媒体４８にアクセスするようになっているスタンドアローン型コンピュータシステム４２の１部として提供され得る。
【００１９】
図３に示すように、本発明とカップリングされたこの大容量記憶媒体５０は、自身が、ネットワーク５２に対して直接接続され、これによって、このネットワーク上では、複数の独立型コンピュータ又はＣＰＵ５４がインテリジェント型大容量記憶媒体５０にアクセスするようになっている。このインテリジェント型大容量記憶媒体５０は、自身が、バンクを成すハードディスクドライブから成るが、このドライブバンクは、ＲＡＩＤ、ディスクファーム又は他の何らかの大規模並行なメモリデバイス構成を備え、これによって、膨大な分量のデータに対してかなり減少したアクセス時間で、アクセスし、また、近似整合する機能を実現している。
【００２０】
図４に示すように、本発明を装備したインテリジェント型大容量記憶媒体５６は、ネットワーク接続型記憶デバイス（ＮＡＳＤ）としてネットワーク５８に接続され、これによって、ネットワーク５８上で、複数のスタンドアローン型コンピュータ６０が、それに対してアクセスし得るようになっている。図４に示すような構成によって、図４ではディスクとして表されているデータ記憶デバイスはその各々が、ネットワークに接続されているどのプロセッサからもアクセス可能であることが予想される。このような１つの構成では、固有のＩＰアドレス又は他のネットワークアドレスが各データ記憶媒体に対して割り当てられる。
【００２１】
図２〜４に例として示すような構成は、本発明とコンパティブルであり高度に有用である、コンピュータとネットワークとの様々な構成の例を示しているだけである。他の例は、当業者には明らかであり、したがって、本発明は、本発明の汎用性を図示する目的でここに示すような例によって制限されることを意図しない。
【００２２】
図５Ａに示すように、本発明による方法は、その代替例を、アナログキーとデジタルキーのどちらを用いるかという点に関して説明する。しかしながら、方法の開始に際して、ＣＰＵはある機能を実行し、この間に、大容量記憶媒体に記憶されているデータをアクセスすることを選択する。一般的には、ＣＰＵは、アプリケーション６２を実行するが、これは、ＤＮＡ検索や、インターネット検索や、アナログ音声検索や、指紋検索や、画像検索や、データに対する近似の（又は正確な）整合が所望されるこの種の他の検索であったりする。このより高次の言語アプリケーションを実行するに際して、ＣＰＵは、一般的に、要求又は照会を実行して、記憶デバイス２６から情報を得る。この照会には、様々なパラメータを指定する指令が含まれているが、これらのパラメータは、要求された情報を適切に記憶デバイス２６から得るためには、ディスク制御ユニット２８と近似整合／プリフェッチプロセッサ２０が有しなければならないものである。このパラメータの例には、これに限られないが次のものが含まれる。記憶デバイスを走査するための開始ロケーション；（整合がなかった場合における）走査が終了した後の最終ロケーション；走査で使用される予定のキー；整合の近似性の指定；整合が発生した場合における返却されるべき情報、など。返却され得る情報のソーティングには、整合が発見された情報のアドレス又は、この整合した情報を含んでいるセクター、レコード、レコードの部分もしくは他のデータ集合が含まれる。このデータ集合もまた、動的に指定して、整合したら返却されるデータを、境界フィールド内に包含される整合データを有する境界データ指定子同士間にあるものとして指定してもよい。例えば、「ｔｅｒｒｏｒｉｓｔ」（テロリスト）という語をテキストのストリング中に探すと、ミススペルしだいでは「ｔｅｒｒｅｒｉｓｔ」という語が近似整合して発見されて、その周りの文章によって画定されるデータフィールドが返却されるかもしれない。別の照会パラメータは、返却情報が、システム、入力／出力バス３４、又はディスクキャッシュ３０に送出されるべきであるかを示すものである。
【００２３】
この照会の結果、一般的には、オペレーティングシステムのユーティリティが１つ以上実行されることになる。より高次のユーティリティコマンドの例として、ＵＮＩＸオペレーティングシステムの場合、これは、ｇｌｉｍｐｓｅやｆｉｎｄやｇｒｅｐやａｐｒｏｐｏｓの修正バージョンであったりする。その他のこのような機能も、ＣＰＵに検索や近似検索などのコマンド６６を本発明の近似整合／プリフェッチプロセッサ（図１を参照）に送出させるが、これらのコマンドの関連の部分もまた、ディスクコントローラ２８に送出されて、例えば、なんらかの大容量記憶媒体の位置付けアクティビティ６９を始動させるが、このアクティビティは、後になってこの媒体から情報を適切に読み出すためには必要とされる。
【００２４】
この時点では、本発明の特定の実施形態で実現されることが望まれる特定の方法しだいでは、アナログキー又はデジタルキーを決定することが必要である。このキーは、正確なデータであれ近似的なデータであれ、検索されているデータに対応するデータである。アナログキーの場合、このキーは、大容量記憶媒体内などに事前記憶されて専用回路を用いて展開されたり、又は、発生されることを必要とされる。アナログキーが事前に記憶されている場合、事前記憶済みキー送出ステップ６８が、マイクロプロセッサ又はプラグラム可能な論理デバイス２２（図１を参照）によって実行され、これが、ステップ７０に示すように、デジタル式のサンプリング済み形式でキーを近似整合ユニット２４に送信する。代替例では、アナログキーが事前に記憶されていない場合、アナログキーは多数あるメカニズムの内の１つを用いて展開されるが、これらのメカニズムの内の２つを図５に示す。マイクロプロセッサ２２において、ステップ７２において磁気媒体上にキーを書き込み、次に、そのキーをステップ７４で読み出して、キーのアナログ信号表示を発生する。ステップ７１などの別のステップでは、ＣＰＵから受信したキーのデジタルバージョンは、適切なデジタルアナログ回路を用いてアナログ信号表示に変換し、これが次に適切にサンプリングされる。次に、このキーは、ステップ７０のように、そのデジタルサンプルとして記憶される。デジタルキーを用いる場合、マイクロプロセッサ２２が、このデジタルキーをステップ７６で近似整合ユニット２４に記憶する必要があるだけである。マイクロプロセッサ２２と近似整合ユニット２４の各々に対して含むことが望まれる特定の構造体によっては、キーはこれらのコンポーネントのどれか又は全ての中に常駐し得るのであり、そのキーに対する適切なデジタル形式を最終的に近似整合ユニット２４中に獲得して、比較と相関をするようにするのが望ましいことを理解すべきである。次に、大容量記憶デバイスが、７９において、その開始ロケーションに達すると、大容量記憶媒体２６上に記憶されているデータは、ステップ７８で連続的に読み出されて、大容量記憶媒体２６に記憶されているデータを表す連続ストリーム信号を発生する。アナログキーを用いた場合、このアナログキーは、ステップ８０で大容量記憶媒体２６から読み出されたアナログデータと相関される。本発明者は、多くの先行技術による比較器及び相関回路のどれでも用いることは可能であると考察しているが、本目的のためには、本発明者は、アナログ信号とキーをデジタルサンプリングすることが、以下に説明するように、このような比較と相関係数の計算を実行するにあたって極めて有用であると提案するものである。大容量記憶媒体２６からデータを読み出すことによって発生されたこのアナログ信号は、先行技術によるデバイスによってアナログデータ又はデジタルデータのどちらかを読み出すことによって発生すると便利であり、デジタルキーを用いて、デジタルデータを大容量記憶媒体２６に記憶されたままで整合させる目的で使用する必要はないことに注意すべきである。代替例では、相関ステップ８２を、デジタルキーを大容量記憶媒体２６から読み出されたままのデジタルデータのストリームと整合させることによって実行され得る。キーは、近似情報が包含されていることを反映するものであると注意すべきである。したがって、これを記憶媒体から読み出された情報と相関させることによって、近似整合機能が可能となる。
【００２５】
次に、判断論理８４は、データの１部分がキーと近似的に整合するか否かについてインテリジェント的に判定する。整合が見つかれば、データはステップ８６におけるように処理され、照会によって要求されたデータが、ディスクキャッシュ３０に対して送出されるか、又は、直接的にシステムバス３４上に送出されるか、そうでなければ、バッファリングされるかＣＰＵ３２かネットワークインタフェース３６に対して入手可能とされるか、そうでなければ図１〜４に示すようになる。論理ステップ８８は、図５では、大容量媒体２６からのデータの連続的読み出しに復帰するものとして提示されているが、これはおそらく「ｄｏ」ループを示している。しかしながら、これは連続的なプロセスであり、また、データは大容量記憶媒体２６からストリームとして処理され個別化されたデータのかたまりや、フレームや、バイトや、他の所定のデータ部分として処理されていないことを理解すべきである。この可能性は排除されていないとはいえ、本発明では、連続的に変化するデータ読み出し信号上で、キーを本質的に「滑らす」ことによって、大容量記憶媒体２６からデータを即座に読み出すことが可能であるようにするのが望ましい。読み取りのタイミングをどのマルチビットデータ構造体の開始や終了に同期させなければならない必要性もなく、また、データが、大容量記憶媒体２６から読み出されながら「リアルタイムで」連続的に比較されるにつれて、他のなんらかの中間ステップを、実行する必要性もない。このタイプの比較と相関は、パターン整合又はパターン比較と呼ばれたりするものである。結局、データアクセスは、ステップ９０で完了して、プロセスは完了する。
【００２６】
本明細書において、発明者は、本発明を予備的に試験し、その操作性と効果性を実証する予備データを発生している。
【００２７】
図６は、読み出し／書き込みヘッドが、１０−ビットデジタルキーが記憶されている磁気媒体から読み出しを実行している際に、読み出し／書き込みヘッドから出力されるアナログ信号の測定結果の図形表示内容である。同図に示すように、技術上周知なように、ハードディスクなどの磁気媒体からデータが読み出される読み出し／書き込みヘッドによって発生された真のアナログ信号を表すピーク値がアナログ信号中に存在する。図６に示す尺度は、縦軸がボルトであり、横軸がマイクロ秒の１０分の１である。
【００２８】
図７に示すように、磁気媒体の試験部分に記憶されている疑似ランダムバイナリシーケンスからデータが読み出されるにつれて、再度、読み出し／書き込みヘッドによってアナログ信号が発生する。図７から分かるように、この読み出し信号は、このレベルで検査した場合、理想的な方形波出力とはならない。
【００２９】
図８は、８ビットキーの近似的２ビットとディスク又は磁気媒体上の異なったロケーションでエンコーディングされた疑似ランダムバイナリシーケンスにおいて見出されたそれに対応する２ビットとの間の重なりをより特定的に図示する、横軸を拡大した、図形表示内容である。
【００３０】
図９は、ハードディスクからのデータの連続的読み取り値とキーとが比較されるにつれて連続的に計算された相関係数の図形表示内容である。この相関係数は、アナログ信号を高速でサンプリングし、先行技術による信号処理相関技法を用いて計算される。このような１例が、１９９２年１１月発行のＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｍａｇｎｅｔｉｃｓの第２８巻の第６号のホインビル（Ｈｏｉｎｖｉｌｌｅ）、インデック（Ｉｎｄｅｃｋ）及びミュラー（Ｍｕｌｌｅｒ）による「長手方向磁気記録媒体の空間雑音現象」（Ｓｐａｔｉａｌ　Ｎｏｉｓｅ　Ｐｈｅｎｏｍｅｎａ　ｏｆ　Ｌｏｎｇｉｔｕｄｉｎａｌ　Ｍａｇｎｅｔｉｃ　Ｒｅｃｏｒｄｉｎｇ　Ｍｅｄｉａ）の中に見受けられ、その開示内容は参照して本明細書に組み込まれる。読み取り、比較及び係数相関の方法及び装置の先行技術による例は、米国特許第５，７４０，２４４号などの共発明者の先行特許の内の１つ以上に見受けられ、その開示内容は参照してここに組み込まれる。前記の内容は、本発明を実現するために用いられるデバイスと方法の例を表すものであるが、本明細書の他の箇所で述べたように、他の類似のデバイス及び方法も同様に用いても、本発明の目的は達せられる。
【００３１】
３２５と記されたポイントの近傍で、１に近いきわだったピーク値が認められるが、これは、キーと疑似ランダムバイナリシーケンスとの間における非常に近接した整合を示すものである。したがって、本発明は、疑似ランダムデジタルシーケンス内に存在するキーを発見することが可能であることが実証された。図９もまた、本発明の強力な態様であると信じられている近似整合の機会を図示するものである。図９をよく見ると、相関係数中には他にもより低いピーク値が現れることに気づく。したがって、判定ポイントとして０．４というしきい値を設定すると、１に近づくピーク値の発生が整合すなわち「ヒット」を示すだけではなく、他の別の５つのピーク値も「ヒット」を示すものである。このように、所望の係数値を、特定の検索パラメータに適合するように予め決定したり調整したりしてもよい。例えば、多量のテキストから成る本文中から特定の語を検索する場合、相関値が低ければそれは、その語は存在するが、ミススペルされていることを示している。
【００３２】
図１０に、同じ８ビットキーではあるがデータ集合は異なる場合の相関係数の連続計算結果を示す。ここでも、約２００マイクロ秒のところで単一整合がピックアップされている。この場合もまた、低いしきい値を設定した場合、疑似ランダムデータ中にさらなるヒットが存在していることに気づく。
【００３３】
本発明の精神から逸脱しない範囲内で、本発明に対する様々な変更例や修正例が当業者には明らかであろう。これらの代替例の内のいくつかを上記した。例えば、図６〜１０に示すアナログ処理によって例示される動作の全てが、デジタルドメインでその等化処理が可能である。したがって、近似整合と相関というタイプの処理を、アナログビットパターンの標準的なデジタル表示物に対して実行することが可能である。これはまた、調整されたデジタル論理、マイクロプロセッサ及びデジタル信号プロセッサ又はこれらの代わりとなる組み合わせを用いて連続的に達成することが可能である。したがって、本発明は添付の特許請求の範囲とその合法的な等化物によってのみ制限されるというのが、本発明者の意図である。
【図面の簡単な説明】
【図１】
自身に対して非同期アクセスする論理大容量記憶媒体と、他のコンピュータシステムに対するネットワークと本発明との間のネットワークインタフェースと、を備える本発明による自身のシステム又は入力／出力バス上でアクセスするコンピュータのブロック図である。
【図１Ａ】
本発明を接続するための様々な挿入ポイントを図示する従来の剛性のディスクドライブシステムの略図である。
【図２】
スタンドアロン構成にした本発明の実現形態を示すブロック図である。
【図３】
ネットワーク上での共用遠隔大容量記憶デバイスとして実現された本発明を示すブロック図である。
【図４】
ネットワーク接続型記憶デバイス（ＮＡＳＤ）としての本発明を示すブロック図である。
【図５】
大容量記憶媒体内のデータをアクセスする本発明の方法における論理ステップの詳細を示すフローチャートである。
【図６】
キーとして用いられ得るアナログ信号の図形表示である。
【図７】
「キー」データパターンが存在する大容量記憶媒体からデータを連続的に読み出す動作を表すアナログ信号の図形表示である。
【図８】
データ信号に対して上にあり、整合されたキー信号の図形表示である。
【図９】
大容量記憶媒体内のデータが走査されてキーと比較されるにつれて連続的に計算される相関機能の図形表示である。
【図１０】
データの様々な集合を読み出すことによって取られ、しかも、「キー」データパターンを含んでもいる信号とキーを連続的に比較するにつれて得られた相関機能の図形表示である。
【図１】
2004502996.tif 000003
【図１Ａ】
2004502996.tif 000004
【図２】
2004502996.tif 000005
【図３】
2004502996.tif 000006
【図４】
2004502996.tif 000007
【図５Ａ】
2004502996.tif 000008
【図５Ｂ】
2004502996.tif 000009
【図６】
2004502996.tif 000010
【国際公開パンフレット】
2004502996.tif 000011
2004502996.tif 000012
2004502996.tif 000013
2004502996.tif 000014
2004502996.tif 000015
2004502996.tif 000016
2004502996.tif 000017
2004502996.tif 000018
2004502996.tif 000019
2004502996.tif 000020
2004502996.tif 000021
2004502996.tif 000022
2004502996.tif 000023
2004502996.tif 000024
2004502996.tif 000025
2004502996.tif 000026
2004502996.tif 000027
2004502996.tif 000028
2004502996.tif 000029
2004502996.tif 000030
2004502996.tif 000031
2004502996.tif 000032
2004502996.tif 000033
2004502996.tif 000034
2004502996.tif 000035
2004502996.tif 000036
2004502996.tif 000037
2004502996.tif 000038
【国際公開パンフレット（コレクトバージョン）】
2004502996.tif 000039
2004502996.tif 000040
【国際公開パンフレット（コレクトバージョン）】
2004502996.tif 000041
2004502996.tif 000042
【国際調査報告】
2004502996.tif 000043
2004502996.tif 000044
2004502996.tif 000045