JPH11212980A - インデクス作成方法および検索方法 - Google Patents

インデクス作成方法および検索方法

Info

Publication number
JPH11212980A
JPH11212980A JP10026691A JP2669198A JPH11212980A JP H11212980 A JPH11212980 A JP H11212980A JP 10026691 A JP10026691 A JP 10026691A JP 2669198 A JP2669198 A JP 2669198A JP H11212980 A JPH11212980 A JP H11212980A
Authority
JP
Japan
Prior art keywords
word
index
document
value
identification number
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.)
Granted
Application number
JP10026691A
Other languages
English (en)
Other versions
JP3849279B2 (ja
Inventor
Miki Watanabe
美樹 渡辺
Hiroshi Hayata
宏 早田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujifilm Business Innovation Corp
Original Assignee
Fuji Xerox Co Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Fuji Xerox Co Ltd filed Critical Fuji Xerox Co Ltd
Priority to JP02669198A priority Critical patent/JP3849279B2/ja
Publication of JPH11212980A publication Critical patent/JPH11212980A/ja
Priority to US09/972,865 priority patent/US6678687B2/en
Application granted granted Critical
Publication of JP3849279B2 publication Critical patent/JP3849279B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

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/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/31—Indexing; Data structures therefor; Storage structures
    • G06F16/316—Indexing structures
    • G06F16/322—Trees
    • 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
    • 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/99934—Query formulation, input preparation, or translation
    • 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)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【課題】 文書に対する全文検索のためのＢ＋木インデ
クスを高速に生成し、また、当該インデクスを用いて高
速な検索を実現する。 【解決手段】 キーしての語と、当該語を含む文書との
組を登録するＢ＋木インデクスを複数のＢ＋木サブイン
デクスにより構成し、文書と語に各々を一意に識別する
文書識別番号ｉdと語識別番号ｉwを与え、文書に適用す
る関数として文書識別番号を二次元配列の横方向の位置
を示す値にマップするハッシュ関数Ｈdと、語に適用す
る関数として語識別番号を二次元配列の縦方向の位置を
示す値にマップするハッシュ関数Ｈwとを用意し、文書
における語の出現をその文書識別番号およびその語識別
番号の各々にハッシュ関数を適用して得られた値を用い
て対応するサブインデクスＢ＋木（Ｈd(ｉd)，Ｈw(ｉ
w)）に登録する。そして、当該インデクスに対して、キ
ーとして語識別番号に文書識別番号を結合した値を用い
て検索を行う。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、例えば文書に対す
る全文検索のためのインデクスを高速に生成し、また、
当該インデクスを用いて高速な検索を実現する方法に関
し、特に、当該インデクスの構成に関する。
【０００２】
【従来の技術】大量の文書に対する全文検索の方法とし
て、シグネチャ・ファイルと呼ばれるデータ構造を用い
る方法がある。 特開平７-２４４６７１号公報に示され
ている方法では、文書における文字の出現をビットで表
すインデクスを構成している。この方法では、格納され
ている文書数に影響されずに、比較的高速な検索が可能
である。しかしながら、いくつかの異なる語に対して１
つのビットを割り当てているため、指定した以外の語が
含まれている文書が検索される可能性があり、正確な検
索が行えないという問題があった。また、生成や検索の
アルゴリズムが複雑であり、既存のデータベース管理シ
ステムの上で実現することが困難であった。
【０００３】このような問題に対して、文献「Compress
ion and Fast Indexing for Multi-Gigabyte Text Data
bases」には、一般的なデータベース管理システムが提
供しているハッシュ表やＢ＋木などのインデクス手法を
用いて、高速な全文検索の機能を実現する方法が提案さ
れている。この方法では、インデクスのキーとなる語と
値となる文書に識別番号を割り付け、それらを圧縮して
格納している。これにより、検索に必要となるディスク
の読み出しページ数を減らし、高速に検索が可能とな
る。また、異なる語に異なる識別番号を割り付けられる
ため、正確な検索が可能となる。なお、この文献は、こ
の方法を用いて、約７０万件の文書に対する検索が高速
に行えることを示している。
【０００４】
【発明が解決しようとする課題】しかしながら、上記の
文献で述べられている方法では、インデクスの新規作成
や更新処理の性能が考慮されていないため、高い性能が
得られないという問題があった。特に、更新時に或る語
に対して同じ文書を重複して登録しないようにするため
の確認の処理は、文書識別番号の集まりに対する繰り返
し処理により実現しなければならないため、効率よく実
現することができない。
【０００５】また、インタネットのＷＷＷページに対す
る全文検索を行う場合などのように、対象となる文書の
数が数百万件となると、上記の文献で示したような方法
であっても、Ｂ＋木の大きさが数十ＧＢとなるため、イ
ンデクスへの追加や検索の処理を効率よく行うことがで
きない。これは、Ｂ＋木に対する１個の語と文書の組の
追加や検索処理が木の高さ＋１だけの回数のハードディ
スクに対するアクセスを必要とすること、Ｂ＋木が巨大
になるとディスクのメモリ中へのキャッシュの効果が得
られず、ハードディスクに対するほとんどすべてのアク
セスが実際にハードディスクからデータを読み込む処理
を必要とすることに起因する。
【０００６】例えば、Ｂ＋木の全体の大きさが１０ＧＢ
であり、Ｂ＋木の各ノードの大きさが８ＫＢであり、各
ノードの分岐の数が５００であるとすると、Ｂ＋木の高
さｌｏｇ500（１０ＧＢ／８ＫＢ）−１＝２．１６で、
１個の語と文書の組を追加、検索するために平均で２〜
３回のディスク・アクセスが必要となる。ハードディス
クを１回アクセスするために数十ミリ秒から数百ミリ秒
かかるため、１個の語と文書の組の追加、検索には０．
１秒から１秒の時間が必要となる。よって、１個の文書
の中に１００個の異なる語が含まれているとすると、１
個の文書を登録するために１０秒から１００秒の時間を
必要とすることになる。このようなことから、Ｂ＋木に
格納するデータの数が多くなるにつれて、Ｂ＋木の高さ
が高くなってＢ＋木が大きくなり、アクセスするページ
数が増え、結果として格納、検索に要する時間が長くな
る。例えば、図１７に格納時間の変化の傾向を示すよう
に、格納文書数の増加に応じて格納時間が大幅に増加し
てしまう。
【０００７】本発明は、上記従来の事情に鑑みなされた
もので、例えば膨大な数にのぼる文書に対する全文検索
のためのインデクスを高速に作成する方法を提供するこ
とを目的とする。また、本発明は、このように作成され
たインデクスを用いて、高速な検索を実現する方法を提
供することを目的とする。
【０００８】
【課題を解決するための手段】具体的には、本発明は、
Ｂ＋木インデクスのキーとして、語の識別番号の後ろに
文書の識別番号つなげて配置したものを用いることで、
或る文書における或る語の出現を、Ｂ＋木インデクスに
対する１回の検索で実現できるようにした。しかしなが
ら、この場合に、これを単一のＢ＋木で管理しようとす
ると、大量の文書を格納した状態では、Ｂ＋木が巨大に
なり、１つの文書を追加しようとする際に、最悪の場
合、その文書に含まれている異なる語の出現数と同じだ
けのページを更新しなければならなくなる。
【０００９】これを避けるため、Ｂ＋木インデクスを、
語の識別番号に或るハッシュ関数を適用して得られるハ
ッシュ値と、文書識別番号に別のハッシュ関数を適用し
て得られるハッシュ値とによって複数のサブインデクス
に分割し、これらサブインデクスを二次元の配列に配置
する。そして、インデクスの新規生成時や更新時には、
文書識別番号のハッシュ値が同じになるものをまとめて
登録することで、書き込みページ数を少なくし、処理効
率を高めた。また、複数の語のＡＮＤやＯＲ検索を行う
際には、語識別番号のハッシュ値が同じになるものをグ
ループにまとめ、グループごとに文書識別番号のハッシ
ュ値が同じになるＢ＋木に対する検索をまとめて処理す
ることで、ページ読み出し時のページ・キャッシュのヒ
ット率を高め、処理効率を高めた。
【００１０】すなわち、本発明では、指定されたキーか
ら値を検索するために、キー（例えば、語）と値（例え
ば、当該語を含んでいる１つの文書）とを対応させたイ
ンデクスを作成する方法において、キーと値との組を登
録するインデクスを、例えばＢ＋木構造の複数のサブイ
ンデクスにより構成し、登録する値に所定の関数を適用
して決まる値とキーに所定の関数を適用して決まる値に
よって参照される二次元配列位置にサブインデクスを格
納している。
【００１１】より具体的には、本発明では、文書と語に
各々を一意に識別する文書識別番号と語識別番号を与
え、文書に適用する関数として文書識別番号を二次元配
列の一の方向の位置を示す値にマップするハッシュ関数
と、語に適用する関数として語識別番号を二次元配列の
他の方向の位置を示す値にマップするハッシュ関数とを
用意し、文書における語の出現をその文書識別番号およ
びその語識別番号の各々にハッシュ関数を適用して得ら
れた値を用いて対応するサブインデクスに登録する。ま
た、本発明では、語に一意に識別する語識別番号を与
え、語の出現に適用する関数としてその語の文書におけ
る出現回数或いは出現頻度を二次元配列の一の方向の位
置を示す値にマップするハッシュ関数と、語に適用する
関数として語識別番号を二次元配列の他の方向の位置を
示す値にマップするハッシュ関数を用意し、或る文書に
おける或る語の出現をその語の出現回数およびその語識
別番号の各々にハッシュ関数を適用して得られた値を用
いて対応するサブインデクスに登録する。
【００１２】また、上記の登録に際して、複数の文書に
おける語の出現を一括して登録する場合には、それらの
文書の文書識別番号（或いは、各語の出現回数または出
現頻度）にハッシュ関数を適用して決まる値が同じにな
るものを１つのグループにまとめて、グループごとに語
の出現を登録する。さらには、上記の登録に際して、１
つのグループにまとめられた文書におけるすべての語の
出現を登録する場合には、各語の出現を語にハッシュ関
数を適用して決まる値が同じになるものを一つのグルー
プにまとめて、グループごとに語の出現を登録する。な
お、上記の登録に際しては、主記憶装置に用意した少な
くとも１つのサブインデクスが格納できるページキャッ
シュを用いる。
【００１３】また、本発明は、文書名と当該文書に含ま
れる語とを対応させたインデクスをもちいて、語をキー
として対応する文書名を得る検索方法において、文書名
および語に各々を一意に識別する文書識別番号と語識別
番号を与え、キーとして語識別番号に文書識別番号を結
合した値を用いる。より具体的には、文書名と当該文書
に含まれる語とを対応させたインデクスを複数のサブイ
ンデクスにより構成し、文書名と語に各々を一意に識別
する文書識別番号と語識別番号を与えて、文書識別番号
と語識別番号とにハッシュ関数を適用して決まる値によ
って参照される二次元配列位置のサブインデクスに登録
したインデクスをもちいて、語をキーとして対応する文
書名を得る検索方法において、複数の語による検索を行
う場合に、各語の識別番号にハッシュ関数を適用して決
まる値が同じになるものを１つのグループにまとめて、
グループごとにサブインデクスに対する検索を実行す
る。
【００１４】また、文書名と当該文書に含まれる語とを
対応させたインデクスを複数のサブインデクスにより構
成し、文書名と語に各々を一意に識別する文書識別番号
と語識別番号を与えて、文書識別番号と語識別番号とに
ハッシュ関数を適用して決まる値によって参照される二
次元配列位置のサブインデクスに登録したインデクスを
もちいて、語をキーとして対応する文書名を得る検索方
法において、複数の語のＡＮＤまたはＯＲ条件による検
索を行う場合に、文書識別番号にハッシュ関数を適用し
て決まる値が同じになる文書に対するサブインデクスに
対して各語の出現を検索し、その検索結果についてＡＮ
ＤまたはＯＲの演算を実施する。
【００１５】
【発明の実施の形態】本発明の実施形態を図面を参照し
て説明する。図１には、本発明に係る方法を実行する装
置の構成例を示してある。なお、この装置はコンピュー
タハードウエア資源を用いて、本発明を実施するための
プログラムを実行することにより構成されている。
【００１６】文書蓄積部１はハードディスク装置等の外
部メモリにより構成されており、文書蓄積部１には登録
や検索の対象となる文書がその文書名とともに格納され
る。文書ソート部２は、インデクスの登録の対象となる
文書の文書名を、あらかじめ定義されたハッシュ関数を
文書識別番号に適用して得られる値が同じになるものが
まとまるようにソートする。形態素解析部３は、指定さ
れた文書の全文を解析し、語の切り出しを行う。インデ
クス登録部４は、与えられた文書名および語の識別番号
を得て、インデクス選択部５の機能により選択されたＢ
＋木構造に、語識別番号と文書識別番号をキーとして語
の出現を登録する。
【００１７】インデクス蓄積部６は、ハードディスク装
置等の外部メモリにより構成されており、インデクス蓄
積部６はあらかじめ定められた大きさの二次元の配列
（ここではＤ×Ｗ、ただし、Ｄ，Ｗは１以上の整数）上
にＢ＋木を記憶する。また、インデクス蓄積部６は文書
名と文書識別番号、語と語識別番号の対応関係も記憶し
ている。インデクス選択部５は、与えられた文書識別番
号と語識別番号に、それぞれあらかじめ定められたハッ
シュ関数を適用し、その結果得られた値を用いてインデ
クス蓄積部６に格納されているインデクス表から語の出
現を登録するＢ＋木の識別番号を選択する。
【００１８】ここで、文書ソート部２、インデクス選択
部５で用いられる文書識別番号に適用されるハッシュ関
数および語識別番号に適用されるハッシュ関数Ｈは、文
書識別番号をｉd、語識別番号をｉwとしたとき、それぞ
れ、０≦Ｈd（ｉd）＜Ｄ、０≦Ｈw（ｉw）＜Ｗ、となる
整数を値とするように定義される。
【００１９】問い合わせ入力部７は、利用者からの検索
要求を受け付け、語をＡＮＤまたはＯＲで結合した検索
式を生成する。検索実行部８は、与えられた検索式に含
まれている語の識別番号から、インデクス選択部５の機
能により検索の対象となるＢ＋木を得て検索処理を行
う。結果出力部９は、検索実行部８により得られた検索
結果をディスプレイ表示等して利用者に提示する。
【００２０】図２には、インデクス蓄積部６に格納され
ているＢ＋木のキーの構成例を示してある。このＢ＋木
のキーは、語識別番号の後ろに文書識別番号を結合した
構造となっており、本例では、語識別番号として４バイ
ト、文書識別番号として４バイトの領域を割り当ててい
る。これにより、或る語を含む文書を得る検索において
は、その語の出現を含むすべてのＢ＋木について、その
語の語識別番号の後ろに文書識別番号として最小のもの
（ここでは０）を結合した値と、文書識別番号として最
大のもの（ここではＦＦＦＦＦＦＦＦ（１６進））を結
合した値の範囲で検索を行うことで、その語に対するす
べての出現を、文書識別番号の昇順に得ることができ
る。
【００２１】すなわち、この処理ではその手順を図３に
示すように、図２のキーに対して、３２ビット左へシフ
トさせた値をｓｔａｒｔ点とし（ステップＳ１）、３２
ビット左へシフトさせて０×ＦＦＦＦＦＦＦＦを加えた
値をｅｎｄ点として（ステップＳ２）、ｓｔａｒｔ点か
らｅｎｄ点までの範囲で検索を行う（ステップＳ３）。
なお、図３において、＜＜はビットを左にシフトする演
算を示している。また、或る文書における或る語の出現
を検索したいときには、その語の識別番号とその文書の
識別番号を結合した値をキーとして、完全に一致するも
のを検索することで、該当する語の出現を得ることがで
きる。
【００２２】例えば、いくつかの文書に関する語の出現
を登録した時点で、Ｂ＋木の一部の状態が図４に示され
ているようになっていたとする。この状態において、語
識別番号が４５（１６進）であるような語を含む文書を
検索する場合には、キーの値が４５００００００００
（１６進）と４５ＦＦＦＦＦＦＦＦ（１６進）の範囲に
あるものを検索することで目的とする語の出現（Ｏ4と
Ｏ5）を得られる。また、語識別番号が４５（１６進）
であるような語が文書識別番号が７であるような文書に
含まれているか否かを確認する場合には、４５００００
０００７（１６進）をキーとして、キーの値が一致する
ものを検索することで、語の出現（Ｏ5）を得ることが
できる。
【００２３】図５には、インデクス蓄積部６におけるＢ
＋木の格納構造を示してある。このＢ＋木は、Ｄ×Ｗの
二次元配列にＤ×Ｗ個のサブインデクスを格納した構造
となっており、文書識別番号がｉdで且つ語識別番号が
Ｉwである或る語の出現は、Ｂ＋木（Ｈw(ｉw)，Ｈd(ｉ
d)）のサブインデクスに対応してＢ＋木に登録されてい
る。よって、語識別番号がｉwである語の出現を検索す
る場合には、図６に示されている手順で選択されたＢ＋
木について図３に示されている処理を実行する。
【００２４】図６には、指定された或る一つの語が出現
する文書を検索する処理手順を示してある。まず、この
処理では、与えられた語の語識別番号Ｉwをｉwに代入
し、その値を引数としてハッシュ関数Ｈwを適用して得
られる値をｗに代入している（ステップＳ１０）。そし
て、変数ｉおよびｒを０に初期化し（ステップＳ１
１）、ｉを１つずつ増加させながら（ステップＳ１
４）、ｉがＤとなるまで（ステップＳ１５）、Ｂ＋木
（ｗ，ｉ）に対して語の検索を繰り返し行い（ステップ
Ｓ１２）、その結果を配列Ｒに追加している（ステップ
Ｓ１３）。
【００２５】これにより、図５に示した二次元配列の或
る一つの行に記憶されているＢ＋木の各サブインデクス
に対する検索が行える。このようにすることにより、目
的とする語の出現はそれ以外のＢ＋木には含まれていな
いので、これにより見つかった文書のみに目的とする語
が含まれていることになる。このような処理により、検
索の対象となるＢ＋木が限定されかつ各Ｂ＋木を順序良
く利用するため、検索対象のサブインデクスを保持する
キャッシュのヒット率を高めることができ、効率よく検
索が実行できる。なお、検索において、検索実行部８が
使用する主記憶装置のキャッシュに、少なくとも１つの
Ｂ＋木サブインデクスが保持されるようになっている。
【００２６】図７には、複数の語のＡＮＤまたはＯＲ条
件で検索を行う処理手順を示してある。この処理は、複
数の語とＡＮＤまたはＯＲの演算が与えられて呼び出さ
れ、まず、与えられた語の識別番号にハッシュ関数Ｈw
（ｉw）を適用して得られる値の順にソートし、その結
果を配列Ｘに格納している（ステップＳ２０）。これに
より、以下の検索において同じＢ＋木サブインデクスに
対する検索が連続して実行されるようになり、サブイン
デクスを保持するキャッシュのヒット率を高めることが
できる。
【００２７】次に、図５に示した二次元配列の列を指定
する変数ｄと確定した検索結果の数を示す変数Ｉの値を
０に初期化し（ステップＳ２１）、Ｂ＋木（０，ｄ）に
対して語識別番号Ｘ［０］の語の出現を検索する（ステ
ップＳ２２）。この検索の処理は図３に示して手順で実
施され、検索結果の数は変数ｒに代入され、検索結果は
配列Ｒ［０．．．ｒ］に代入される（ステップＳ２
３）。続いて、変数ｗの値を１に初期化し（ステップＳ
２４）、ｗを１つずつ増加させながら次のような処理を
繰り返し行う。すなわち、二次元配列の縦方向にサブイ
ンデクスＢ＋木（Ｈw(X[0])，ｄ）を選択して、検索を
実行しながらＡＮＤ，ＯＲの演算を実行する。
【００２８】この処理は次の手順で実行され、サブイン
デクスＢ＋木（Ｈw(X[0])，ｄ）に対してＸ[w]の語の出
現を図３の処理により検索し（ステップＳ２５）、その
結果の数と結果を変数ｒ’とＲ’［０．．．ｒ’］に代
入する（ステップＳ２６）。続いて、ＡＮＤかＯＲかの
演算を判断し（ステップＳ２７）、判断結果に従ってＲ
［Ｉ．．．Ｉ＋ｒ］とＲ’［０．．．ｒ’］に対してＡ
ＮＤまたはＯＲの演算を実施する（ステップＳ２８、Ｓ
２９）。なお、ＡＮＤとＯＲの演算処理は、それぞれ図
８、図９に基づいて後述する手順により実行される。
【００２９】ＡＮＤ演算を行った場合には（ステップＳ
２８）、演算の結果がｒ＝Ｉ（すなわち、演算の結果該
当する語の出現がなかった）場合には（ステップＳ３
０）、ｄを１つ増加させ（ステップＳ３１）、ｄがＤよ
り小さい（すなわち、二次元配列の列がまだ残ってい
る）場合には（ステップＳ３２）、次の列のＢ＋木サブ
インデクスの検索に進む（ステップＳ２４）。一方、ｒ
＝Ｉでない場合には（ステップＳ３０）、ｗを１つだけ
増加させ（ステップＳ３３）、次の語があることを確認
して（ステップＳ３４）、次の語による検索演算に進む
（ステップＳ２５）。また、ＯＲ演算を行った場合には
（ステップＳ２９）、演算の終了後にｗを１つだけ増加
させ（ステップＳ３３）、次の語があることを確認して
（ステップＳ３４）、次の語による検索演算に進む（ス
テップＳ２５）。
【００３０】図８には、上記のＡＮＤ演算の処理（ステ
ップＳ２８）の手順を示してある。この処理では、配列
Ｒ［ｌ．．．ｌ＋ｒ］に含まれている語の出現で配列
Ｒ’［０．．．ｒ’］に同じ文書の語の出現が含まれて
いるもののみを配列Ｒに残す演算を行う。両方に含まれ
ているか否かの確認は、ｉを０からｒまで、ｉ’を０か
らｒ’まで増加させながら（ステップＳ４１、Ｓ４６〜
Ｓ４８）、文書識別番号Ｒ［ｉ］．ｉｄと文書識別番号
Ｒ’［ｉ’］．ｉｄを比較することで行う（ステップＳ
４２）。
【００３１】そして、Ｒ［ｉ］．ｉｄ＜Ｒ’［ｉ’］．
ｉｄの場合には、配列Ｒ’にはＲ［ｉ］．ｉｄと同じ文
書識別番号の文書に対する語の出現は含まれていないの
で、Ｒ［ｉ］を配列Ｒから削除する（ステップＳ４
３）。また、Ｒ［ｉ］．ｉｄ＝Ｒ’［ｉ’］．ｉｄの場
合には、配列Ｒ’［ｉ’］はＲ［ｉ］と同じ文書に対す
る語の出現であるので、Ｒ［ｉ］を配列Ｒに残し、ｉと
ｉ’とをそれぞれ１つずつ増加させて次の語の出現の処
理に進む（ステップＳ４４）。また、Ｒ［ｉ］．ｉｄ＞
Ｒ’［ｉ’］．ｉｄの場合には、Ｒ［ｉ］と同じ文書に
対する語の出現がＲ’［ｉ’＋１．．．ｒ’］に含まれ
ている可能性があるので、ｉ’を１つだけ増加させて再
び比較の処理に戻る（ステップＳ４５）。
【００３２】以上の処理は、ｉが配列Ｒの最後まで進む
かｉ’が配列Ｒ’の最後に進むまで繰り返され、最後に
ｒにｉの値を代入することで（ステップＳ４９）、配列
Ｒの後方にあって、Ｒ’［ｒ’−１］の語の出現に対す
る文書の文書識別番号よりも大きい文書識別番号の文書
に対する語の出現をすべて削除して終了する。なお、検
索結果が０の場合には（ステップＳ４０、Ｓ５０）、そ
のまま処理を終了する。
【００３３】図９には、上記のＯＲ演算の処理（ステッ
プＳ２９）の手順を示してある。この処理では、配列
Ｒ’［０．．．ｒ’］に含まれている語の出現で配列Ｒ
［ｌ．．．ｌ＋ｒ］に同じ文書の語の出現が含まれてい
ないものを配列Ｒに追加することを行う。この判断は、
ｉを０からｒまで、ｉ’を０からｒ’まで増加させなが
ら（ステップＳ６０、Ｓ６３〜Ｓ６７）、文書識別番号
Ｒ［ｉ］．ｉｄと文書識別番号Ｒ’［ｉ’］．ｉｄを比
較することで行う（ステップＳ６２）。
【００３４】そして、Ｒ［ｉ］．ｉｄ＜Ｒ’［ｉ’］．
ｉｄの場合には、配列Ｒ’にはＲ［ｉ］．ｉｄと同じ文
書識別番号の文書に対する語の出現が含まれていないの
で、ｉを１つだけ増加させて次の比較の処理に進む（ス
テップＳ６３）。また、Ｒ［ｉ］．ｉｄ＝Ｒ’
［ｉ’］．ｉｄの場合には、これらの語の出現は同じ文
書に対するものであるので、ｉとｉ’とを共に１つだけ
増加させて比較の処理に戻る（ステップＳ６４）。ま
た、Ｒ［ｉ］．ｉｄ＞Ｒ’［ｉ’］．ｉｄの場合には、
配列Ｒ［ｌ．．．ｌ＋ｒ］にはＲ’［ｉ’］．ｉｄと同
じ文書識別番号の文書に対する語の出現は含まれていな
いので、語の出現Ｒ’［ｉ’］をＲ［ｉ］の直後に挿入
し（ステップＳ６５）、ｉを２、ｉ’を１だけ増加させ
て次の比較の処理に進む（ステップＳ６６）。なお、上
記の比較の処理に先立って、ｉ＝ｒの確認を行い（ステ
ップＳ６１）、それが真ならばＲ［ｌ．．．ｌ＋ｒ］の
すべての要素に対する処理が終了したことになるので、
配列Ｒ’で未処理の語の出現をすべて配列Ｒの最後尾に
追加して処理を終了する（ステップＳ６８）。
【００３５】図１０には、複数の文書の語の出現を一括
して登録する処理の手順を示してある。この処理では、
まず、各文書を文書識別番号にハッシュ関数Ｈdを適用
して得られる値によりグループ分けし、グループ分けさ
れた文書をグループごとに配列Ｇに格納する（ステップ
Ｓ７０）。続いて、変数ｇを初期化し（ステップＳ７
１）、配列Ｇに格納されている各グループについて、そ
れに属しているすべての文書から語の出現（文書と語の
組）を取り出し（ステップＳ７２）、それらを語の識別
番号にハッシュ関数Ｈwを適用して得られる値によりグ
ループ分けして、グループ分けされた語の出現をグルー
プごとに配列Ｏに格納する（ステップＳ７３）。そし
て、変数ｗを１つずつ増加させながら（ステップＳ７
４、Ｓ７６、Ｓ７７）、配列Ｇに格納されている各グル
ープについてそれに属している語の出現を登録する処理
（図１１により後述する）を実施し（ステップＳ７
５）、さらに、変数ｄを１つずつ増加させながら（ステ
ップＳ７８、Ｓ７９）、上記の処理を繰り返し行う。
【００３６】上記の処理により、語の出現は図５に示さ
れた配列の左上から下方向に並んだＢ＋木サブインデク
スに順に格納され、一番下のＢ＋木サブインデクスまで
格納が終わると、一つ右の列について上から下方向に並
んだＢ＋木サブインデクスに順に格納されるため、複数
のＢ＋木サブインデクスを交互に参照することがなくな
り、ページ・キャッシュのヒット率を高めることができ
る。さらに、主記憶上に一つのＢ＋木サブインデクスの
内容を保持できるだけの領域があれば、格納処理をすべ
て主記憶中で実行できるため、きわめて高速に格納処理
を実行できる。
【００３７】図１１には、或る文書における或る語の出
現を登録する処理の手順を示してある。この処理では、
語および文書に対してそれらの識別番号ｉw、ｉdを得
て、それぞれにハッシュ関数Ｈw（ｉw）、Ｈd（ｉd）を
適用して得られる値を変数ｗ、ｄに保持する（ステップ
Ｓ８０、Ｓ８１）。そして、ｉwの値を左に３２ビット
シフトした値にｉdの値を足したものを変数ｋに代入し
（ステップＳ８２）、図５に示された配列のサブインデ
クスＢ＋木（ｗ，ｄ）にｋをキーとして語の出現を登録
する（ステップＳ８３）。
【００３８】以上のように構成されたイデクスを用い、
配列の分割数としてＤ＝６４、Ｗ＝６４を用いると、従
来の一つのＢ＋木によるインデクスに比べて、木の深さ
を２／３程度に縮小できる。これにより、文書の格納時
の性能を、例えば、従来の図１７に示した状況から、図
１６に実線で示されているように改善することができ
る。ここで、図１６で破線で示されているのは図１７で
示されている従来技術による格納時間の推移である。な
おまた、格納性能ばかりではなく、検索時の性能も約
１．５倍に改善できる。
【００３９】図１２には、本発明の第２実施例として、
Ｂ＋木インデクスの縦方向の分割に、語の出現回数に或
る関数を適用した値を用いる場合のキーの構成を示して
ある。 本実施例のキーは、語識別番号の後ろに出現回
数を整数であらわした値を結合した構造であり、語識別
番号として４バイト、出現回数として４バイトの領域を
割り当てている。
【００４０】図１３には、図１２に示されたキーの構成
を用いて、語の出現をＢ＋木に登録した状態を示してあ
る。図に示されているように、同じ語に対する複数の異
なる語の出現が、語の出現回数の多い順にならべられ
る。これにより、検索処理において、検索の結果を語の
出現回数の多い順に取り出すことが容易となる。
【００４１】なお、第２実施例における語の出現を検索
する処理手順は、図６に示した第１実施例における語の
出現を検索する処理と同じである。また、語の出現を登
録する処理手順は、図１０に示した処理手順において文
書識別番号を用いて文書をグループ分けしている処理
（ステップＳ７０）を語の出現回数を用いて語の出現を
グループ分けする処理に置き換え、また、図１１に示し
た処理手順において文書識別番号の値を用いてキーとな
る値を生成している処理（ステップＳ８１、Ｓ８２）を
語の出現回数の値を用いてキーとなる値を生成する処理
に置き換えることで実現できる。
【００４２】図１４には、本発明の第３実施例として、
Ｂ＋木の縦方向の分割に語の出現頻度に或る関数を適用
した値を用いる場合のキーの構成を示してある。本実施
例のキーは、語識別番号の後ろに出現頻度を整数であら
わした値を結合した構造であり、語識別番号として４バ
イト、出現頻度として１バイトの領域を割り当ててい
る。なお、或る語の出現の出現頻度は、その語がその文
書に現れた回数をその文書の総語数で割って１００を掛
けた値であらわす。
【００４３】図１５には、図１４に示されたキーの構成
を用いて、語の出現をＢ＋木に登録した状態を示してあ
る。図に示されているように、同じ語に対する複数の異
なる語の出現が語の出現頻度の高い順にならべられる。
これにより、検索処理において、検索の結果を語の出現
頻度の高い順に取り出すことが容易となる。
【００４４】なお、第３実施例における語の出現を検索
する処理手順は、図６に示した第１実施例における語の
出現を検索する処理と同じである。また、語の出現を登
録する処理手順は、図１０に示した処理手順において文
書識別番号を用いて文書をグループ分けしている処理
（ステップＳ７０）を語の出現頻度を用いて語の出現を
グループ分けする処理に置き換え、また、図１１に示し
た処理手順において文書識別番号の値を用いてキーとな
る値を生成している処理（ステップＳ８１、Ｓ８２）を
語の出現頻度の値を用いてキーとなる値を生成する処理
に置き換えることで実現できる。
【００４５】
【発明の効果】以上説明したように、本発明によれば、
キーと値との組を登録するインデクスを複数のサブイン
デクスにより構成し、登録する値にハッシュ関数等の所
定の関数を適用して決まる値とキーにハッシュ関数等の
所定の関数を適用して決まる値によって参照される二次
元配列位置にサブインデクスを格納するようにし、ま
た、検索においては、キーとして、語の識別番号の後ろ
に文書の識別番号あるいは後の出現回数や出現頻度をつ
なげて配置したものを用いるようにしたため、大量の文
書に対しても、文書の格納処理や検索処理に必要となる
更新ページ数や読み出しページ数を削減でき、高速に処
理を実行できる。
【図面の簡単な説明】
【図１】 本発明の一実施形態に係る装置構成を示す図
である。
【図２】 第１実施例に係るキーの構成を示す図であ
る。
【図３】 語の出現を検索する処理の手順を示すフロー
チャートである。
【図４】 Ｂ＋木の内容の一部を例示する図である。
【図５】 Ｂ＋木のインデクス配列の構成を示す図であ
る。
【図６】 語の出現を検索する処理の手順を示すフロー
チャートである。
【図７】 複数の語による検索の処理手順を示すフロー
チャートである。
【図８】 ＡＮＤ演算の処理手順を示すフローチャート
である。
【図９】 ＯＲ演算の処理手順を示すフローチャートで
ある。
【図１０】 複数の文書を一括して登録する処理手順を
示すフローチャートである。
【図１１】 或る１つの語の出現を登録する処理手順を
示すフローチャートである。
【図１２】 第２実施例に係るキーの構成を示す図であ
る。
【図１３】 第２実施例におけるＢ＋木の内容の一部を
例示する図である。
【図１４】 第３実施例に係るキーの構成を示す図であ
る。
【図１５】 第３実施例におけるＢ＋木の内容の一部を
例示する図である。
【図１６】 本発明の第１実施例を用いた場合の登録文
書数に対する新規文書登録に要する時間の推移を示した
グラフである。
【図１７】 従来技術を用いた場合の登録文書数に対す
る新規文書登録に要する時間の推移を示したグラフであ
る。
【符号の説明】
１・・・文書蓄積部、 ２・・・文書ソート部、 ４・
・・インデクス登録部、５・・・インデクス選択部、
６・・・インデクス蓄積部、８・・・検索実行部、

Claims (16)

    【特許請求の範囲】
  1. 【請求項１】 指定されたキーから値を検索するため
    に、キーと値とを対応させたインデクスを作成する方法
    において、 キーと値との組を登録するインデクスを複数のサブイン
    デクスにより構成し、 登録する値に所定の関数を適用して決まる値とキーに所
    定の関数を適用して決まる値によって参照される二次元
    配列位置にサブインデクスを格納することを特徴とする
    インデクス作成方法。
  2. 【請求項２】 請求項１に記載のインデクス作成方法に
    おいて、 サブインデクスとしてＢ＋木構造を用いることを特徴と
    するインデクス作成方法。
  3. 【請求項３】 請求項１または請求項２に記載のインデ
    クス作成方法において、 キーとして語を用い、値として当該語を含んでいる１つ
    の文書を用いることを特徴とするインデクス作成方法。
  4. 【請求項４】 請求項３に記載のインデクス作成方法に
    おいて、 文書と語に各々を一意に識別する文書識別番号と語識別
    番号を与え、 文書に適用する関数として文書識別番号を二次元配列の
    一の方向の位置を示す値にマップするハッシュ関数と、
    語に適用する関数として語識別番号を二次元配列の他の
    方向の位置を示す値にマップするハッシュ関数とを用意
    し、 文書における語の出現をその文書識別番号およびその語
    識別番号の各々にハッシュ関数を適用して得られた値を
    用いて対応するサブインデクスに登録することを特徴と
    するインデクス作成方法。
  5. 【請求項５】 請求項４に記載のインデクス作成方法に
    おいて、 複数の文書における語の出現を一括して登録する場合
    に、それらの文書の文書識別番号にハッシュ関数を適用
    して決まる値が同じになるものを１つのグループにまと
    めて、グループごとに語の出現を登録することを特徴と
    するインデクス作成方法。
  6. 【請求項６】 請求項３に記載のインデクス作成方法に
    おいて、 語に一意に識別する語識別番号を与え、 語の出現に適用する関数としてその語の文書における出
    現回数を二次元配列の一の方向の位置を示す値にマップ
    するハッシュ関数と、 語に適用する関数として語識別番号を二次元配列の他の
    方向の位置を示す値にマップするハッシュ関数を用意
    し、 或る文書における或る語の出現をその語の出現回数およ
    びその語識別番号の各々にハッシュ関数を適用して得ら
    れた値を用いて対応するサブインデクスに登録すること
    を特徴とするインデクス作成方法。
  7. 【請求項７】 請求項６に記載のインデクス作成方法に
    おいて、 複数の文書における語の出現を一括して登録する場合
    に、各語の出現回数にハッシュ関数を適用して決まる値
    が同じになるものを１つのグループにまとめて、グルー
    プごとに語の出現を登録することを特徴とするインデク
    ス作成方法。
  8. 【請求項８】 請求項３に記載のインデクス作成方法に
    おいて、 語に一意に識別する語識別番号を与え、 語の出現に適用する関数としてその語の文書における出
    現頻度を二次元配列の一の方向の位置を示す値にマップ
    するハッシュ関数と、 語に適用する関数として語識別番号を二次元配列の他の
    方向の位置を示す値にマップするハッシュ関数を用意
    し、 或る文書における或る語の出現をその語の出現頻度およ
    びその語識別番号の各々にハッシュ関数を適用して得ら
    れた値を用いて対応するサブインデクスに登録すること
    を特徴とするインデクス作成方法。
  9. 【請求項９】 請求項８に記載のインデクス作成方法に
    おいて、 複数の文書における語の出現を一括して登録する場合
    に、各語の出現頻度にハッシュ関数を適用して決まる値
    が同じになるものを１つのグループにまとめて、グルー
    プごとに語の出現を登録することを特徴とするインデク
    ス作成方法。
  10. 【請求項１０】 請求項５または請求項７または請求項
    ９に記載のインデクス作成方法において、 １つのグループにまとめられた文書におけるすべての語
    の出現を登録する場合に、各語の出現を語にハッシュ関
    数を適用して決まる値が同じになるものを一つのグルー
    プにまとめて、グループごとに語の出現を登録すること
    を特徴とするインデクス作成方法。
  11. 【請求項１１】 請求項１０に記載のインデクス作成方
    法において、 主記憶装置に用意した少なくとも１つのサブインデクス
    が格納できるページキャッシュを用いることを特徴とす
    るインデクス作成方法。
  12. 【請求項１２】 文書名と当該文書に含まれる語とを対
    応させたインデクスをもちいて、語をキーとして対応す
    る文書名を得る検索方法において、 文書名および語に各々を一意に識別する文書識別番号と
    語識別番号を与え、 キーとして語識別番号に文書識別番号を結合した値を用
    いることを特徴としたインデクス検索方法。
  13. 【請求項１３】 文書名と当該文書に含まれる語とを対
    応させたインデクスを複数のサブインデクスにより構成
    し、文書名と語に各々を一意に識別する文書識別番号と
    語識別番号を与えて、文書識別番号と語識別番号とにハ
    ッシュ関数を適用して決まる値によって参照される二次
    元配列位置のサブインデクスに登録したインデクスをも
    ちいて、語をキーとして対応する文書名を得る検索方法
    において、 複数の語による検索を行う場合に、各語の識別番号にハ
    ッシュ関数を適用して決まる値が同じになるものを１つ
    のグループにまとめて、グループごとにサブインデクス
    に対する検索を実行することを特徴とするインデクス検
    索方法。
  14. 【請求項１４】 文書名と当該文書に含まれる語とを対
    応させたインデクスを複数のサブインデクスにより構成
    し、文書名と語に各々を一意に識別する文書識別番号と
    語識別番号を与えて、文書識別番号と語識別番号とにハ
    ッシュ関数を適用して決まる値によって参照される二次
    元配列位置のサブインデクスに登録したインデクスをも
    ちいて、語をキーとして対応する文書名を得る検索方法
    において、 複数の語のＡＮＤまたはＯＲ条件による検索を行う場合
    に、文書識別番号にハッシュ関数を適用して決まる値が
    同じになる文書に対するサブインデクスに対して各語の
    出現を検索し、その検索結果についてＡＮＤまたはＯＲ
    の演算を実施することを特徴とするインデクス検索方
    法。
  15. 【請求項１５】 指定されたキーから値を検索するため
    に、キーと値とを対応させたインデクスを作成する装置
    において、 複数のサブインデクスから構成したインデクスを記憶す
    るインデクス記憶手段と、 登録する値に所定の関数を適用することにより第１の値
    を算出する第１の関数適用手段と、 キーに所定の関数を適用することにより第２の値を算出
    する第２の関数適用手段と、 算出された前記第１の値と前記第２の値に応じて定まる
    二次元配列の位置にある前記インデクス記憶手段内のサ
    ブインデクスに前記キーと前記登録する値との組を格納
    する格納手段と、を備えたことを特徴とするインデクス
    作成装置。
  16. 【請求項１６】 指定されたキーから値を検索するため
    にキーと値とを対応させたインデクスの作成処理を、コ
    ンピュータに実行させるプログラムを当該コンピュータ
    に読み取り可能に記憶した記憶媒体において、 前記プログラムは、キーと値との組を登録するインデク
    スを複数のサブインデクスにより構成して、登録する値
    に所定の関数を適用して決まる値とキーに所定の関数を
    適用して決まる値によって参照される二次元配列位置に
    サブインデクスを格納する処理を、前記コンピュータに
    実行させることを特徴とする記憶媒体。
JP02669198A 1998-01-23 1998-01-23 インデクス作成方法および検索方法 Expired - Fee Related JP3849279B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP02669198A JP3849279B2 (ja) 1998-01-23 1998-01-23 インデクス作成方法および検索方法
US09/972,865 US6678687B2 (en) 1998-01-23 2001-10-10 Method for creating an index and method for searching an index

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP02669198A JP3849279B2 (ja) 1998-01-23 1998-01-23 インデクス作成方法および検索方法

Publications (2)

Publication Number Publication Date
JPH11212980A true JPH11212980A (ja) 1999-08-06
JP3849279B2 JP3849279B2 (ja) 2006-11-22

Family

ID=12200428

Family Applications (1)

Application Number Title Priority Date Filing Date
JP02669198A Expired - Fee Related JP3849279B2 (ja) 1998-01-23 1998-01-23 インデクス作成方法および検索方法

Country Status (2)

Country Link
US (1) US6678687B2 (ja)
JP (1) JP3849279B2 (ja)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20040103495A (ko) * 2003-05-30 2004-12-08 마이크로소프트 코포레이션 ｂ-트리를 사용한 위치 액세스
JP2007094838A (ja) * 2005-09-29 2007-04-12 Oki Electric Ind Co Ltd 文書処理装置および文書処理方法
KR100886189B1 (ko) * 2000-11-30 2009-02-27 코퍼아이 리미티드 데이터 베이스
KR100955189B1 (ko) 2008-08-11 2010-04-29 엔에이치엔(주) 문서 검색을 위한 서명 데이터 집합 생성 방법 및 시스템
US7970769B2 (en) 2006-11-23 2011-06-28 Samsung Electronics Co., Ltd. Apparatus and method for optimized index search
JP2011258115A (ja) * 2010-06-11 2011-12-22 Nippon Telegr & Teleph Corp <Ntt> 情報格納検索装置、情報格納方法、および情報格納プログラム
WO2014141802A1 (ja) * 2013-03-12 2014-09-18 ソニー株式会社 情報処理装置、情報処理システム、および情報処理方法、並びにプログラム
KR20190013907A (ko) 2016-06-09 2019-02-11 가부시키가이샤 사이게임스 정보 처리 시스템 및 방법, 및 프로그램

Families Citing this family (73)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8352400B2 (en) 1991-12-23 2013-01-08 Hoffberg Steven M Adaptive pattern recognition based controller apparatus and method and human-factored interface therefore
US7966078B2 (en) 1999-02-01 2011-06-21 Steven Hoffberg Network media appliance system and method
US6859808B1 (en) * 2001-05-31 2005-02-22 Oracle International Corporation Mapping logical row identifiers for primary B+tree-like structures to physical row identifiers
JP4215425B2 (ja) * 2001-11-21 2009-01-28 日本電気株式会社 文章管理システム、その管理方法及びそのプログラム
US7287023B2 (en) * 2003-11-26 2007-10-23 International Business Machines Corporation Index structure for supporting structural XML queries
US7707039B2 (en) * 2004-02-15 2010-04-27 Exbiblio B.V. Automatic modification of web pages
US8442331B2 (en) 2004-02-15 2013-05-14 Google Inc. Capturing text from rendered documents using supplemental information
US8037102B2 (en) 2004-02-09 2011-10-11 Robert T. and Virginia T. Jenkins Manipulating sets of hierarchical data
US8799303B2 (en) 2004-02-15 2014-08-05 Google Inc. Establishing an interactive environment for rendered documents
US20060041484A1 (en) 2004-04-01 2006-02-23 King Martin T Methods and systems for initiating application processes by data capture from rendered documents
US10635723B2 (en) 2004-02-15 2020-04-28 Google Llc Search engines and systems with handheld document data capture devices
US7812860B2 (en) 2004-04-01 2010-10-12 Exbiblio B.V. Handheld device for capturing text from both a document printed on paper and a document displayed on a dynamic display device
US8527498B1 (en) * 2004-02-20 2013-09-03 Teradata Us, Inc. Method and system for organizing values of alternative equality conditions
US20060081714A1 (en) 2004-08-23 2006-04-20 King Martin T Portable scanning device
US9008447B2 (en) 2004-04-01 2015-04-14 Google Inc. Method and system for character recognition
US20080313172A1 (en) 2004-12-03 2008-12-18 King Martin T Determining actions involving captured information and electronic content associated with rendered documents
US8621349B2 (en) * 2004-04-01 2013-12-31 Google Inc. Publishing techniques for adding value to a rendered document
US20070300142A1 (en) 2005-04-01 2007-12-27 King Martin T Contextual dynamic advertising based upon captured rendered text
US20060098900A1 (en) * 2004-09-27 2006-05-11 King Martin T Secure data gathering from rendered documents
US8793162B2 (en) 2004-04-01 2014-07-29 Google Inc. Adding information or functionality to a rendered document via association with an electronic counterpart
USRE50599E1 (en) 2004-04-01 2025-09-23 Kyocera Corporation Search engines and systems with handheld document data capture devices
US9116890B2 (en) 2004-04-01 2015-08-25 Google Inc. Triggering actions in response to optically or acoustically capturing keywords from a rendered document
US9143638B2 (en) 2004-04-01 2015-09-22 Google Inc. Data capture from rendered documents using handheld device
US8146156B2 (en) 2004-04-01 2012-03-27 Google Inc. Archive of text captures from rendered documents
US7990556B2 (en) 2004-12-03 2011-08-02 Google Inc. Association of a portable scanner with input/output and storage devices
US7894670B2 (en) 2004-04-01 2011-02-22 Exbiblio B.V. Triggering actions in response to optically or acoustically capturing keywords from a rendered document
US8713418B2 (en) 2004-04-12 2014-04-29 Google Inc. Adding value to a rendered document
US8489624B2 (en) 2004-05-17 2013-07-16 Google, Inc. Processing techniques for text capture from a rendered document
US8620083B2 (en) 2004-12-03 2013-12-31 Google Inc. Method and system for character recognition
US9460346B2 (en) 2004-04-19 2016-10-04 Google Inc. Handheld device for capturing text from both a document printed on paper and a document displayed on a dynamic display device
US8090698B2 (en) 2004-05-07 2012-01-03 Ebay Inc. Method and system to facilitate a search of an information resource
US9646107B2 (en) * 2004-05-28 2017-05-09 Robert T. and Virginia T. Jenkins as Trustee of the Jenkins Family Trust Method and/or system for simplifying tree expressions such as for query reduction
US7620632B2 (en) * 2004-06-30 2009-11-17 Skyler Technology, Inc. Method and/or system for performing tree matching
US8346620B2 (en) 2004-07-19 2013-01-01 Google Inc. Automatic modification of web pages
US20060080427A1 (en) * 2004-10-12 2006-04-13 Yach David P Apparatus, and associated method, for facilitating determination of synchronization status of database copies connected by way of a radio air interface of a radio communication system
EP1845453A4 (en) * 2004-10-28 2010-06-16 Univ Fukui DATABASE MANAGEMENT DEVICE, PROCESS AND PROGRAM
US7801923B2 (en) 2004-10-29 2010-09-21 Robert T. and Virginia T. Jenkins as Trustees of the Jenkins Family Trust Method and/or system for tagging trees
US7627591B2 (en) 2004-10-29 2009-12-01 Skyler Technology, Inc. Method and/or system for manipulating tree expressions
US7630995B2 (en) 2004-11-30 2009-12-08 Skyler Technology, Inc. Method and/or system for transmitting and/or receiving data
US7636727B2 (en) 2004-12-06 2009-12-22 Skyler Technology, Inc. Enumeration of trees from finite number of nodes
US20110029504A1 (en) * 2004-12-03 2011-02-03 King Martin T Searching and accessing documents on private networks for use with captures from rendered documents
US20110075228A1 (en) * 2004-12-03 2011-03-31 King Martin T Scanner having connected and unconnected operational behaviors
US8316059B1 (en) 2004-12-30 2012-11-20 Robert T. and Virginia T. Jenkins Enumeration of rooted partial subtrees
US8615530B1 (en) 2005-01-31 2013-12-24 Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Method and/or system for tree transformation
US7681177B2 (en) 2005-02-28 2010-03-16 Skyler Technology, Inc. Method and/or system for transforming between trees and strings
US8356040B2 (en) 2005-03-31 2013-01-15 Robert T. and Virginia T. Jenkins Method and/or system for transforming between trees and arrays
US7386570B2 (en) * 2005-03-31 2008-06-10 International Business Machines Corporation Method, system and program product for providing high performance data lookup
US7899821B1 (en) 2005-04-29 2011-03-01 Karl Schiffmann Manipulation and/or analysis of hierarchical data
JP4925778B2 (ja) * 2006-03-31 2012-05-09 富士通株式会社 学習管理プログラム及び学習管理装置
US7689547B2 (en) * 2006-09-06 2010-03-30 Microsoft Corporation Encrypted data search
EP2067119A2 (en) 2006-09-08 2009-06-10 Exbiblio B.V. Optical scanners, such as hand-held optical scanners
US7743003B1 (en) 2007-05-16 2010-06-22 Google Inc. Scaling machine learning using approximate counting that uses feature hashing
US7984041B1 (en) * 2007-07-09 2011-07-19 Oracle America, Inc. Domain specific local search
WO2010096191A2 (en) * 2009-02-18 2010-08-26 Exbiblio B.V. Automatically capturing information, such as capturing information using a document-aware device
US8447066B2 (en) 2009-03-12 2013-05-21 Google Inc. Performing actions based on capturing information from rendered documents, such as documents under copyright
EP2406767A4 (en) 2009-03-12 2016-03-16 Google Inc AUTOMATIC CONTENT SUPPLY ASSOCIATED WITH CAPTURED INFORMATION, TYPE INFORMATION CAPTURED IN REAL TIME
US9684710B2 (en) * 2009-05-28 2017-06-20 Microsoft Technology Licensing, Llc Extending random number summation as an order-preserving encryption scheme
US9081799B2 (en) 2009-12-04 2015-07-14 Google Inc. Using gestalt information to identify locations in printed information
US9323784B2 (en) 2009-12-09 2016-04-26 Google Inc. Image search using text-based elements within the contents of images
US8661037B2 (en) * 2010-04-09 2014-02-25 International Business Machines Corporation System and method for multithreaded text indexing for next generation multi-core architectures
CN102737064B (zh) * 2011-04-15 2016-02-24 腾讯科技（深圳）有限公司 文件缓存方法及装置
WO2013032436A1 (en) * 2011-08-29 2013-03-07 Intel Corporation Parallel operation on b+ trees
US10311021B1 (en) * 2012-02-08 2019-06-04 Veritas Technologies Llc Systems and methods for indexing backup file metadata
US8880540B1 (en) 2012-03-28 2014-11-04 Emc Corporation Method and system for using location transformations to identify objects
US9396540B1 (en) 2012-03-28 2016-07-19 Emc Corporation Method and system for identifying anchors for fields using optical character recognition data
US9069768B1 (en) 2012-03-28 2015-06-30 Emc Corporation Method and system for creating subgroups of documents using optical character recognition data
US8832108B1 (en) * 2012-03-28 2014-09-09 Emc Corporation Method and system for classifying documents that have different scales
US8843494B1 (en) 2012-03-28 2014-09-23 Emc Corporation Method and system for using keywords to merge document clusters
US10474652B2 (en) * 2013-03-14 2019-11-12 Inpixon Optimizing wide data-type storage and analysis of data in a column store database
CN104424233A (zh) * 2013-08-26 2015-03-18 联想(北京)有限公司 一种信息处理方法和装置
US10333696B2 (en) 2015-01-12 2019-06-25 X-Prime, Inc. Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
US20180285419A1 (en) * 2015-04-07 2018-10-04 Victor Chernov Method of sparse array implementation for large arrays
US20160299894A1 (en) * 2015-04-07 2016-10-13 Victor Chernov Method of sparse array implementation for large arrays

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1995009395A1 (en) 1993-09-27 1995-04-06 Oracle Corporation Method and apparatus for parallel processing in a database system
JP2758826B2 (ja) 1994-03-02 1998-05-28 株式会社リコー 文書検索装置
US5710916A (en) * 1994-05-24 1998-01-20 Panasonic Technologies, Inc. Method and apparatus for similarity matching of handwritten data objects
US5832475A (en) 1996-03-29 1998-11-03 International Business Machines Corporation Database system and method employing data cube operator for group-by operations
US6457004B1 (en) * 1997-07-03 2002-09-24 Hitachi, Ltd. Document retrieval assisting method, system and service using closely displayed areas for titles and topics
US6374232B1 (en) * 1996-08-29 2002-04-16 Oracle Corp. Method and mechanism for retrieving values from a database
US6058392A (en) * 1996-11-18 2000-05-02 Wesley C. Sampson Revocable Trust Method for the organizational indexing, storage, and retrieval of data according to data pattern signatures
US5852822A (en) 1996-12-09 1998-12-22 Oracle Corporation Index-only tables with nested group keys
US6141655A (en) * 1997-09-23 2000-10-31 At&T Corp Method and apparatus for optimizing and structuring data by designing a cube forest data structure for hierarchically split cube forest template
US6094649A (en) * 1997-12-22 2000-07-25 Partnet, Inc. Keyword searches of structured databases
US6003036A (en) * 1998-02-12 1999-12-14 Martin; Michael W. Interval-partitioning method for multidimensional data
KR100285265B1 (ko) * 1998-02-25 2001-04-02 윤덕용 데이터 베이스 관리 시스템과 정보 검색의 밀결합을 위하여 서브 인덱스와 대용량 객체를 이용한 역 인덱스 저장 구조

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100886189B1 (ko) * 2000-11-30 2009-02-27 코퍼아이 리미티드 데이터 베이스
EP2270680A3 (en) * 2000-11-30 2011-01-19 Coppereye Limited Database
US8224829B2 (en) 2000-11-30 2012-07-17 Bernard Consulting Limited Database
KR20040103495A (ko) * 2003-05-30 2004-12-08 마이크로소프트 코포레이션 ｂ-트리를 사용한 위치 액세스
JP2004362574A (ja) * 2003-05-30 2004-12-24 Microsoft Corp Ｂツリーを使用した位置アクセス
JP2007094838A (ja) * 2005-09-29 2007-04-12 Oki Electric Ind Co Ltd 文書処理装置および文書処理方法
US7970769B2 (en) 2006-11-23 2011-06-28 Samsung Electronics Co., Ltd. Apparatus and method for optimized index search
KR100955189B1 (ko) 2008-08-11 2010-04-29 엔에이치엔(주) 문서 검색을 위한 서명 데이터 집합 생성 방법 및 시스템
JP2011258115A (ja) * 2010-06-11 2011-12-22 Nippon Telegr & Teleph Corp <Ntt> 情報格納検索装置、情報格納方法、および情報格納プログラム
WO2014141802A1 (ja) * 2013-03-12 2014-09-18 ソニー株式会社 情報処理装置、情報処理システム、および情報処理方法、並びにプログラム
KR20190013907A (ko) 2016-06-09 2019-02-11 가부시키가이샤 사이게임스 정보 처리 시스템 및 방법, 및 프로그램
US10990591B2 (en) 2016-06-09 2021-04-27 Cygames, Inc. Sub-query processing system, method, and program

Also Published As

Publication number Publication date
JP3849279B2 (ja) 2006-11-22
US20020059281A1 (en) 2002-05-16
US6678687B2 (en) 2004-01-13

Similar Documents

Publication Publication Date Title
JP3849279B2 (ja) インデクス作成方法および検索方法
US7080091B2 (en) Inverted index system and method for numeric attributes
US5897637A (en) System and method for rapidly identifying the existence and location of an item in a file
KR100798609B1 (ko) 데이터 소트 방법, 데이터 소트 장치 및 데이터 소트 프로그램을 기억하는 기억 매체
US4644471A (en) Method for processing a data base
KR100240243B1 (ko) 데이터 검색장치
Comer Heuristics for trie index minimization
JP3151730B2 (ja) データベース検索システム
JP3859044B2 (ja) インデクス作成方法および検索方法
CN110825747B (zh) 一种信息存取方法、装置和介质
JPH07210569A (ja) 情報検索方法および情報検索装置
JP2020135530A (ja) データ管理装置、データ検索方法及びプログラム
JPH08235033A (ja) オブジェクト指向データベース管理システムにおける結合演算方式
JPH0981582A (ja) 値を基本としたデータ管理装置及びデータ管理方法
JP2001022766A (ja) 多次元データベースの高速処理方法および装置
JP3578045B2 (ja) 全文検索方法及び装置及び全文検索プログラムを格納した記憶媒体
JPH06215044A (ja) 情報検索処理装置
JPH10240741A (ja) 木構造型データの管理方法
CN116955415B (zh) 基于设计层级的数据搜索系统
JP2001134594A (ja) 類似特徴量の検索方法，その検索装置およびその検索プログラム記録媒体
JPH10149367A (ja) テキスト蓄積検索装置
JP2007048318A (ja) リレーショナルデータベースの処理方法およびリレーショナルデータベース処理装置
Eastman Handling incrementally specified Boolean queries: a comparison of inverted and signature file organizations
JP2722684B2 (ja) ファイルシステムの検索装置
JP2003271649A (ja) リレーショナルデータベース問い合わせ処理方式及びリレーショナルデータベース問い合わせ処理システム

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20060515

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060523

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060714

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20060808

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20060821

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100908

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110908

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120908

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120908

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130908

Year of fee payment: 7

LAPS Cancellation because of no payment of annual fees