JPH083817B2 - データベース検索方法 - Google Patents
データベース検索方法Info
- Publication number
- JPH083817B2 JPH083817B2 JP62156716A JP15671687A JPH083817B2 JP H083817 B2 JPH083817 B2 JP H083817B2 JP 62156716 A JP62156716 A JP 62156716A JP 15671687 A JP15671687 A JP 15671687A JP H083817 B2 JPH083817 B2 JP H083817B2
- Authority
- JP
- Japan
- Prior art keywords
- document
- word
- database
- digital data
- flag
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2453—Query optimisation
- G06F16/24532—Query optimisation of parallel queries
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/33—Querying
- G06F16/332—Query formulation
- G06F16/3325—Reformulation based on results of preceding query
- G06F16/3326—Reformulation based on results of preceding query using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
- G06F16/90339—Query processing by using parallel associative memories or content-addressable memories
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y10S707/99935—Query augmenting and refining, e.g. inexact access
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computational Linguistics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Multi Processors (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、テキストそのもの（natural text）を含む
大規模データベースの自由テキスト検索方法に関し、特
に、検索が並行処理される大規模データベースの自由テ
キスト検索方法に関する。
大規模データベースの自由テキスト検索方法に関し、特
に、検索が並行処理される大規模データベースの自由テ
キスト検索方法に関する。
今日、有線放送や、新聞，雑誌その他百科辞典，文献
等の印刷媒体からの記事，抜粋等の情報を大規模データ
ベースに格納し、コンピュータにより検索し、取り出す
ことが益々普及してきた。
等の印刷媒体からの記事，抜粋等の情報を大規模データ
ベースに格納し、コンピュータにより検索し、取り出す
ことが益々普及してきた。
大規模データベースの検索に用いられる方法は、検索
に利用される逐次処理コンピュータにより制限されてき
た。理想的には、検索方法は高い読み出し率と正確さを
持つべきである。読み出し率とは、取り出しの対象とな
るデータベース全体内の関連文書の割合である。正確さ
とは、取り出された関連文書の割合である。全数検索法
では高い読み出し率および高い正確さが得られる。根本
的な問題は、全数検索は非常に長い時間を要するおそれ
があることである。そのため、非全数方法が用いられて
いる。
に利用される逐次処理コンピュータにより制限されてき
た。理想的には、検索方法は高い読み出し率と正確さを
持つべきである。読み出し率とは、取り出しの対象とな
るデータベース全体内の関連文書の割合である。正確さ
とは、取り出された関連文書の割合である。全数検索法
では高い読み出し率および高い正確さが得られる。根本
的な問題は、全数検索は非常に長い時間を要するおそれ
があることである。そのため、非全数方法が用いられて
いる。
データベースを組織する通常の方法は「データベース
の逆（inverting the database）」と呼ばれる主法であ
る。G.Jemes,Document Database（Van,Nostrand Reinho
ld Company 1985）,J.Rijsvergen,Infomation Retrieva
l,p.72（Butterworths,2ded.1979）を参照されたい。各
文書には独自の文書番号が割り当てられる。文書中の語
（“a"および“the"のような余り意味のない語を除く）
には文書番号が付けられ、アルファベット順索引の中に
入れられる。与えられた語を含む全ての文書の位置を確
認するために、その語に関して索引が検索され、一連の
文書番号が戻ってくる。または、各文書の語が代用コー
ドにより記憶される。その場合、各語は複数ハッシュコ
ードのテーブルの中の一つのハッシュコードで表され、
語の検索は、関心のある語に関連したハッシュコードの
存在を検索することにより実行される。
の逆（inverting the database）」と呼ばれる主法であ
る。G.Jemes,Document Database（Van,Nostrand Reinho
ld Company 1985）,J.Rijsvergen,Infomation Retrieva
l,p.72（Butterworths,2ded.1979）を参照されたい。各
文書には独自の文書番号が割り当てられる。文書中の語
（“a"および“the"のような余り意味のない語を除く）
には文書番号が付けられ、アルファベット順索引の中に
入れられる。与えられた語を含む全ての文書の位置を確
認するために、その語に関して索引が検索され、一連の
文書番号が戻ってくる。または、各文書の語が代用コー
ドにより記憶される。その場合、各語は複数ハッシュコ
ードのテーブルの中の一つのハッシュコードで表され、
語の検索は、関心のある語に関連したハッシュコードの
存在を検索することにより実行される。
一語より多い語を含む文書の検索には、索引上でのブ
ール検索法が代表的に用いられる。ブール検索は、照会
（query）について文書との理論的比較を行うことによ
りその結果を得る検索である。この手法を実際に応用す
るには、ディスクドライブを満載した多くの部屋と複数
の大型メインフレーム・コンピュータを要する。索引の
検索と理論的比較が逐次的に行われるために、照会の複
雑さによっては、応答時間はしばしば非常に遅くなる。
このようなシステムは、その提供する検索の質が低く、
使用するにあたって取り扱いづらい。読み出し率と正確
さの間には相反する関係があり、それにより大規模デー
タベース上のブール検索の質が制限される。ある単一の
語を含む文書に対するデータベースの検索は、全ての関
連文書がその語を使用しているという保証はないから、
低い読み出し率になる。さらに、関連のない多数の文書
が取り出され、正確さが低下し易い。複数の語の検索の
場合はこれらの問題を一層悪化させる。もし検索者が複
数の語の中のいずれかを探すならば（分離照会）、読み
出し率は良くなるが、正確さは落ちる。もし検索者が複
数の語の全てを含む文書を探すならば（連結照会）、正
確さは良くなるが、読み出し率は下がる。大規模データ
ベースの場合、これは重要な情報を見逃すか、関連のな
い多数の文書を検索することを検索者が選択しなければ
ならないことを意味する。完全なテキストのためのブー
ル照会を用いることについてはさらに問題がある。第１
にユーザは、彼が関心を持つ文書の著者がどの語を使用
したかの推測を試みて推測ゲームを行う。第２に、例え
彼がその語群を推測したとしても、過多または過化なデ
ータを得ることを避けるために、彼は連結する語として
どの語を使うべきかを決定しなくてはならない。これに
より、ユーザはしばしば照会を複数回繰り返し実行して
デバックする必要がある。最後に、ブール照会の文法は
複雑で、システムを学習することとは困難である。
ール検索法が代表的に用いられる。ブール検索は、照会
（query）について文書との理論的比較を行うことによ
りその結果を得る検索である。この手法を実際に応用す
るには、ディスクドライブを満載した多くの部屋と複数
の大型メインフレーム・コンピュータを要する。索引の
検索と理論的比較が逐次的に行われるために、照会の複
雑さによっては、応答時間はしばしば非常に遅くなる。
このようなシステムは、その提供する検索の質が低く、
使用するにあたって取り扱いづらい。読み出し率と正確
さの間には相反する関係があり、それにより大規模デー
タベース上のブール検索の質が制限される。ある単一の
語を含む文書に対するデータベースの検索は、全ての関
連文書がその語を使用しているという保証はないから、
低い読み出し率になる。さらに、関連のない多数の文書
が取り出され、正確さが低下し易い。複数の語の検索の
場合はこれらの問題を一層悪化させる。もし検索者が複
数の語の中のいずれかを探すならば（分離照会）、読み
出し率は良くなるが、正確さは落ちる。もし検索者が複
数の語の全てを含む文書を探すならば（連結照会）、正
確さは良くなるが、読み出し率は下がる。大規模データ
ベースの場合、これは重要な情報を見逃すか、関連のな
い多数の文書を検索することを検索者が選択しなければ
ならないことを意味する。完全なテキストのためのブー
ル照会を用いることについてはさらに問題がある。第１
にユーザは、彼が関心を持つ文書の著者がどの語を使用
したかの推測を試みて推測ゲームを行う。第２に、例え
彼がその語群を推測したとしても、過多または過化なデ
ータを得ることを避けるために、彼は連結する語として
どの語を使うべきかを決定しなくてはならない。これに
より、ユーザはしばしば照会を複数回繰り返し実行して
デバックする必要がある。最後に、ブール照会の文法は
複雑で、システムを学習することとは困難である。
第２の検索法では、「単純照会（simple queries）」
と呼ばれるブール照会についての変形を用いる。C.J.va
nrijsvergen,Information Retieval,p.160（Betterworh
ts,2ded.1979）を参照されたい。この検索法では、照会
は１セットが複数の語で構成され、その各々には点数が
割り当てられる。データベース内のどの文書も、それが
含む各語についての点数を加算した点数を付けて格納さ
れる。この照会の結果は、合計点数で順序付けられた１
個の複数文書となる。単純照会は、それがサポートする
検索の質において、ブール照会に匹敵する。例えば、肯
定的な点数（positive score）を持つ文書だけユーザが
調査するときは、彼は実質的には分離照会の結果を調査
しているのであって、読み出し率は高いが、正確さは低
いことが予期される。単純照会の利点は、これら両極端
の中間に、中程度の読み出し率と正確さの領域が存在す
るということである。さらに単純照会はブール照会より
も使い易いということがある。ユーザは、単純照会では
連結する語など存在しないから、どの語を連結して使用
すべきかを決定する必要がない。単純照会は語のリスト
からなるため、ユーザは複雑な照会言語を学習する必要
がない。しかし、単純照会での検索は、ブール照会での
検索と同時に、やはり推測ゲームが残ってしまう。さら
に問題なのは、取り出す文書の数を管理可能な程度に制
限するために、照会に対する応答点数に関して、しきい
値をどのくらいに定めるかということである。
と呼ばれるブール照会についての変形を用いる。C.J.va
nrijsvergen,Information Retieval,p.160（Betterworh
ts,2ded.1979）を参照されたい。この検索法では、照会
は１セットが複数の語で構成され、その各々には点数が
割り当てられる。データベース内のどの文書も、それが
含む各語についての点数を加算した点数を付けて格納さ
れる。この照会の結果は、合計点数で順序付けられた１
個の複数文書となる。単純照会は、それがサポートする
検索の質において、ブール照会に匹敵する。例えば、肯
定的な点数（positive score）を持つ文書だけユーザが
調査するときは、彼は実質的には分離照会の結果を調査
しているのであって、読み出し率は高いが、正確さは低
いことが予期される。単純照会の利点は、これら両極端
の中間に、中程度の読み出し率と正確さの領域が存在す
るということである。さらに単純照会はブール照会より
も使い易いということがある。ユーザは、単純照会では
連結する語など存在しないから、どの語を連結して使用
すべきかを決定する必要がない。単純照会は語のリスト
からなるため、ユーザは複雑な照会言語を学習する必要
がない。しかし、単純照会での検索は、ブール照会での
検索と同時に、やはり推測ゲームが残ってしまう。さら
に問題なのは、取り出す文書の数を管理可能な程度に制
限するために、照会に対する応答点数に関して、しきい
値をどのくらいに定めるかということである。
さらに他の検索法には、関連性を帰還（feedback）す
る方法がある。この検索法では、単純照会は、関連性が
あると判定された文書テキストから構成される。G.Salf
on,The Swart Retrieval System−Experimet in Automa
tic Document Processing,p.313（Prentice−Hall 197
1）;C.J.van Rijsvergen,Information Retrieval,p.105
（Butterworths,2d ed.1979）を参照されたい。最初
に、関連性がありそうな文書、小数個の位置を探し出す
ための検索法が使用される。ユーザはそれから、これら
の文書を見て、彼が明らかに関連があると思うものも良
いと特徴付け、彼が明らかに関連がないと思うものを悪
いと特徴付ける。特徴付けされた文書テキストは、次い
で、適切な検索語について調べられ、これらの語から照
会が構築される。ある語が出現する良い文書が多いほ
ど、新しい照会の中でのその語の重要性は大きくなり、
それ故、その語に対して割り当てる点数は高くなる。新
しい照会は、数百の言葉を含むこともある。次いでこの
照会は同じデータベースに対して単純照会と同じ形態で
適用される。関連性を帰還する方法は、検索過程で多数
の語を使用するので、高い正確さと高い読み出し率の双
方へ導く。単独の語それ自身だけではほとんど情報を伝
えないが、数百語が一緒になると多量の情報を伝える。
関連性の高い文書だけが、数百項目のこの組を利用する
比率が高くなる。しかし、かかる照会を実行する唯一の
方法は、全数検索によることであって、それは現在デー
タベース検索システムに利用されている逐次動作のメイ
ンフレーム・システムでは実行不可能である。
る方法がある。この検索法では、単純照会は、関連性が
あると判定された文書テキストから構成される。G.Salf
on,The Swart Retrieval System−Experimet in Automa
tic Document Processing,p.313（Prentice−Hall 197
1）;C.J.van Rijsvergen,Information Retrieval,p.105
（Butterworths,2d ed.1979）を参照されたい。最初
に、関連性がありそうな文書、小数個の位置を探し出す
ための検索法が使用される。ユーザはそれから、これら
の文書を見て、彼が明らかに関連があると思うものも良
いと特徴付け、彼が明らかに関連がないと思うものを悪
いと特徴付ける。特徴付けされた文書テキストは、次い
で、適切な検索語について調べられ、これらの語から照
会が構築される。ある語が出現する良い文書が多いほ
ど、新しい照会の中でのその語の重要性は大きくなり、
それ故、その語に対して割り当てる点数は高くなる。新
しい照会は、数百の言葉を含むこともある。次いでこの
照会は同じデータベースに対して単純照会と同じ形態で
適用される。関連性を帰還する方法は、検索過程で多数
の語を使用するので、高い正確さと高い読み出し率の双
方へ導く。単独の語それ自身だけではほとんど情報を伝
えないが、数百語が一緒になると多量の情報を伝える。
関連性の高い文書だけが、数百項目のこの組を利用する
比率が高くなる。しかし、かかる照会を実行する唯一の
方法は、全数検索によることであって、それは現在デー
タベース検索システムに利用されている逐次動作のメイ
ンフレーム・システムでは実行不可能である。
本発明は上記大規模データベース検索システムの問題
点を解決し、高い読み出し率と高い正確さの双方に到達
できる並列処理装置によるデータベース検索法を提供す
ることを目的とする。
点を解決し、高い読み出し率と高い正確さの双方に到達
できる並列処理装置によるデータベース検索法を提供す
ることを目的とする。
上記問題点を解決するために本発明においては、例え
ば、中央コンピュータで数千の処理装置（例えばMPUと
メモリの組み合わせ）を制御し、数千の操作を並行して
実行できる単一命令多重データ（SIMD）方式計算機を、
複数のディジタルデータ処理装置として用い、適切な関
連文書を、大規模データベース中から下記ステップによ
って並列的に検索する。
ば、中央コンピュータで数千の処理装置（例えばMPUと
メモリの組み合わせ）を制御し、数千の操作を並行して
実行できる単一命令多重データ（SIMD）方式計算機を、
複数のディジタルデータ処理装置として用い、適切な関
連文書を、大規模データベース中から下記ステップによ
って並列的に検索する。
すなわち、第１の発明は、データベース中の関連文書
を検索するデータベース検索方法において、 （ａ）複数のディジタルデータ処理装置それぞれ中に、
文書の中の語を表すハッシュコードのテーブルを少なく
とも一つ格納するステップと、 （ｂ）少なくとも一つの語と、語それぞれに割当てられ
た評価点数とを持つ照会を形成するステップと、 （ｃ）照会された語が当該データベース中に存在するか
否かを下記によりテストするステップと、 ｉ）照会された語に対応する前記ハッシュコードが格納
されているテーブルの中での、ビット位置を決定する。
を検索するデータベース検索方法において、 （ａ）複数のディジタルデータ処理装置それぞれ中に、
文書の中の語を表すハッシュコードのテーブルを少なく
とも一つ格納するステップと、 （ｂ）少なくとも一つの語と、語それぞれに割当てられ
た評価点数とを持つ照会を形成するステップと、 （ｃ）照会された語が当該データベース中に存在するか
否かを下記によりテストするステップと、 ｉ）照会された語に対応する前記ハッシュコードが格納
されているテーブルの中での、ビット位置を決定する。
ii）照会された語に対応する前記ビット位置のテストは
各前記ディジタルデータ処理装置内で同時に行う。
各前記ディジタルデータ処理装置内で同時に行う。
（ｄ）あるディジタルデータ処理装置内でテストされた
全てのビット位置でハッシュコードが発見されたなら
ば、照会された語全てに関する前記評価点数を加算する
ステップと、 （ｅ）当該加算された評価点数の合計をしきい値と比較
し、該しきい値よりも当該合計の評価点数が高くなる文
書を識別するステップと を具えたことを特徴とする。
全てのビット位置でハッシュコードが発見されたなら
ば、照会された語全てに関する前記評価点数を加算する
ステップと、 （ｅ）当該加算された評価点数の合計をしきい値と比較
し、該しきい値よりも当該合計の評価点数が高くなる文
書を識別するステップと を具えたことを特徴とする。
第２の発明は、特許請求の範囲第１項に記載のデータ
ベース検索方法において、前記照会を形成するステップ
は、 （ａ）前記関連文書の一群を識別するステップと、 （ｂ）前記文書中の語が前記関連文書中で出現する頻度
を決定するステップと、 （ｃ）前記関連文書中での語の出現頻度に基づいて照会
を生成するステップと を具えたことを特徴とする。
ベース検索方法において、前記照会を形成するステップ
は、 （ａ）前記関連文書の一群を識別するステップと、 （ｂ）前記文書中の語が前記関連文書中で出現する頻度
を決定するステップと、 （ｃ）前記関連文書中での語の出現頻度に基づいて照会
を生成するステップと を具えたことを特徴とする。
第３の発明は、特許請求の範囲第１項に記載のデータ
ベース検索方法において、中央コンピュータをさらに有
し、前記評価点数を加算するステップは、 （ａ）前記ディジタルデータ処理装置内のフラッグをセ
ットし、該フラッグにより前記テーブル内に照会された
語が存在することを示すステップと、 （ｂ）前記ディジタルデータ処理装置内のフラッグがセ
ットされているならば、該フラッグにより指定された評
価点を加算すべき旨の指令を、前記中央コンピュータか
ら各前記ディジタルデータ処理装置へ同時に伝送するス
テップと を具えたことを特徴とする。
ベース検索方法において、中央コンピュータをさらに有
し、前記評価点数を加算するステップは、 （ａ）前記ディジタルデータ処理装置内のフラッグをセ
ットし、該フラッグにより前記テーブル内に照会された
語が存在することを示すステップと、 （ｂ）前記ディジタルデータ処理装置内のフラッグがセ
ットされているならば、該フラッグにより指定された評
価点を加算すべき旨の指令を、前記中央コンピュータか
ら各前記ディジタルデータ処理装置へ同時に伝送するス
テップと を具えたことを特徴とする。
第４の発明は、特許請求の範囲第１項に記載のデータ
ベース検索方法において、前記文書を識別するステップ
は、 （ａ）前記評価点数の最上位ビットをテストするステッ
プと、 （ｂ）前記最上位ビットがセットされていれば前記ディ
ジタルデータ処理装置内のフラッグをセットするステッ
プと、 （ｃ）前記フラッグがセットされているディジタルデー
タ処理装置内の評価装置内の評価点数の第２位ビットを
テストするステップと、 （ｄ）上記ステップを最下位ビットに至るまで繰り返し
行うステップと を具えたことを特徴とする。
ベース検索方法において、前記文書を識別するステップ
は、 （ａ）前記評価点数の最上位ビットをテストするステッ
プと、 （ｂ）前記最上位ビットがセットされていれば前記ディ
ジタルデータ処理装置内のフラッグをセットするステッ
プと、 （ｃ）前記フラッグがセットされているディジタルデー
タ処理装置内の評価装置内の評価点数の第２位ビットを
テストするステップと、 （ｄ）上記ステップを最下位ビットに至るまで繰り返し
行うステップと を具えたことを特徴とする。
第５の発明は、特許請求の範囲第１項に記載のデータ
ベース検索方法において、前記文書は複数テーブルのチ
ェインにより表され、その各々は当該文書の一部分であ
る表記を格納し、前記文書総点数を計算する前記ステッ
プは、 （ａ）前記チェイン内の各下位テーブルが示す部分文書
の評価点数を当該チェイン内の上位テーブルへ伝送する
ステップと、 （ｂ）全ての前記テーブルの評価点を前記チェインの最
初のテーブルの中に蓄積するステップと を具えたことを特徴とする。
ベース検索方法において、前記文書は複数テーブルのチ
ェインにより表され、その各々は当該文書の一部分であ
る表記を格納し、前記文書総点数を計算する前記ステッ
プは、 （ａ）前記チェイン内の各下位テーブルが示す部分文書
の評価点数を当該チェイン内の上位テーブルへ伝送する
ステップと、 （ｂ）全ての前記テーブルの評価点を前記チェインの最
初のテーブルの中に蓄積するステップと を具えたことを特徴とする。
第６の発明は、特許請求の範囲第１項に記載のデータ
ベース検索方法において、前記ハッシュコードのテーブ
ルの少なくとも一つを格納する前記ステップは、 （ａ）前記ディジタルデータ処理装置内の前記テーブル
のビットを初期設定して０（ゼロ）にするステップと、 （ｂ）前記文書の中の各語に対し、当該テーブルのアド
レス範囲内の値を持つ複数の独立したハッシュコードを
生成するステップと、 （ｃ）各ハッシュコード値に対応して当該テーブル内の
アドレスに一つのビットをセットするステップと を具えたことを特徴とする。
ベース検索方法において、前記ハッシュコードのテーブ
ルの少なくとも一つを格納する前記ステップは、 （ａ）前記ディジタルデータ処理装置内の前記テーブル
のビットを初期設定して０（ゼロ）にするステップと、 （ｂ）前記文書の中の各語に対し、当該テーブルのアド
レス範囲内の値を持つ複数の独立したハッシュコードを
生成するステップと、 （ｃ）各ハッシュコード値に対応して当該テーブル内の
アドレスに一つのビットをセットするステップと を具えたことを特徴とする。
記述の如く、大規模データベースの検索に、単純照会
と関連適切性の帰還法を組み合わせて用いると、理論的
に高い読み出し率と高い正確さで応答が得られることは
従来から判ってはいたが、従来の計算機による逐次的処
理法では、実行に長時間を要し不可能であった。これに
対し、本発明では、例えば、中央コンピュータで極めて
多数（数千またはそれ以上にも及ぶ）の処理装置（MPU
とメモリの組）を一斉に制御して、多数の操作を同時に
並行して実行できる単一命令多重データ（SIMD）方式計
算機を複数のディジタル処理装置として利用し、並行処
理を行うことによって上記の単純照会と関連適切性の帰
還法の組み合わせによる大規模データベースの検索が可
能になる。
と関連適切性の帰還法を組み合わせて用いると、理論的
に高い読み出し率と高い正確さで応答が得られることは
従来から判ってはいたが、従来の計算機による逐次的処
理法では、実行に長時間を要し不可能であった。これに
対し、本発明では、例えば、中央コンピュータで極めて
多数（数千またはそれ以上にも及ぶ）の処理装置（MPU
とメモリの組）を一斉に制御して、多数の操作を同時に
並行して実行できる単一命令多重データ（SIMD）方式計
算機を複数のディジタル処理装置として利用し、並行処
理を行うことによって上記の単純照会と関連適切性の帰
還法の組み合わせによる大規模データベースの検索が可
能になる。
本発明実施例では特開昭60−84661号（特願昭59−109
776号）公報に開示されている「並列プロセッサ」を利
用する。
776号）公報に開示されている「並列プロセッサ」を利
用する。
第１図に示すように、この計算機システムは、中央コ
ンピュータ10,マイクロ制御器20,並列処理集積回路（I
C）35のアレイ30,データソース40,第１バッファ兼マル
チプレクサ／デマルチプレクサ50,第1,第2,第3,第４双
方向バス制御回路60,70,75,第２バッファ兼マルチプレ
クサ／デマルチプレクサ80,データシンク90よりなる。
中央コンピュータ10は適切にプログラムした市販コンピ
ュータ、例えば商品名シンボリクス3600シリーズLISP計
算機を使えば良い。検索対象のデータベースは下記のご
とく、個々のIC35の中の処理装置／メモリ36のメモリに
格納される。
ンピュータ10,マイクロ制御器20,並列処理集積回路（I
C）35のアレイ30,データソース40,第１バッファ兼マル
チプレクサ／デマルチプレクサ50,第1,第2,第3,第４双
方向バス制御回路60,70,75,第２バッファ兼マルチプレ
クサ／デマルチプレクサ80,データシンク90よりなる。
中央コンピュータ10は適切にプログラムした市販コンピ
ュータ、例えば商品名シンボリクス3600シリーズLISP計
算機を使えば良い。検索対象のデータベースは下記のご
とく、個々のIC35の中の処理装置／メモリ36のメモリに
格納される。
マイクロ制御器20は32ビット並列バス22を介してアレ
イ30に与える一連の命令を発生させる従来の設計による
命令順序制御器である。マイクロ制御器20はアレイ30か
ら線26上の信号を受け取る。この信号はデータ出力や状
態情報として用いられる汎用、すなわちグローバル信号
である。バス22と線26は各IC35に並列に接続される。そ
の結果、マイクロ制御器20からの信号はアレイ中の各IC
35に同時に与えられ、またマイクロ制御器20に線26で与
えられる信号はアレイの全IC35からの信号出力を結合す
ることにより形成される。
イ30に与える一連の命令を発生させる従来の設計による
命令順序制御器である。マイクロ制御器20はアレイ30か
ら線26上の信号を受け取る。この信号はデータ出力や状
態情報として用いられる汎用、すなわちグローバル信号
である。バス22と線26は各IC35に並列に接続される。そ
の結果、マイクロ制御器20からの信号はアレイ中の各IC
35に同時に与えられ、またマイクロ制御器20に線26で与
えられる信号はアレイの全IC35からの信号出力を結合す
ることにより形成される。
この実施例では、アレイ30は4096（＝212）個の同一IC3
5を備え、各IC35は16（＝24）個の同一処理装置／メモ
リ36を持つ。従ってアレイ30全体は65,536（＝216）個
の同一処理装置／メモリ36を持つ。
5を備え、各IC35は16（＝24）個の同一処理装置／メモ
リ36を持つ。従ってアレイ30全体は65,536（＝216）個
の同一処理装置／メモリ36を持つ。
処理装置／メモリ36は、２種類の形態に編成され相互
接続されている：一つは従来通りの二次元格子パターン
で、もう一つは16次元超立体ネットワークである。格子
パターンでは、処理装置／メモリは矩形アレイに編成さ
れ、それぞれアレイ内で隣接する４組と接続されてい
る。このアレイの辺および隣接する４組は、北，東，
南，西として識別される。超立方体ネットワークは処理
装置群がメッセージパケットを交換して通信できるよう
にする。この配置はIC35を16次元のブールのｎ立方体の
形に編成し相互接続することによって実現される。各IC
35は、かかる相互接続ネットワークを通るメッセージの
経路を制御する論理回路を備えている。そして、各IC内
では全ての処理装置／メモリがバス接続され、各処理装
置／メモリはその他のどれとも最大16本の通信線を介し
て信号を送って交信できる。
接続されている：一つは従来通りの二次元格子パターン
で、もう一つは16次元超立体ネットワークである。格子
パターンでは、処理装置／メモリは矩形アレイに編成さ
れ、それぞれアレイ内で隣接する４組と接続されてい
る。このアレイの辺および隣接する４組は、北，東，
南，西として識別される。超立方体ネットワークは処理
装置群がメッセージパケットを交換して通信できるよう
にする。この配置はIC35を16次元のブールのｎ立方体の
形に編成し相互接続することによって実現される。各IC
35は、かかる相互接続ネットワークを通るメッセージの
経路を制御する論理回路を備えている。そして、各IC内
では全ての処理装置／メモリがバス接続され、各処理装
置／メモリはその他のどれとも最大16本の通信線を介し
て信号を送って交信できる。
第２図はさらに詳細な処理装置／メモリ36の説明図で
ある。第２図に示すように、処理装置／メモリは、ラン
ダムアクセスメモリ（RAM）250,算術論理回路（ALU）28
0,フラッグ制御器290よりなる。上記ALUは３送信源、す
なわち上記RAM内の２個のレジスタと１個のフラッグ入
力からのデータに基づいて演算を行い、２個の出力、す
なわち上記RAMレジスタの一つに書き込まれる和出力
と、上記フラッグ制御器内の特定レジスタおよび他の特
定処理装置／メモリで利用できる桁上り出力とを生ず
る。
ある。第２図に示すように、処理装置／メモリは、ラン
ダムアクセスメモリ（RAM）250,算術論理回路（ALU）28
0,フラッグ制御器290よりなる。上記ALUは３送信源、す
なわち上記RAM内の２個のレジスタと１個のフラッグ入
力からのデータに基づいて演算を行い、２個の出力、す
なわち上記RAMレジスタの一つに書き込まれる和出力
と、上記フラッグ制御器内の特定レジスタおよび他の特
定処理装置／メモリで利用できる桁上り出力とを生ず
る。
RAM250への入力は、バス152,154,156,158,ALU280から
の和出力線285、特開昭60−84661号公報第6B図中の通信
インターフェース装置（CIU）180からのメッセージパケ
ット入力線122、およびフラッグ制御器290からの書き込
み許可線298である。RAM250からの出力は、線256,257で
ある。第256,257上の信号はRAM250内の、それぞれ、レ
ジスタA,レジスタＢと呼ぶ。同じ列の二つの別のレジス
タから得られる。バス152,154,156,158はマイクロ制御
器20からの命令に従って、これらのレジスタおよびその
中の列にアドレスする。図示の例ではRAM250は記憶容量
4096ビットを持つ。
の和出力線285、特開昭60−84661号公報第6B図中の通信
インターフェース装置（CIU）180からのメッセージパケ
ット入力線122、およびフラッグ制御器290からの書き込
み許可線298である。RAM250からの出力は、線256,257で
ある。第256,257上の信号はRAM250内の、それぞれ、レ
ジスタA,レジスタＢと呼ぶ。同じ列の二つの別のレジス
タから得られる。バス152,154,156,158はマイクロ制御
器20からの命令に従って、これらのレジスタおよびその
中の列にアドレスする。図示の例ではRAM250は記憶容量
4096ビットを持つ。
フラッグ制御器290は８個の１ビットＤ形フリップ・
フロップ292、16入力の中から２入力を選択するセレク
タ294および幾つかの論理ゲートからなるアレイであ
る。フリップ・フロップ292への入力はALU280からの桁
上り出力信号，セレクタ294からの書き込み許可線298
（信号），および特開昭60−84661号公報第6B図中のプ
ログラマブル・ロジック・アレイ（PLA）150からの８本
の線よりなるバス176である。線172はアドレス線であ
り、その各線は、それぞれ別のフリップ・フロップ292
に接続され、フラッグ・ビットを書き込むフリップ・フ
ロップ１個を選択する。フリップ・フロップ292の出力
はセレクタ294に与えられる。セレクタ294への入力は、
最大16本のフラッグ信号295およびそれぞれ16本の線よ
りなる線174,176であり、その中の８本はフリップ・フ
ロップ294からのものである。さらに、線174,176は、ア
ドレス線であり、出力または継続処理のために、フラッ
グ信号線の一つを選択する。線174,176によりどのフラ
ッグが選択された場合にも、セレクタ294は線296と297
に出力を与える。
フロップ292、16入力の中から２入力を選択するセレク
タ294および幾つかの論理ゲートからなるアレイであ
る。フリップ・フロップ292への入力はALU280からの桁
上り出力信号，セレクタ294からの書き込み許可線298
（信号），および特開昭60−84661号公報第6B図中のプ
ログラマブル・ロジック・アレイ（PLA）150からの８本
の線よりなるバス176である。線172はアドレス線であ
り、その各線は、それぞれ別のフリップ・フロップ292
に接続され、フラッグ・ビットを書き込むフリップ・フ
ロップ１個を選択する。フリップ・フロップ292の出力
はセレクタ294に与えられる。セレクタ294への入力は、
最大16本のフラッグ信号295およびそれぞれ16本の線よ
りなる線174,176であり、その中の８本はフリップ・フ
ロップ294からのものである。さらに、線174,176は、ア
ドレス線であり、出力または継続処理のために、フラッ
グ信号線の一つを選択する。線174,176によりどのフラ
ッグが選択された場合にも、セレクタ294は線296と297
に出力を与える。
ALU280は、８入力１出力のデコーダ282,和出力のセレ
クタ284,桁上り出力セレクタ286よりなる。特開昭60−8
4661号公報に詳述したように、これにより、加算，論理
和，論理積を含む多くの関数に対する和および桁上り出
力を発生できる。ALU280は一度に３ビット、すなわち、
RAM250内のレジスタA,Bからの線256,257上の２ビットお
よびフラッグ制御器290からの線296上の１ビットに基づ
いて演算する。上記ALUは２出力を持つ。すなわち、RAM
250のレジスタＡに書き込まれる線285上の和、および、
フラッグ・レジスタ292に書き込まれ、この処理装置／
メモリに接続されている他の処理装置／メモリ36の入力
に与えられる線287上の桁上りである。
クタ284,桁上り出力セレクタ286よりなる。特開昭60−8
4661号公報に詳述したように、これにより、加算，論理
和，論理積を含む多くの関数に対する和および桁上り出
力を発生できる。ALU280は一度に３ビット、すなわち、
RAM250内のレジスタA,Bからの線256,257上の２ビットお
よびフラッグ制御器290からの線296上の１ビットに基づ
いて演算する。上記ALUは２出力を持つ。すなわち、RAM
250のレジスタＡに書き込まれる線285上の和、および、
フラッグ・レジスタ292に書き込まれ、この処理装置／
メモリに接続されている他の処理装置／メモリ36の入力
に与えられる線287上の桁上りである。
文書の語は、元来は綴り訂正辞書のために開発された
代用コーディングと呼ばれテーブル形式で記憶される。
Dodds,“Reducing Dictionary Size by Using a Hashin
g Techique",Communications of the ACM,Vol.25,No.6,
pp.368−370（June 1982）;Nix,“Experiense With a S
pace Efficient Way to Store a Dictionary",Communic
ations of the ACM,Vol.24,No.5,pp.297−298（May,198
1）;Peterson,“Computer Proprams for Detecting and
Correcting Spelling Errors",Communications of the
ACM,Vol.23,No.12,pp.676−687（December,1980），を
参照させたい。テーブルは任意の大きさで良いが、テー
ブル512または1024ビット長であることが望ましい。409
6ビットのRAMは512ビットの６個のテーブルまたは1024
ビットの３個のテーブルが許容され、残りのメモリはス
クラッチ・メモリとして用いられる。
代用コーディングと呼ばれテーブル形式で記憶される。
Dodds,“Reducing Dictionary Size by Using a Hashin
g Techique",Communications of the ACM,Vol.25,No.6,
pp.368−370（June 1982）;Nix,“Experiense With a S
pace Efficient Way to Store a Dictionary",Communic
ations of the ACM,Vol.24,No.5,pp.297−298（May,198
1）;Peterson,“Computer Proprams for Detecting and
Correcting Spelling Errors",Communications of the
ACM,Vol.23,No.12,pp.676−687（December,1980），を
参照させたい。テーブルは任意の大きさで良いが、テー
ブル512または1024ビット長であることが望ましい。409
6ビットのRAMは512ビットの６個のテーブルまたは1024
ビットの３個のテーブルが許容され、残りのメモリはス
クラッチ・メモリとして用いられる。
一つの文書の語をテーブルに格納するには、テーブル
をまず初期設定して“0"にする。固定数の別々のハッシ
ュコード（この実施例では10個）が文書内の重要な語そ
れぞれに対して生成される。各コードはテーブル内での
位置に対応している。例えば、512ビットのテーブルに
対し、各コードは“0"から“511"の間にある。一つの語
のために生成されたハッシュコードの各々に対して、テ
ーブル内のそのアドレスにおける対応ビットは“1"にセ
ットされる。データ格納要求を抑制するために“a"や
“the"等の無意味な語はテーブル内には含まれない。さ
らに、文書内の名詞節を拾い上げてテーブルに入力する
ために、なるべく文字列索引（text indexer）を用いる
ことが良い。これにより文書を1/3に圧縮することが可
能になる。
をまず初期設定して“0"にする。固定数の別々のハッシ
ュコード（この実施例では10個）が文書内の重要な語そ
れぞれに対して生成される。各コードはテーブル内での
位置に対応している。例えば、512ビットのテーブルに
対し、各コードは“0"から“511"の間にある。一つの語
のために生成されたハッシュコードの各々に対して、テ
ーブル内のそのアドレスにおける対応ビットは“1"にセ
ットされる。データ格納要求を抑制するために“a"や
“the"等の無意味な語はテーブル内には含まれない。さ
らに、文書内の名詞節を拾い上げてテーブルに入力する
ために、なるべく文字列索引（text indexer）を用いる
ことが良い。これにより文書を1/3に圧縮することが可
能になる。
データベースの各文書は、SIMD方式計算機の一つ以上
の処理装置／メモリ内の一つ以上のテーブル内に、この
ような形で格納される。もしある文書が、一つのテーブ
ルに格納すべき最大数以上の語を含む場合には、追加テ
ーブルが用いられる。例えば、90語の文書がデータベー
スに格納されるとき、各テーブルに30語が含まれるなら
ば、合計で３個のテーブルが使用される。単一文書を含
むテーブルの組はチェインと呼ばれる。一つのチェイン
内の各テーブルは、なるべく物理的に別の処理装置内に
位置し、そして各テーブルはそれぞれのメモリの同じ個
所に位置しているのが良い。あるいは、また、全てのテ
ーブルを物理的に同じ処理装置内に置くこともできる。
の処理装置／メモリ内の一つ以上のテーブル内に、この
ような形で格納される。もしある文書が、一つのテーブ
ルに格納すべき最大数以上の語を含む場合には、追加テ
ーブルが用いられる。例えば、90語の文書がデータベー
スに格納されるとき、各テーブルに30語が含まれるなら
ば、合計で３個のテーブルが使用される。単一文書を含
むテーブルの組はチェインと呼ばれる。一つのチェイン
内の各テーブルは、なるべく物理的に別の処理装置内に
位置し、そして各テーブルはそれぞれのメモリの同じ個
所に位置しているのが良い。あるいは、また、全てのテ
ーブルを物理的に同じ処理装置内に置くこともできる。
処理装置／メモリ内のテーブルに格納されている文書
の中の一つの語の存在を調べるために、その語に対する
10個のハッシュコードに対応するビットを、上記処理装
置／メモリの各テーブル内でチェックする。もしテーブ
ル内の10個のビットのどれもが“0"ならば、当該語はそ
のテーブル内には絶対に存在せず、否定応答を与える。
もし全てのビットが“1"ならば、当該語は多分存在し、
肯定応答を与える。このアルゴリズムは誤りで否定を生
じないけれども、誤りで肯定の可能性がある。このアル
ゴリズムにおける誤りの肯定の確率は、各テーブルに含
まれる語数とテーブルの大きさ、および各語にあてがっ
たビット数に依存する。各語には10ビットあてがった51
2ビットのテーブルでは、テーブルに15個を含む場合に
誤りの肯定の確率は数百万分の一、20語のテーブルの場
合に十万分の一、30語のテーブルの場合に十万分の三
十、となる。最適システム性能を得るには、テーブルを
約15〜30語に限定することが好ましいと思われる。
の中の一つの語の存在を調べるために、その語に対する
10個のハッシュコードに対応するビットを、上記処理装
置／メモリの各テーブル内でチェックする。もしテーブ
ル内の10個のビットのどれもが“0"ならば、当該語はそ
のテーブル内には絶対に存在せず、否定応答を与える。
もし全てのビットが“1"ならば、当該語は多分存在し、
肯定応答を与える。このアルゴリズムは誤りで否定を生
じないけれども、誤りで肯定の可能性がある。このアル
ゴリズムにおける誤りの肯定の確率は、各テーブルに含
まれる語数とテーブルの大きさ、および各語にあてがっ
たビット数に依存する。各語には10ビットあてがった51
2ビットのテーブルでは、テーブルに15個を含む場合に
誤りの肯定の確率は数百万分の一、20語のテーブルの場
合に十万分の一、30語のテーブルの場合に十万分の三
十、となる。最適システム性能を得るには、テーブルを
約15〜30語に限定することが好ましいと思われる。
第３図，第４図は本発明に係るシステムで用いられる
全数検索方を示す。ユーザがコンピュータ端末から文書
にアクセスできるように、文書は中央コンピュータに完
全原文の形で格納されており、このデータベースにアク
セスするために表示端末が備えられている。各文書中の
重要な語はハッシュコード化され、そのハッシュコード
はSIMD計算機の処理装置／メモリのメモリ内の一つ以上
のテーブルに格納される。上述のように、無意味な語は
無視され、記憶されるのは一般に名詞節に限られる。検
索を始める際、ユーザは関心のある題目の輪郭を描く、
少なくとも１語、好ましくは数語を選択する。彼はこれ
らの語を中央コンピュータに入力し、かつこの検索での
彼の各語に対する評価を反映させてそれぞれの語に点数
を割り当てる。中央コンピュータは、これらの語の一つ
以上が存在するか否かを、中央コンピュータに格納され
ている文書の完全原文について調査し、もし適用できる
ときは、その文書に対する点数を算出し、ユーザに対
し、この方法で選択された複数文書の名を知らせる。そ
れからユーザは、これらの文書を調べ、中央コンピュー
タへどの文書が関連があるか、また「良い」、どれが関
連がない。または「悪い」と知らせる。コンピュータは
次にこれらの文書を調べ、適当な検索語を突き止め、こ
れらの語から照会は形成する。また、コンピュータは、
例えば当該語が現れ良い文書の数による、その評価に基
づいて、これらの語に点数を割り当てる。特別な語の発
生頻度（珍しい語は一層価値がある）とか、ある語が標
題や見出しに現れたとか、ユーザがその語に明白に注意
したか、などのような、その他のパラメータは単純照会
を構成するときに利用される。でき上がった照会（命
令）は数百語を含むことがある。
全数検索方を示す。ユーザがコンピュータ端末から文書
にアクセスできるように、文書は中央コンピュータに完
全原文の形で格納されており、このデータベースにアク
セスするために表示端末が備えられている。各文書中の
重要な語はハッシュコード化され、そのハッシュコード
はSIMD計算機の処理装置／メモリのメモリ内の一つ以上
のテーブルに格納される。上述のように、無意味な語は
無視され、記憶されるのは一般に名詞節に限られる。検
索を始める際、ユーザは関心のある題目の輪郭を描く、
少なくとも１語、好ましくは数語を選択する。彼はこれ
らの語を中央コンピュータに入力し、かつこの検索での
彼の各語に対する評価を反映させてそれぞれの語に点数
を割り当てる。中央コンピュータは、これらの語の一つ
以上が存在するか否かを、中央コンピュータに格納され
ている文書の完全原文について調査し、もし適用できる
ときは、その文書に対する点数を算出し、ユーザに対
し、この方法で選択された複数文書の名を知らせる。そ
れからユーザは、これらの文書を調べ、中央コンピュー
タへどの文書が関連があるか、また「良い」、どれが関
連がない。または「悪い」と知らせる。コンピュータは
次にこれらの文書を調べ、適当な検索語を突き止め、こ
れらの語から照会は形成する。また、コンピュータは、
例えば当該語が現れ良い文書の数による、その評価に基
づいて、これらの語に点数を割り当てる。特別な語の発
生頻度（珍しい語は一層価値がある）とか、ある語が標
題や見出しに現れたとか、ユーザがその語に明白に注意
したか、などのような、その他のパラメータは単純照会
を構成するときに利用される。でき上がった照会（命
令）は数百語を含むことがある。
この照会は次いでSIMD計算機のメモリに格納されたハ
ッシュ・テーブルを検索するのに用いられる。照会内の
各語に対し、中央コンピュータはルック・アップ・テー
ブルから、値、すなわち、対応するハッシュコードの10
ビットが格納されているハッシュ・テーブル内のアドレ
スを決める。中央コンピュータは次いで各処理装置／メ
モリにこれらのアドレスそれぞれにおけるビットを読む
ように命令する。読まれたビットはフラッグを立てるの
に用いられ、このフラッグは、フラッグの次の値を決め
るために読まれた次のビットと共に論理積演算される。
もしハッシュコードの何れかのビットが“0"（ゼロ）な
らば、フラッグは“0"（ゼロ）になる。そして問題の語
がそのテーブルに格納されていないことを示しているの
で、このテストは失敗である。もしテストが成功すれ
ば、フラッグは“1"で、その語はそのテーブルで表され
た文書中に存在するとみなされ、その語に関する点数が
その文書に与えられ、その文書中の他の語に関する全て
の点数に累計される。
ッシュ・テーブルを検索するのに用いられる。照会内の
各語に対し、中央コンピュータはルック・アップ・テー
ブルから、値、すなわち、対応するハッシュコードの10
ビットが格納されているハッシュ・テーブル内のアドレ
スを決める。中央コンピュータは次いで各処理装置／メ
モリにこれらのアドレスそれぞれにおけるビットを読む
ように命令する。読まれたビットはフラッグを立てるの
に用いられ、このフラッグは、フラッグの次の値を決め
るために読まれた次のビットと共に論理積演算される。
もしハッシュコードの何れかのビットが“0"（ゼロ）な
らば、フラッグは“0"（ゼロ）になる。そして問題の語
がそのテーブルに格納されていないことを示しているの
で、このテストは失敗である。もしテストが成功すれ
ば、フラッグは“1"で、その語はそのテーブルで表され
た文書中に存在するとみなされ、その語に関する点数が
その文書に与えられ、その文書中の他の語に関する全て
の点数に累計される。
各文書に対する点数をこの照会の全検索が完了するま
での各個の処理装置／メモリに格納しておくと、各個の
処理装置／メモリから中央コンピュータへの通信が最小
限に抑えられて都合がよい。フラッグ・ビットが“1"な
らば点数を累計するようにとの命令を全処理装置／メモ
リへ伝送することによって、各語がテストされた後、点
数は集計される。
での各個の処理装置／メモリに格納しておくと、各個の
処理装置／メモリから中央コンピュータへの通信が最小
限に抑えられて都合がよい。フラッグ・ビットが“1"な
らば点数を累計するようにとの命令を全処理装置／メモ
リへ伝送することによって、各語がテストされた後、点
数は集計される。
文書が複数のテーブル間に分割されている場合は、各
テーブルの値はチェインの最初のテーブルへパスされ
て、そこで集計される。
テーブルの値はチェインの最初のテーブルへパスされ
て、そこで集計される。
処理装置／メモリに格納されていた点数を、大きさの
順にソートすることによって、最大点数を持つ文書が特
定される。ソート用のプログラムは当業者間で良く知ら
れており、そのSIMD計算機けの適用法は前記記載から明
らかであろう。あるいはまた、点数を調べて最大点数を
決定し、一連のかかる最大値に関連した文書の決定を処
理装置／メモリから得ることができる。このようなテス
トを行うために、中央コンピュータは、各処理装置／メ
モリに格納されている点数の最上位ビットを同時にテス
トする。これは、全ての処理装置／メモリで点数が全て
て同じアドレスに格納されていれば、実行は容易であ
る。このテストは、以下の形態、すなわち、最初のフラ
ッグを立て、そしてもし最上位ビットが“0"（ゼロ）な
らば、テストの以後の部分を無視し、さらにもし最上位
ビットが“1"ならば、第１図のグローバル信号線26へ出
力を発生するようにという命令の形態をしている。どの
処理装置／メモリからも線26上に出力信号が入って来な
かったならば、中央コンピュータは全てのフラッグとそ
の処理装置／メモリをリセットし、次の最上位ビットに
ついて新たにテストを始める。もし出力が得られたなら
ば、中央コンピュータはテストの次のサイクルに入り、
まだテスト中の処理装置／メモリへ、第２のフラッグを
立て、次の最上位ビットをテストして“0"（ゼロ）なら
ばテスト以後の部分を無視し、そのビットが“1"ならば
グローバル信号線に出力を出すようにとの命令を出す。
グローバル線上に出力が得られなかったならば、テスト
のそのサイクルの間停止されていた処理装置／メモリの
第２のフラッグがリセットされ、これらの処理装置／メ
モリは再活性化され、そして第３の最上位ビットがテス
トされる。しかし、出力が得られたならば、第２のフラ
ッグが立てられていた処理装置／メモリの第１のフラッ
グが立てられ、中央コンピュータはテストの次のサイク
ルに入る。中央コンピュータは第３の最上位ビットをテ
ストする。そして以下同様である。このプロセスの結
果、最大の点数を持つ処理装置／メモリはアレイの中で
隔離され、その点数に関連した文書は識別される。その
文書に関連した点数は“0"（ゼロ）にセットされ、次に
高い点数を持つ文書を発見するために、プロセスは繰り
返される。そして、以下同様である。
順にソートすることによって、最大点数を持つ文書が特
定される。ソート用のプログラムは当業者間で良く知ら
れており、そのSIMD計算機けの適用法は前記記載から明
らかであろう。あるいはまた、点数を調べて最大点数を
決定し、一連のかかる最大値に関連した文書の決定を処
理装置／メモリから得ることができる。このようなテス
トを行うために、中央コンピュータは、各処理装置／メ
モリに格納されている点数の最上位ビットを同時にテス
トする。これは、全ての処理装置／メモリで点数が全て
て同じアドレスに格納されていれば、実行は容易であ
る。このテストは、以下の形態、すなわち、最初のフラ
ッグを立て、そしてもし最上位ビットが“0"（ゼロ）な
らば、テストの以後の部分を無視し、さらにもし最上位
ビットが“1"ならば、第１図のグローバル信号線26へ出
力を発生するようにという命令の形態をしている。どの
処理装置／メモリからも線26上に出力信号が入って来な
かったならば、中央コンピュータは全てのフラッグとそ
の処理装置／メモリをリセットし、次の最上位ビットに
ついて新たにテストを始める。もし出力が得られたなら
ば、中央コンピュータはテストの次のサイクルに入り、
まだテスト中の処理装置／メモリへ、第２のフラッグを
立て、次の最上位ビットをテストして“0"（ゼロ）なら
ばテスト以後の部分を無視し、そのビットが“1"ならば
グローバル信号線に出力を出すようにとの命令を出す。
グローバル線上に出力が得られなかったならば、テスト
のそのサイクルの間停止されていた処理装置／メモリの
第２のフラッグがリセットされ、これらの処理装置／メ
モリは再活性化され、そして第３の最上位ビットがテス
トされる。しかし、出力が得られたならば、第２のフラ
ッグが立てられていた処理装置／メモリの第１のフラッ
グが立てられ、中央コンピュータはテストの次のサイク
ルに入る。中央コンピュータは第３の最上位ビットをテ
ストする。そして以下同様である。このプロセスの結
果、最大の点数を持つ処理装置／メモリはアレイの中で
隔離され、その点数に関連した文書は識別される。その
文書に関連した点数は“0"（ゼロ）にセットされ、次に
高い点数を持つ文書を発見するために、プロセスは繰り
返される。そして、以下同様である。
単純照会法を用いて沢山の文書が検索されることがあ
るから、検索された文書の数を管理可能な数に制限する
方法を用いることが好ましい。これは、最良の文書（す
なわち最高点の文書）をまず検索し、もし十分な数の文
書が検索されているならば、そこで止めてしまえば良
い。または、点数にしきい値を設け、文書の総点数がし
きい値以下のものは検索しないことにしても良い。
るから、検索された文書の数を管理可能な数に制限する
方法を用いることが好ましい。これは、最良の文書（す
なわち最高点の文書）をまず検索し、もし十分な数の文
書が検索されているならば、そこで止めてしまえば良
い。または、点数にしきい値を設け、文書の総点数がし
きい値以下のものは検索しないことにしても良い。
本発明のシステムを利用することによりユーザは高い
読み出し率と高い正確さの双方を得られることが判っ
た。従来は実際的でなかった全数検索法が使えるように
なった。検索が並行して行われので、検索時間は非常に
早くなった。例えば、112メガバイトのデータベースに
対する200語の単純照会は、60ミリセカンドで実行され
る。
読み出し率と高い正確さの双方を得られることが判っ
た。従来は実際的でなかった全数検索法が使えるように
なった。検索が並行して行われので、検索時間は非常に
早くなった。例えば、112メガバイトのデータベースに
対する200語の単純照会は、60ミリセカンドで実行され
る。
当業者には明らかなように、上記発明の範囲内で沢山
の変形が可能である。本発明は、単純照会と関連性帰還
を結合した検索法の並行処理実行に関して説明された
が、ブール検索法その他の全数検索法などを利用するこ
ともできる。
の変形が可能である。本発明は、単純照会と関連性帰還
を結合した検索法の並行処理実行に関して説明された
が、ブール検索法その他の全数検索法などを利用するこ
ともできる。
以上説明したように本発明によれば、大規模データベ
ースの検索を、高い読み出し率と高い正確さを並立させ
ながら、短時間で実行できる。
ースの検索を、高い読み出し率と高い正確さを並立させ
ながら、短時間で実行できる。
第１図，第２図は本発明に用いるSIMD計算機の模式的詳
細図、 第３図は探索，探索の簡単な流れ図、 第４図は照会命令生成過程の流れ図である。 10…中央コンピュータ、20…マイクロ制御器、30…アレ
イ、35…並列処理IC、36…処理装置／メモリ、250…RA
M、280…ALU。
細図、 第３図は探索，探索の簡単な流れ図、 第４図は照会命令生成過程の流れ図である。 10…中央コンピュータ、20…マイクロ制御器、30…アレ
イ、35…並列処理IC、36…処理装置／メモリ、250…RA
M、280…ALU。
フロントページの続き (56)参考文献 Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ（1986−12）Ｐ．1229− 1239
Claims (6)
- 【請求項１】データベース中の関連文書を検索するデー
タベース検索方法において、 （ａ）複数のディジタルデータ処理装置それぞれの中
に、文書の中の語を表すハッシュコードのテーブルを少
なくとも一つ格納するステップと、 （ｂ）少なくとも一つの語と、語それぞれに割当てられ
た評価点数とを持つ照会を形成するステップと、 （ｃ）照会された語が当該データベース中に存在するか
否かを下記によりテストするステップと、 ｉ）照会された語に対応する前記ハッシュコードが格納
されているテーブルの中での、ビット位置を決定する。 ii）照会された語に対応する前記ビット位置のテストは
各前記ディジタルデータ処理装置内で同時に行う。 （ｄ）あるディジタルデータ処理装置内でテストされた
全てのビット位置でハッシュコードが発見されたなら
ば、照会された語全てに関する前記評価点数を加算する
ステップと、 （ｅ）当該加算された評価点数の合計をしきい値と比較
し、該しきい値よりも当該合計の評価点数が高くなる文
書を識別するステップと を具えたことを特徴とするデータベース検索方法。 - 【請求項２】特許請求の範囲第１項に記載のデータベー
ス検索方法において、前記照会を形成するステップは、 （ａ）前記関連文書の一群を識別するステップと、 （ｂ）前記文書中の語が前記関連文書中で出現する頻度
を決定するステップと、 （ｃ）前記関連文書中での語の出現頻度に基づいて照会
を生成するステップと を具えたことを特徴とするデータベース検索方法。 - 【請求項３】特許請求の範囲第１項に記載のデータベー
ス検索方法において、中央コンピュータをさらに有し、
前記評価点数を加算するステップは、 （ａ）前記ディジタルデータ処理装置内のフラッグをセ
ットし、該フラッグにより前記テーブル内に照会された
語が存在することを示すステップと、 （ｂ）前記ディジタルデータ処理装置内のフラッグがセ
ットされているならば、該フラッグにより指定された評
価点を加算すべき旨の指令を、前記中央コンピュータか
ら各前記ディジタルデータ処理装置へ同時に伝送するス
テップと を具えたことを特徴とするデータベース検索方法。 - 【請求項４】特許請求の範囲第１項に記載のデータベー
ス検索方法において、前記文書を識別するステップは、 （ａ）前記評価点数の最上位ビットをテストするステッ
プと、 （ｂ）前記最上位ビットがセットされていれば前記ディ
ジタルデータ処理装置内のフラッグをセットするステッ
プと、 （ｃ）前記フラッグがセットされているディジタルデー
タ処理装置内の評価点数の第２位ビットをテストするス
テップと、 （ｄ）上記ステップを最下位ビットに至るまで繰り返し
行うステップと を具えたことを特徴とするデータベース検索方法。 - 【請求項５】特許請求の範囲第１項に記載のデータベー
ス検索方法において、前記文書は複数テーブルのチェイ
ンにより表され、その各々は当該文書の一部分である表
記を格納し、前記文書総点数を計算する前記ステップ
は、 （ａ）前記チェイン内の各下位テーブルが示す部分文書
の評価点数を当該チェイン内の上位テーブルへ伝送する
ステップと、 （ｂ）全ての前記テーブルの評価点を前記チェインの最
初のテーブルの中に蓄積するステップと を具えたことを特徴とするデータベース検索方法。 - 【請求項６】特許請求の範囲第１項に記載のデータベー
ス検索方法において、前記ハッシュコードのテーブルの
少なくとも一つを格納する前記ステップは、 （ａ）前記ディジタルデータ処理装置内の前記テーブル
のビットを初期設定して０（ゼロ）にするステップと、 （ｂ）前記文書の中の各語に対し、当該テーブルのアド
レス範囲内の値を持つ複数の独立したハッシュコードを
生成するステップと、 （ｃ）各ハッシュコード値に対応して当該テーブル内の
アドレスに一つのビットをセットするステップと を具えたことを特徴とするデータベース検索方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/878,532 US4870568A (en) | 1986-06-25 | 1986-06-25 | Method for searching a database system including parallel processors |
| US878532 | 1986-06-25 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6359626A JPS6359626A (ja) | 1988-03-15 |
| JPH083817B2 true JPH083817B2 (ja) | 1996-01-17 |
Family
ID=25372216
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62156716A Expired - Lifetime JPH083817B2 (ja) | 1986-06-25 | 1987-06-25 | データベース検索方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US4870568A (ja) |
| EP (1) | EP0251594B1 (ja) |
| JP (1) | JPH083817B2 (ja) |
| CA (1) | CA1282496C (ja) |
| DE (1) | DE3750492T2 (ja) |
Families Citing this family (88)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| NL8603193A (nl) * | 1986-12-16 | 1988-07-18 | Hollandse Signaalapparaten Bv | Database-systeem. |
| US5170482A (en) * | 1987-08-14 | 1992-12-08 | Regents Of The University Of Minnesota | Improved hypercube topology for multiprocessor computer systems |
| JP2509947B2 (ja) * | 1987-08-19 | 1996-06-26 | 富士通株式会社 | ネットワ−ク制御方式 |
| US5257395A (en) * | 1988-05-13 | 1993-10-26 | International Business Machines Corporation | Methods and circuit for implementing and arbitrary graph on a polymorphic mesh |
| US5088048A (en) * | 1988-06-10 | 1992-02-11 | Xerox Corporation | Massively parallel propositional reasoning |
| US5408655A (en) * | 1989-02-27 | 1995-04-18 | Apple Computer, Inc. | User interface system and method for traversing a database |
| US5469354A (en) * | 1989-06-14 | 1995-11-21 | Hitachi, Ltd. | Document data processing method and apparatus for document retrieval |
| JPH03129472A (ja) * | 1989-07-31 | 1991-06-03 | Ricoh Co Ltd | 文書検索装置における処理方法 |
| US5170370A (en) * | 1989-11-17 | 1992-12-08 | Cray Research, Inc. | Vector bit-matrix multiply functional unit |
| US5210870A (en) * | 1990-03-27 | 1993-05-11 | International Business Machines | Database sort and merge apparatus with multiple memory arrays having alternating access |
| US5367677A (en) * | 1990-05-11 | 1994-11-22 | Thinking Machines Corporation | System for iterated generation from an array of records of a posting file with row segments based on column entry value ranges |
| US5761655A (en) * | 1990-06-06 | 1998-06-02 | Alphatronix, Inc. | Image file storage and retrieval system |
| US5757983A (en) * | 1990-08-09 | 1998-05-26 | Hitachi, Ltd. | Document retrieval method and system |
| US5321833A (en) * | 1990-08-29 | 1994-06-14 | Gte Laboratories Incorporated | Adaptive ranking system for information retrieval |
| US5325500A (en) * | 1990-12-14 | 1994-06-28 | Xerox Corporation | Parallel processing units on a substrate, each including a column of memory |
| US5488725A (en) * | 1991-10-08 | 1996-01-30 | West Publishing Company | System of document representation retrieval by successive iterated probability sampling |
| US5388259A (en) * | 1992-05-15 | 1995-02-07 | Bell Communications Research, Inc. | System for accessing a database with an iterated fuzzy query notified by retrieval response |
| US5511186A (en) * | 1992-11-18 | 1996-04-23 | Mdl Information Systems, Inc. | System and methods for performing multi-source searches over heterogeneous databases |
| US5819259A (en) * | 1992-12-17 | 1998-10-06 | Hartford Fire Insurance Company | Searching media and text information and categorizing the same employing expert system apparatus and methods |
| US5548770A (en) * | 1993-02-25 | 1996-08-20 | Data Parallel Systems, Inc. | Method and apparatus for improving retrieval of data from a database |
| US5809212A (en) * | 1993-07-12 | 1998-09-15 | New York University | Conditional transition networks and computational processes for use interactive computer-based systems |
| US5742806A (en) | 1994-01-31 | 1998-04-21 | Sun Microsystems, Inc. | Apparatus and method for decomposing database queries for database management system including multiprocessor digital data processing system |
| US5499360A (en) * | 1994-02-28 | 1996-03-12 | Panasonic Technolgies, Inc. | Method for proximity searching with range testing and range adjustment |
| US6081804A (en) * | 1994-03-09 | 2000-06-27 | Novell, Inc. | Method and apparatus for performing rapid and multi-dimensional word searches |
| US5553139A (en) * | 1994-04-04 | 1996-09-03 | Novell, Inc. | Method and apparatus for electronic license distribution |
| US5522077A (en) * | 1994-05-19 | 1996-05-28 | Ontos, Inc. | Object oriented network system for allocating ranges of globally unique object identifiers from a server process to client processes which release unused identifiers |
| US5715443A (en) * | 1994-07-25 | 1998-02-03 | Apple Computer, Inc. | Method and apparatus for searching for information in a data processing system and for providing scheduled search reports in a summary format |
| US5623652A (en) * | 1994-07-25 | 1997-04-22 | Apple Computer, Inc. | Method and apparatus for searching for information in a network and for controlling the display of searchable information on display devices in the network |
| US5530939A (en) * | 1994-09-29 | 1996-06-25 | Bell Communications Research, Inc. | Method and system for broadcasting and querying a database using a multi-function module |
| US5946678A (en) * | 1995-01-11 | 1999-08-31 | Philips Electronics North America Corporation | User interface for document retrieval |
| US5758149A (en) * | 1995-03-17 | 1998-05-26 | Unisys Corporation | System for optimally processing a transaction and a query to the same database concurrently |
| US5742807A (en) * | 1995-05-31 | 1998-04-21 | Xerox Corporation | Indexing system using one-way hash for document service |
| US5799298A (en) * | 1995-08-07 | 1998-08-25 | International Business Machines Corporation | Method of indirect specification of user preferences |
| JP3842319B2 (ja) * | 1995-11-08 | 2006-11-08 | 富士通株式会社 | 情報検索システム |
| US5926811A (en) * | 1996-03-15 | 1999-07-20 | Lexis-Nexis | Statistical thesaurus, method of forming same, and use thereof in query expansion in automated text searching |
| US5905860A (en) * | 1996-03-15 | 1999-05-18 | Novell, Inc. | Fault tolerant electronic licensing system |
| US5758069A (en) * | 1996-03-15 | 1998-05-26 | Novell, Inc. | Electronic licensing system |
| US5909681A (en) * | 1996-03-25 | 1999-06-01 | Torrent Systems, Inc. | Computer system and computerized method for partitioning data for parallel processing |
| US7308485B2 (en) * | 1997-04-15 | 2007-12-11 | Gracenote, Inc. | Method and system for accessing web pages based on playback of recordings |
| US7167857B2 (en) | 1997-04-15 | 2007-01-23 | Gracenote, Inc. | Method and system for finding approximate matches in database |
| US5987525A (en) * | 1997-04-15 | 1999-11-16 | Cddb, Inc. | Network delivery of interactive entertainment synchronized to playback of audio recordings |
| US7779020B2 (en) | 2002-03-01 | 2010-08-17 | International Business Machines Corporation | Small-footprint applicative query interpreter method, system and program product |
| US6807632B1 (en) * | 1999-01-21 | 2004-10-19 | Emc Corporation | Content addressable information encapsulation, representation, and transfer |
| US6119215A (en) * | 1998-06-29 | 2000-09-12 | Cisco Technology, Inc. | Synchronization and control system for an arrayed processing engine |
| US6513108B1 (en) | 1998-06-29 | 2003-01-28 | Cisco Technology, Inc. | Programmable processing engine for efficiently processing transient data |
| US6195739B1 (en) | 1998-06-29 | 2001-02-27 | Cisco Technology, Inc. | Method and apparatus for passing data among processor complex stages of a pipelined processing engine |
| US6101599A (en) * | 1998-06-29 | 2000-08-08 | Cisco Technology, Inc. | System for context switching between processing elements in a pipeline of processing elements |
| US6836838B1 (en) | 1998-06-29 | 2004-12-28 | Cisco Technology, Inc. | Architecture for a processor complex of an arrayed pipelined processing engine |
| US6356548B1 (en) | 1998-06-29 | 2002-03-12 | Cisco Technology, Inc. | Pooled receive and transmit queues to access a shared bus in a multi-port switch asic |
| US6728839B1 (en) | 1998-10-28 | 2004-04-27 | Cisco Technology, Inc. | Attribute based memory pre-fetching technique |
| US6173386B1 (en) | 1998-12-14 | 2001-01-09 | Cisco Technology, Inc. | Parallel processor with debug capability |
| US6385747B1 (en) | 1998-12-14 | 2002-05-07 | Cisco Technology, Inc. | Testing of replicated components of electronic device |
| US6920562B1 (en) | 1998-12-18 | 2005-07-19 | Cisco Technology, Inc. | Tightly coupled software protocol decode with hardware data encryption |
| US6529983B1 (en) | 1999-11-03 | 2003-03-04 | Cisco Technology, Inc. | Group and virtual locking mechanism for inter processor synchronization |
| US6681341B1 (en) | 1999-11-03 | 2004-01-20 | Cisco Technology, Inc. | Processor isolation method for integrated multi-processor systems |
| CA2403874A1 (en) * | 2000-03-28 | 2001-12-06 | Dana-Farber Cancer Institute, Inc. | Molecular database for antibody characterization |
| US6892237B1 (en) | 2000-03-28 | 2005-05-10 | Cisco Technology, Inc. | Method and apparatus for high-speed parsing of network messages |
| US6505269B1 (en) | 2000-05-16 | 2003-01-07 | Cisco Technology, Inc. | Dynamic addressing mapping to eliminate memory resource contention in a symmetric multiprocessor system |
| AU2001296604A1 (en) * | 2000-10-04 | 2002-04-15 | Pyxsys Corporation | Simd system and method |
| US20050010604A1 (en) * | 2001-12-05 | 2005-01-13 | Digital Networks North America, Inc. | Automatic identification of DVD title using internet technologies and fuzzy matching techniques |
| US7447872B2 (en) * | 2002-05-30 | 2008-11-04 | Cisco Technology, Inc. | Inter-chip processor control plane communication |
| US6990483B2 (en) * | 2002-07-08 | 2006-01-24 | International Business Machines Corporation | Method, system and program product for automatically retrieving documents |
| US7945581B2 (en) * | 2002-11-14 | 2011-05-17 | Lexisnexis Risk Data Management, Inc. | Global-results processing matrix for processing queries |
| US8676843B2 (en) * | 2002-11-14 | 2014-03-18 | LexiNexis Risk Data Management Inc. | Failure recovery in a parallel-processing database system |
| US7293024B2 (en) | 2002-11-14 | 2007-11-06 | Seisint, Inc. | Method for sorting and distributing data among a plurality of nodes |
| US7240059B2 (en) * | 2002-11-14 | 2007-07-03 | Seisint, Inc. | System and method for configuring a parallel-processing database system |
| US7185003B2 (en) * | 2002-11-14 | 2007-02-27 | Seisint, Inc. | Query scheduling in a parallel-processing database system |
| US6968335B2 (en) | 2002-11-14 | 2005-11-22 | Sesint, Inc. | Method and system for parallel processing of database queries |
| US7403942B1 (en) | 2003-02-04 | 2008-07-22 | Seisint, Inc. | Method and system for processing data records |
| US7912842B1 (en) | 2003-02-04 | 2011-03-22 | Lexisnexis Risk Data Management Inc. | Method and system for processing and linking data records |
| US7657540B1 (en) | 2003-02-04 | 2010-02-02 | Seisint, Inc. | Method and system for linking and delinking data records |
| US7720846B1 (en) | 2003-02-04 | 2010-05-18 | Lexisnexis Risk Data Management, Inc. | System and method of using ghost identifiers in a database |
| EP1457889A1 (en) * | 2003-03-13 | 2004-09-15 | Koninklijke Philips Electronics N.V. | Improved fingerprint matching method and system |
| US8924654B1 (en) * | 2003-08-18 | 2014-12-30 | Cray Inc. | Multistreamed processor vector packing method and apparatus |
| WO2005064487A1 (ja) * | 2003-12-25 | 2005-07-14 | Shinji Furusho | 分散メモリ型情報処理システム |
| US20050246194A1 (en) * | 2004-04-06 | 2005-11-03 | Lundberg Steven W | System and method for information disclosure statement management |
| US7574424B2 (en) * | 2004-10-13 | 2009-08-11 | Sybase, Inc. | Database system with methodology for parallel schedule generation in a query optimizer |
| US8126870B2 (en) * | 2005-03-28 | 2012-02-28 | Sybase, Inc. | System and methodology for parallel query optimization using semantic-based partitioning |
| EP2001583A4 (en) * | 2006-03-09 | 2010-09-01 | Gracenote Inc | METHOD AND SYSTEM FOR NAVIGATION BETWEEN MEDIA |
| US8266168B2 (en) * | 2008-04-24 | 2012-09-11 | Lexisnexis Risk & Information Analytics Group Inc. | Database systems and methods for linking records and entity representations with sufficiently high confidence |
| CA2723204C (en) * | 2008-07-02 | 2013-04-09 | Lexisnexis Risk & Information Analytics Group, Inc. | Statistical measure and calibration of search criteria where one or both of the search criteria and database is incomplete |
| US8458441B2 (en) * | 2009-05-14 | 2013-06-04 | Microsoft Corporation | Vector extensions to an interpreted general expression evaluator in a database system |
| US9411859B2 (en) | 2009-12-14 | 2016-08-09 | Lexisnexis Risk Solutions Fl Inc | External linking based on hierarchical level weightings |
| US9189505B2 (en) | 2010-08-09 | 2015-11-17 | Lexisnexis Risk Data Management, Inc. | System of and method for entity representation splitting without the need for human interaction |
| US9442930B2 (en) | 2011-09-07 | 2016-09-13 | Venio Inc. | System, method and computer program product for automatic topic identification using a hypertext corpus |
| US9442928B2 (en) | 2011-09-07 | 2016-09-13 | Venio Inc. | System, method and computer program product for automatic topic identification using a hypertext corpus |
| US9378246B2 (en) * | 2012-05-03 | 2016-06-28 | Hiromichi Watari | Systems and methods of accessing distributed data |
| US10303687B2 (en) | 2016-09-01 | 2019-05-28 | Parallel Universe, Inc. | Concurrent processing of data sources |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4152762A (en) * | 1976-03-03 | 1979-05-01 | Operating Systems, Inc. | Associative crosspoint processor system |
| US4118788A (en) * | 1977-03-07 | 1978-10-03 | Bell Telephone Laboratories, Incorporated | Associative information retrieval |
| US4255796A (en) * | 1978-02-14 | 1981-03-10 | Bell Telephone Laboratories, Incorporated | Associative information retrieval continuously guided by search status feedback |
| US4358824A (en) * | 1979-12-28 | 1982-11-09 | International Business Machines Corporation | Office correspondence storage and retrieval system |
| US4445171A (en) * | 1981-04-01 | 1984-04-24 | Teradata Corporation | Data processing systems and methods |
| US4468728A (en) * | 1981-06-25 | 1984-08-28 | At&T Bell Laboratories | Data structure and search method for a data base management system |
| US4464650A (en) * | 1981-08-10 | 1984-08-07 | Sperry Corporation | Apparatus and method for compressing data signals and restoring the compressed data signals |
| US4495566A (en) * | 1981-09-30 | 1985-01-22 | System Development Corporation | Method and means using digital data processing means for locating representations in a stored textual data base |
| US4451901A (en) * | 1982-01-21 | 1984-05-29 | General Electric Company | High speed search system |
| US4554631A (en) * | 1983-07-13 | 1985-11-19 | At&T Bell Laboratories | Keyword search automatic limiting method |
-
1986
- 1986-06-25 US US06/878,532 patent/US4870568A/en not_active Expired - Lifetime
-
1987
- 1987-06-16 CA CA000539813A patent/CA1282496C/en not_active Expired - Fee Related
- 1987-06-19 DE DE3750492T patent/DE3750492T2/de not_active Expired - Lifetime
- 1987-06-19 EP EP87305461A patent/EP0251594B1/en not_active Expired - Lifetime
- 1987-06-25 JP JP62156716A patent/JPH083817B2/ja not_active Expired - Lifetime
Non-Patent Citations (1)
| Title |
|---|
| ＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅＡＣＭ（１９８６−１２）Ｐ．１２２９−１２３９ |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0251594A2 (en) | 1988-01-07 |
| JPS6359626A (ja) | 1988-03-15 |
| US4870568A (en) | 1989-09-26 |
| CA1282496C (en) | 1991-04-02 |
| EP0251594A3 (en) | 1991-10-09 |
| EP0251594B1 (en) | 1994-09-07 |
| DE3750492T2 (de) | 1995-03-16 |
| DE3750492D1 (de) | 1994-10-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH083817B2 (ja) | データベース検索方法 | |
| JP3726742B2 (ja) | 文書の一般テキストサマリを作成する方法およびシステム | |
| US5995962A (en) | Sort system for merging database entries | |
| US4495566A (en) | Method and means using digital data processing means for locating representations in a stored textual data base | |
| US4554631A (en) | Keyword search automatic limiting method | |
| US5551049A (en) | Thesaurus with compactly stored word groups | |
| US4290105A (en) | Method and apparatus for testing membership in a set through hash coding with allowable errors | |
| US20060106767A1 (en) | System and method for identifying query-relevant keywords in documents with latent semantic analysis | |
| EP0378848A2 (en) | Method for use of morphological information to cross reference keywords used for information retrieval | |
| JPS60134945A (ja) | データベース処理方法 | |
| US5895463A (en) | Compression of grouped data | |
| US4941124A (en) | Text comparator with counter shift register | |
| JPH0619895A (ja) | 限られたテキストソースからの項目に関する文書処理情報を記憶する方法 | |
| US6278990B1 (en) | Sort system for text retrieval | |
| US6470334B1 (en) | Document retrieval apparatus | |
| WO1983002675A1 (en) | Text comparator | |
| Burkowski | A hardware hashing scheme in the design of a multiterm string comparator | |
| US7302377B1 (en) | Accelerated event queue for logic simulation | |
| WO2005043409A1 (ja) | 表形式データの結合方法、結合装置およびプログラム | |
| US11822530B2 (en) | Augmentation to the succinct trie for multi-segment keys | |
| Lee et al. | Text retrieval machines | |
| JPH10240741A (ja) | 木構造型データの管理方法 | |
| JPS6386019A (ja) | メツセ−ジ発生装置 | |
| EP0649106B1 (en) | Compactly stored word groups | |
| JPH0752450B2 (ja) | 辞書デ−タ検索装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080117 Year of fee payment: 12 |