JPH11272676A - 分割検索方法及び装置 - Google Patents
分割検索方法及び装置Info
- Publication number
- JPH11272676A JPH11272676A JP10078765A JP7876598A JPH11272676A JP H11272676 A JPH11272676 A JP H11272676A JP 10078765 A JP10078765 A JP 10078765A JP 7876598 A JP7876598 A JP 7876598A JP H11272676 A JPH11272676 A JP H11272676A
- Authority
- JP
- Japan
- Prior art keywords
- search
- key data
- search key
- data
- bit
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/02—Comparing digital values
-
- 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/90344—Query processing by using string matching techniques
-
- 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/953—Organization of data
- Y10S707/955—Object-oriented
-
- 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/99936—Pattern matching access
-
- 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/99941—Database schema or data structure
- Y10S707/99943—Generating database or data structure, e.g. via user interface
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Databases & Information Systems (AREA)
- General Engineering & Computer Science (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computational Linguistics (AREA)
- Computational Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【課題】 検索回数を抑え、検索キーデータやマスクデ
ータの構成が複雑にならないようにしながら、異なるマ
スクパターンの２分探索を行えるようにする。 【解決手段】 検索キーデータを、上位ビットの第１検
索キーデータ及び下位ビットの第２検索キーデータに分
割し、第１検索キーデータ、及び検索対象データの該第
１検索キーデータに対応する上位ビットを比較する上位
ビット比較回路１３を備える。第２検索キーデータ、及
び前記検索対象データの該第２検索キーデータに対応す
る下位ビットを比較する下位ビット比較回路１４を備え
る。外部から入力される比較イネーブルビットＥＢ、上
位ビット比較回路１３の比較結果、及び下位ビット比較
回路１４の比較結果に従って、検索キーデータ及び検索
対象データの一致あるいは不一致を判定する判定回路１
６を備える。
ータの構成が複雑にならないようにしながら、異なるマ
スクパターンの２分探索を行えるようにする。 【解決手段】 検索キーデータを、上位ビットの第１検
索キーデータ及び下位ビットの第２検索キーデータに分
割し、第１検索キーデータ、及び検索対象データの該第
１検索キーデータに対応する上位ビットを比較する上位
ビット比較回路１３を備える。第２検索キーデータ、及
び前記検索対象データの該第２検索キーデータに対応す
る下位ビットを比較する下位ビット比較回路１４を備え
る。外部から入力される比較イネーブルビットＥＢ、上
位ビット比較回路１３の比較結果、及び下位ビット比較
回路１４の比較結果に従って、検索キーデータ及び検索
対象データの一致あるいは不一致を判定する判定回路１
６を備える。
Description
【０００１】
【発明の属する技術分野】本発明は、２分探索を用いて
値を検索する際、検索対象データを複数の部分に分ける
と共に、この内のどの部分が一致すれば、一致したとい
う判定結果を出力するかを示すビット列を設け、これに
より、複数の検索条件に基づいた検索を、１回ないしは
少ない回数で行うことを可能とする分割検索方法及び装
置に関する。
値を検索する際、検索対象データを複数の部分に分ける
と共に、この内のどの部分が一致すれば、一致したとい
う判定結果を出力するかを示すビット列を設け、これに
より、複数の検索条件に基づいた検索を、１回ないしは
少ない回数で行うことを可能とする分割検索方法及び装
置に関する。
【０００２】
【従来の技術】２分割検索方法を用いた場合、１回の検
索で使用できるマスク・パターンは、１種類である。検
索キーと、検索対象のデータの一定の一部が一致してい
ればよいものと、全部が一致していなければならないも
のとが混在している場合がある。ＡＴＭ（asynchronous
transfer mode）スイッチにおいて、ＶＰＩ／ＶＣＩ
（Ｖirtual Ｐath Ｉdentifier ／Ｖirtual Ｃhannel
Ｉdentifire ）変換を行う場合は、その一例である。
索で使用できるマスク・パターンは、１種類である。検
索キーと、検索対象のデータの一定の一部が一致してい
ればよいものと、全部が一致していなければならないも
のとが混在している場合がある。ＡＴＭ（asynchronous
transfer mode）スイッチにおいて、ＶＰＩ／ＶＣＩ
（Ｖirtual Ｐath Ｉdentifier ／Ｖirtual Ｃhannel
Ｉdentifire ）変換を行う場合は、その一例である。
【０００３】
【発明が解決しようとする課題】異なるマスク・パター
ンで２分探索を行う場合、検索キーや検索対象データが
同じでも、従来では、複数回に分けて２分探索の検索を
行う必要があった。あるいは、データの各エントリ毎に
マスクデータを保存しておくか、特別な値を用いてデー
タを登録する必要があった。
ンで２分探索を行う場合、検索キーや検索対象データが
同じでも、従来では、複数回に分けて２分探索の検索を
行う必要があった。あるいは、データの各エントリ毎に
マスクデータを保存しておくか、特別な値を用いてデー
タを登録する必要があった。
【０００４】複数回に分けて検索する場合、検索に要す
る時間が多くかかってしまうのは明らかである。各エン
トリ毎にマスクデータを保存しておく場合、データ保存
のための容量が倍になってしまう。又、特別な値を用い
てデータを区別する場合、全体で識別しなくてはならな
いデータにおいて、その値を使用することができなくな
ってしまう。
る時間が多くかかってしまうのは明らかである。各エン
トリ毎にマスクデータを保存しておく場合、データ保存
のための容量が倍になってしまう。又、特別な値を用い
てデータを区別する場合、全体で識別しなくてはならな
いデータにおいて、その値を使用することができなくな
ってしまう。
【０００５】本発明は、前記従来の問題点を解決するべ
くなされたもので、検索回数を抑えながら、又検索キー
・データやマスクデータの構成が複雑にならないように
しながら、異なるマスク・パターンの２分探索を行える
ようにすることができる分割検索方法及び装置を提供す
ることを目的とする。
くなされたもので、検索回数を抑えながら、又検索キー
・データやマスクデータの構成が複雑にならないように
しながら、異なるマスク・パターンの２分探索を行える
ようにすることができる分割検索方法及び装置を提供す
ることを目的とする。
【０００６】
【課題を解決するための手段】まず、本願の第１発明の
分割検索方法は、２分探索を用いる分割検索方法におい
て、検索対象となるデータを複数のブロックに分けると
共に、各ブロックの検索結果に寄与する情報を示すビッ
ト列を設けることにより、複数の検索条件を１度の検索
で実行することができるようにし、前記課題を解決した
ものである。
分割検索方法は、２分探索を用いる分割検索方法におい
て、検索対象となるデータを複数のブロックに分けると
共に、各ブロックの検索結果に寄与する情報を示すビッ
ト列を設けることにより、複数の検索条件を１度の検索
で実行することができるようにし、前記課題を解決した
ものである。
【０００７】次に、本願の第２発明の分割検索装置は、
検索キー・データを、上位ビットの第１検索キー・デー
タ及び下位ビットの第２検索キー・データに分割し、前
記第１検索キー・データ、及び、検索対象データの該第
１検索キー・データに対応する上位ビットを比較する上
位ビット比較回路と、前記第２検索キー・データ、及
び、前記検索対象データの該第２検索キー・データに対
応する下位ビットを比較する下位ビット比較回路と、外
部から入力される比較イネーブル・ビット、前記上位ビ
ット比較回路の比較結果、及び、前記下位ビット比較回
路の比較結果に従って、前記検索キー・データ及び前記
検索対象データの一致あるいは不一致を判定する判定回
路とを備えるようにしたことにより、前記課題を解決し
たものである。
検索キー・データを、上位ビットの第１検索キー・デー
タ及び下位ビットの第２検索キー・データに分割し、前
記第１検索キー・データ、及び、検索対象データの該第
１検索キー・データに対応する上位ビットを比較する上
位ビット比較回路と、前記第２検索キー・データ、及
び、前記検索対象データの該第２検索キー・データに対
応する下位ビットを比較する下位ビット比較回路と、外
部から入力される比較イネーブル・ビット、前記上位ビ
ット比較回路の比較結果、及び、前記下位ビット比較回
路の比較結果に従って、前記検索キー・データ及び前記
検索対象データの一致あるいは不一致を判定する判定回
路とを備えるようにしたことにより、前記課題を解決し
たものである。
【０００８】以下、本発明の作用について、簡単に説明
する。
する。
【０００９】異なるデータの各エントリ毎に、各ブロッ
ク毎のプライオリティを設定するビットを設ける。又、
検索キー・データを、上位ビットの第１検索キー・デー
タ及び下位ビットの第２検索キー・データに分割する。
ク毎のプライオリティを設定するビットを設ける。又、
検索キー・データを、上位ビットの第１検索キー・デー
タ及び下位ビットの第２検索キー・データに分割する。
【００１０】このようにして、前記第１検索キー・デー
タ、及び検索対象データの該第１検索キー・データに対
応する上位ビットを比較する。又、前記第２検索キー・
データ、及び前記検索対象データの該第２検索キー・デ
ータに対応する下位ビットを比較する。更に、外部から
入力される比較イネーブル・ビット、前記上位ビットの
比較結果、及び前記下位ビットの比較結果に従って、前
記検索キー・データ及び前記検索対象データの一致ある
いは不一致を判定する。
タ、及び検索対象データの該第１検索キー・データに対
応する上位ビットを比較する。又、前記第２検索キー・
データ、及び前記検索対象データの該第２検索キー・デ
ータに対応する下位ビットを比較する。更に、外部から
入力される比較イネーブル・ビット、前記上位ビットの
比較結果、及び前記下位ビットの比較結果に従って、前
記検索キー・データ及び前記検索対象データの一致ある
いは不一致を判定する。
【００１１】これにより、検索回数を抑えながら、又検
索キー・データやマスクデータの構成が複雑にならない
ようにしながら、異なるマスク・パターンの２分探索を
行えるようにすることができる。
索キー・データやマスクデータの構成が複雑にならない
ようにしながら、異なるマスク・パターンの２分探索を
行えるようにすることができる。
【００１２】
【発明の実施の形態】まず、本発明が適用された実施形
態の分割検索装置の概要について説明する。
態の分割検索装置の概要について説明する。
【００１３】本実施形態では、検索対象データを２つに
分けて、分割検索を行う。又、後述するように、本実施
形態は、ＡＴＭのＶＰＩ／ＶＣＩ変換に用いる。
分けて、分割検索を行う。又、後述するように、本実施
形態は、ＡＴＭのＶＰＩ／ＶＣＩ変換に用いる。
【００１４】１エントリ３２ビットを３つの部分に分
け、最上位の１ビットを除く上位１５ビットを第１検索
キー・データＰＫとする。又、残りの下位１６ビット
を、第２検索キー・データＳＫとする。最上位の１ビッ
トは、比較イネーブル・ビットＥＢである。
け、最上位の１ビットを除く上位１５ビットを第１検索
キー・データＰＫとする。又、残りの下位１６ビット
を、第２検索キー・データＳＫとする。最上位の１ビッ
トは、比較イネーブル・ビットＥＢである。
【００１５】この比較イネーブル・ビットＥＢは、第１
検索キー・データＰＫのみの一致を有効とするか否かを
示す。該比較イネーブル・ビットＥＢが“１”であれ
ば、第１検索キー・データＰＫのみを用いた検索の比較
を行う。一方、該比較イネーブル・ビットＥＢが“０”
であれば、第１検索キー・データＰＫ及び第２検索キー
・データＳＫを共に用いた検索の比較を行う。該比較イ
ネーブル・ビットＥＢは、各エントリ毎に、有効又は無
効を指定できる。
検索キー・データＰＫのみの一致を有効とするか否かを
示す。該比較イネーブル・ビットＥＢが“１”であれ
ば、第１検索キー・データＰＫのみを用いた検索の比較
を行う。一方、該比較イネーブル・ビットＥＢが“０”
であれば、第１検索キー・データＰＫ及び第２検索キー
・データＳＫを共に用いた検索の比較を行う。該比較イ
ネーブル・ビットＥＢは、各エントリ毎に、有効又は無
効を指定できる。
【００１６】検索結果を示す信号は、探索一致信号ＨＯ
Ｎと探索一致信号ＰＫＨＯＮの２つがある。まず、探索
一致信号ＨＯＮは、検索が成功したか否かを示す信号で
ある。又、探索一致信号ＰＫＨＯＮは、検索が成功した
場合に、全体が一致したのか、あるいは第１検索キー・
データＰＫのみ一致したのかを示す。
Ｎと探索一致信号ＰＫＨＯＮの２つがある。まず、探索
一致信号ＨＯＮは、検索が成功したか否かを示す信号で
ある。又、探索一致信号ＰＫＨＯＮは、検索が成功した
場合に、全体が一致したのか、あるいは第１検索キー・
データＰＫのみ一致したのかを示す。
【００１７】本実施形態では、通常モードに加え、２重
モードを有している。この２重モードでは、第１検索キ
ー・データＰＫのみが一致するエントリが存在し、その
エントリの比較イネーブル・ビットＥＢが“１”だった
場合は、探索一致信号ＰＫＨＯＮと探索一致信号ＨＯＮ
が共に“１”になる。この場合は、第２検索キー・デー
タＳＫの一致あるいは不一致に関わらず、第１検索キー
・データＰＫのみの一致で、そのエントリがヒットした
ものとみなす。第１検索キー・データＰＫ及び第２検索
キー・データＳＫが共に一致し、比較イネーブル・ビッ
トＥＢが“０”のエントリが存在した場合は、探索一致
信号ＰＫＨＯＮが“０”で、探索一致信号ＨＯＮが
“１”となる。
モードを有している。この２重モードでは、第１検索キ
ー・データＰＫのみが一致するエントリが存在し、その
エントリの比較イネーブル・ビットＥＢが“１”だった
場合は、探索一致信号ＰＫＨＯＮと探索一致信号ＨＯＮ
が共に“１”になる。この場合は、第２検索キー・デー
タＳＫの一致あるいは不一致に関わらず、第１検索キー
・データＰＫのみの一致で、そのエントリがヒットした
ものとみなす。第１検索キー・データＰＫ及び第２検索
キー・データＳＫが共に一致し、比較イネーブル・ビッ
トＥＢが“０”のエントリが存在した場合は、探索一致
信号ＰＫＨＯＮが“０”で、探索一致信号ＨＯＮが
“１”となる。
【００１８】なお、このモードにおいては、１つの第１
検索キー・データＰＫに一致するエントリが複数存在し
ないように注意しなければならない。又、このモードを
利用することにより、ＡＴＭのＶＰＩ／ＶＣＩ変換を同
時に行うことができる。
検索キー・データＰＫに一致するエントリが複数存在し
ないように注意しなければならない。又、このモードを
利用することにより、ＡＴＭのＶＰＩ／ＶＣＩ変換を同
時に行うことができる。
【００１９】以下、図を用いて本実施形態を詳細に説明
する。
する。
【００２０】まず、図１は、本実施形態の全体構成を示
すブロック図である。
すブロック図である。
【００２１】図１に示すように、本実施形態の分割検索
装置は、コントローラ１と、アドレス発生回路３と、メ
モリ５とにより構成されている。該分割検索装置では、
アドレス発生回路３で発生させたアドレスＡＤをメモリ
５に供給する。このようにして該メモリ５から読み出さ
れる検索対象データＤを、コントローラ１において、第
１検索キー・データＰＫ及び第２検索キー・データＳＫ
で構成される検索キー・データＫＤと比較ながら、２分
探索の分割検索方法を行う。このような２分探索の際、
アドレス発生回路３は、コントローラ１が出力する大小
比較結果信号ＧＬに従って、アドレスＡＤを出力する。
又、該２分探索の結果は、探索一致信号ＨＯＮ、及び探
索一致信号ＰＫＨＯＮにより出力される。
装置は、コントローラ１と、アドレス発生回路３と、メ
モリ５とにより構成されている。該分割検索装置では、
アドレス発生回路３で発生させたアドレスＡＤをメモリ
５に供給する。このようにして該メモリ５から読み出さ
れる検索対象データＤを、コントローラ１において、第
１検索キー・データＰＫ及び第２検索キー・データＳＫ
で構成される検索キー・データＫＤと比較ながら、２分
探索の分割検索方法を行う。このような２分探索の際、
アドレス発生回路３は、コントローラ１が出力する大小
比較結果信号ＧＬに従って、アドレスＡＤを出力する。
又、該２分探索の結果は、探索一致信号ＨＯＮ、及び探
索一致信号ＰＫＨＯＮにより出力される。
【００２２】次に、図２は、本実施形態で用いる検索テ
ーブルである。
ーブルである。
【００２３】この場合、検索キー全体の長さは３１ビッ
トとなる。比較イネーブル・ビットＥＢが０の場合は、
３１ビット全てが一致した場合にのみ、一致したという
判定結果を出力する。比較イネーブル・ビットＥＢが
“１”の場合には、検索キーの上位１５ビットである第
１検索キー・データＰＫだけでも一致していれば、下位
１６ビットの第２検索キー・データＳＫの一致あるいは
不一致に関わらず、一致したという判定結果を出力す
る。又、比較イネーブル・ビットＥＢが“１”で、一致
という判定結果の場合、探索一致信号ＨＯＮだけでな
く、ＰＫＯＮも“１”（一致）とする。
トとなる。比較イネーブル・ビットＥＢが０の場合は、
３１ビット全てが一致した場合にのみ、一致したという
判定結果を出力する。比較イネーブル・ビットＥＢが
“１”の場合には、検索キーの上位１５ビットである第
１検索キー・データＰＫだけでも一致していれば、下位
１６ビットの第２検索キー・データＳＫの一致あるいは
不一致に関わらず、一致したという判定結果を出力す
る。又、比較イネーブル・ビットＥＢが“１”で、一致
という判定結果の場合、探索一致信号ＨＯＮだけでな
く、ＰＫＯＮも“１”（一致）とする。
【００２４】図３は、第１例のコントローラ１の構成を
示すブロック図である。
示すブロック図である。
【００２５】この図３において、コントローラ１は、一
致検査回路１０と、大小比較回路２０とにより構成され
ている。
致検査回路１０と、大小比較回路２０とにより構成され
ている。
【００２６】まず、一致検査回路１０は、図４に示すよ
うに、入力された比較イネーブル・ビットＥＢを記憶す
るレジスタ１２と、検索キー・データＫＤの第１検索キ
ー・データＰＫ及び検索対象データＤを比較する上位ビ
ット比較回路１３と、検索キー・データＫＤの第２検索
キー・データＳＫ及び検索対象データＤを比較する下位
ビット比較回路１４と、判定回路１６とにより構成とな
っている。このような構成の一致検査回路１０は、全体
として、図５の真理値表のように、上位一致の判定結
果、下位一致の判定結果、及び、比較イネーブル・ビッ
トＥＢに基づいて、探索一致信号ＨＯＮ及び探索一致信
号ＰＫＨＯＮを生成し、出力する。
うに、入力された比較イネーブル・ビットＥＢを記憶す
るレジスタ１２と、検索キー・データＫＤの第１検索キ
ー・データＰＫ及び検索対象データＤを比較する上位ビ
ット比較回路１３と、検索キー・データＫＤの第２検索
キー・データＳＫ及び検索対象データＤを比較する下位
ビット比較回路１４と、判定回路１６とにより構成とな
っている。このような構成の一致検査回路１０は、全体
として、図５の真理値表のように、上位一致の判定結
果、下位一致の判定結果、及び、比較イネーブル・ビッ
トＥＢに基づいて、探索一致信号ＨＯＮ及び探索一致信
号ＰＫＨＯＮを生成し、出力する。
【００２７】次に、図３の大小比較回路２０は、３１ビ
ットのデータの大小比較回路となっている。該大小比較
回路２０は、特に一致を判定するための回路とはなって
いない。これは、一致の場合は、回路１０により判定可
能なためである。該大小比較回路２０は、検索キーと検
索対象データの２つの３１ビットデータの大小によっ
て、大小比較結果信号ＧＬを生成し、出力する。
ットのデータの大小比較回路となっている。該大小比較
回路２０は、特に一致を判定するための回路とはなって
いない。これは、一致の場合は、回路１０により判定可
能なためである。該大小比較回路２０は、検索キーと検
索対象データの２つの３１ビットデータの大小によっ
て、大小比較結果信号ＧＬを生成し、出力する。
【００２８】図７は、第２例のコントローラ１の構成を
示すブロック図である。
示すブロック図である。
【００２９】図示されるように、コントローラ１は、レ
ジスタ１２と、上位ビット比較回路１３と、下位ビット
比較回路１４と、判定回路１７とにより構成されてい
る。前記比較回路１３と比較回路１４は、それぞれ１５
ビット及び１６ビットの一致の検出を含む大小比較回路
である。前記判定回路１７は、まず、前述した図５の真
理値表のように、上位一致の判定結果、下位一致の判定
結果、及び、比較イネーブル・ビットＥＢに基づいて、
探索一致信号ＨＯＮ及び探索一致信号ＰＫＨＯＮを生成
し、出力する。又、該判定回路１７は、図６の真理値表
のように、上位一致の判定結果、上位大小の判定結果、
及び、下位大小の判定結果に基づいて、大小比較結果信
号ＧＬを生成し、出力する。
ジスタ１２と、上位ビット比較回路１３と、下位ビット
比較回路１４と、判定回路１７とにより構成されてい
る。前記比較回路１３と比較回路１４は、それぞれ１５
ビット及び１６ビットの一致の検出を含む大小比較回路
である。前記判定回路１７は、まず、前述した図５の真
理値表のように、上位一致の判定結果、下位一致の判定
結果、及び、比較イネーブル・ビットＥＢに基づいて、
探索一致信号ＨＯＮ及び探索一致信号ＰＫＨＯＮを生成
し、出力する。又、該判定回路１７は、図６の真理値表
のように、上位一致の判定結果、上位大小の判定結果、
及び、下位大小の判定結果に基づいて、大小比較結果信
号ＧＬを生成し、出力する。
【００３０】以上説明したように、第１例のコントロー
ラ１を用いるにしても、第２例のコントローラ１を用い
るにしても、本実施形態によれば、本発明を効果的に適
用することができ、検索回数を抑えながら、又検索キー
・データやマスクデータの構成が複雑にならないように
しながら、異なるマスク・パターンの２分探索を行える
ようにすることができる。
ラ１を用いるにしても、第２例のコントローラ１を用い
るにしても、本実施形態によれば、本発明を効果的に適
用することができ、検索回数を抑えながら、又検索キー
・データやマスクデータの構成が複雑にならないように
しながら、異なるマスク・パターンの２分探索を行える
ようにすることができる。
【００３１】ここで、ＶＰＩ／ＶＣＩ変換へ利用する場
合を考える。
合を考える。
【００３２】例えば、図８のようにＶＣＣ（Ｖirtual
Ｃhannel Ｃonnention ）のＶＣＣ１、ＶＣＣ２、又、
ＶＰＣ（Ｖirtual Ｐath Ｃonnection ）のＶＰＣ１が
張られている場合について考えてみる。従来例では、
“ＦＦＦＦ”をＶＤＣを表すために用いて、図９に示す
ように行われている。この図９の従来例では、ＶＣＩの
“ＦＦＦＦ”という値が使用できなかった。これに対し
て、前述した本実施形態等、例えば図１０のように本発
明を適用すると、従来例のように使用できない値はな
い。
Ｃhannel Ｃonnention ）のＶＣＣ１、ＶＣＣ２、又、
ＶＰＣ（Ｖirtual Ｐath Ｃonnection ）のＶＰＣ１が
張られている場合について考えてみる。従来例では、
“ＦＦＦＦ”をＶＤＣを表すために用いて、図９に示す
ように行われている。この図９の従来例では、ＶＣＩの
“ＦＦＦＦ”という値が使用できなかった。これに対し
て、前述した本実施形態等、例えば図１０のように本発
明を適用すると、従来例のように使用できない値はな
い。
【００３３】
【発明の効果】本発明によれば、検索回数を抑えなが
ら、又検索キー・データやマスクデータの構成が複雑に
ならないようにしながら、異なるマスク・パターンの２
分探索を行えるようにすることができる。
ら、又検索キー・データやマスクデータの構成が複雑に
ならないようにしながら、異なるマスク・パターンの２
分探索を行えるようにすることができる。
【図１】本発明が適用された分割検索装置の実施形態の
全体構成を示すブロック図
全体構成を示すブロック図
【図２】前記実施形態で用いる検索テーブルを示す線図
【図３】前記実施形態で用いる第１例のコントローラの
構成を示すブロック図
構成を示すブロック図
【図４】前記実施形態で用いる一致検査回路の構成を示
すブロック図
すブロック図
【図５】前記一致検査回路の動作を示す真理値表の線図
【図６】前記実施形態で用いる大小比較回路の動作を示
す真理値表の線図
す真理値表の線図
【図７】前記実施形態で用いる第２例のコントローラの
構成を示すブロック図
構成を示すブロック図
【図８】従来からのＶＣＣ及びＶＰＣを示す線図
【図９】従来のＶＰＩ／ＶＣＩ変換を示す線図
【図１０】前記実施形態を利用したＶＰＩ／ＶＣＩ変換
を示す線図
を示す線図
１…コントローラ ３…アドレス発生回路 ５…メモリ １０…一致検査回路 １２…レジスタ １３…上位ビット比較回路 １４…下位ビット比較回路 １６、１７…判定回路
Claims (2)
- 【請求項１】２分探索を用いる分割検索方法において、 検索対象となるデータを複数のブロックに分けると共
に、 各ブロックの検索結果に寄与する情報を示すビット列を
設けることにより、 複数の検索条件を１度の検索で実行することができるよ
うにしたことを特徴とする分割検索方法。 - 【請求項２】検索キー・データを、上位ビットの第１検
索キー・データ及び下位ビットの第２検索キー・データ
に分割し、前記第１検索キー・データ、及び、検索対象
データの該第１検索キー・データに対応する上位ビット
を比較する上位ビット比較回路と、 前記第２検索キー・データ、及び、前記検索対象データ
の該第２検索キー・データに対応する下位ビットを比較
する下位ビット比較回路と、 外部から入力される比較イネーブル・ビット、前記上位
ビット比較回路の比較結果、及び、前記下位ビット比較
回路の比較結果に従って、前記検索キー・データ及び前
記検索対象データの一致あるいは不一致を判定する判定
回路とを備えるようにしたことを特徴とする分割検索装
置。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10078765A JPH11272676A (ja) | 1998-03-26 | 1998-03-26 | 分割検索方法及び装置 |
| US09/274,809 US6457001B1 (en) | 1998-03-26 | 1999-03-23 | Method and apparatus for data retrieval |
| US10/191,594 US20020174116A1 (en) | 1998-03-26 | 2002-07-10 | Method and apparatus for data retrieval |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10078765A JPH11272676A (ja) | 1998-03-26 | 1998-03-26 | 分割検索方法及び装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11272676A true JPH11272676A (ja) | 1999-10-08 |
Family
ID=13671009
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10078765A Pending JPH11272676A (ja) | 1998-03-26 | 1998-03-26 | 分割検索方法及び装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (2) | US6457001B1 (ja) |
| JP (1) | JPH11272676A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1150496A3 (en) * | 2000-04-24 | 2003-03-12 | Nec Corporation | Segmented processing method for a transport stream for digital television and recording media for the same |
| WO2003107352A1 (en) * | 2002-06-13 | 2003-12-24 | Intel Corporation | Method and system for performing inserts and lookups in memory |
| KR100484484B1 (ko) * | 2002-05-20 | 2005-04-20 | 주식회사 케이티 | 정수형의 데이터를 갖는 자료구조에서 구간탐색에 의한이분검출 방법 및 그 장치 |
| US7249216B2 (en) | 2002-12-12 | 2007-07-24 | Fujitsu Limited | Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2003324464A (ja) * | 2002-04-30 | 2003-11-14 | Fujitsu Ltd | データ検索装置及びデータ検索方法 |
| US20080228700A1 (en) | 2007-03-16 | 2008-09-18 | Expanse Networks, Inc. | Attribute Combination Discovery |
| JP5679618B2 (ja) * | 2007-05-31 | 2015-03-04 | 株式会社トリマティス | 光増幅器 |
| US20090043752A1 (en) * | 2007-08-08 | 2009-02-12 | Expanse Networks, Inc. | Predicting Side Effect Attributes |
| US7917438B2 (en) | 2008-09-10 | 2011-03-29 | Expanse Networks, Inc. | System for secure mobile healthcare selection |
| US20100063830A1 (en) * | 2008-09-10 | 2010-03-11 | Expanse Networks, Inc. | Masked Data Provider Selection |
| US8200509B2 (en) * | 2008-09-10 | 2012-06-12 | Expanse Networks, Inc. | Masked data record access |
| US20100076950A1 (en) * | 2008-09-10 | 2010-03-25 | Expanse Networks, Inc. | Masked Data Service Selection |
| US20100169313A1 (en) * | 2008-12-30 | 2010-07-01 | Expanse Networks, Inc. | Pangenetic Web Item Feedback System |
| US8108406B2 (en) | 2008-12-30 | 2012-01-31 | Expanse Networks, Inc. | Pangenetic web user behavior prediction system |
| US8386519B2 (en) * | 2008-12-30 | 2013-02-26 | Expanse Networks, Inc. | Pangenetic web item recommendation system |
| US20100169262A1 (en) * | 2008-12-30 | 2010-07-01 | Expanse Networks, Inc. | Mobile Device for Pangenetic Web |
| US8255403B2 (en) * | 2008-12-30 | 2012-08-28 | Expanse Networks, Inc. | Pangenetic web satisfaction prediction system |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5321843A (en) * | 1989-03-14 | 1994-06-14 | Kabushiki Kaisha Dainichi | Information retrieval apparatus and information editing system using the same |
| WO1994001828A1 (en) * | 1992-07-02 | 1994-01-20 | Wellfleet Communications | Data packet processing method and apparatus |
| US5813001A (en) * | 1993-10-22 | 1998-09-22 | Nodel Corporation | Method for performing optimized intelligent searches of knowledge bases using submaps associated with search objects |
| US5438535A (en) * | 1994-03-29 | 1995-08-01 | Panasonic Technologies, Inc. | Content addressable memory system |
| JP3302578B2 (ja) * | 1996-10-21 | 2002-07-15 | 富士通株式会社 | Ｏａｍ処理装置 |
| US5995971A (en) * | 1997-09-18 | 1999-11-30 | Micdrosoft Corporation | Apparatus and accompanying methods, using a trie-indexed hierarchy forest, for storing wildcard-based patterns and, given an input key, retrieving, from the forest, a stored pattern that is identical to or more general than the key |
| US6112207A (en) * | 1997-10-31 | 2000-08-29 | Oracle Corporation | Apparatus and method which features linearizing attributes of an information object into a string of bytes for object representation and storage in a database system |
-
1998
- 1998-03-26 JP JP10078765A patent/JPH11272676A/ja active Pending
-
1999
- 1999-03-23 US US09/274,809 patent/US6457001B1/en not_active Expired - Fee Related
-
2002
- 2002-07-10 US US10/191,594 patent/US20020174116A1/en not_active Abandoned
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1150496A3 (en) * | 2000-04-24 | 2003-03-12 | Nec Corporation | Segmented processing method for a transport stream for digital television and recording media for the same |
| KR100484484B1 (ko) * | 2002-05-20 | 2005-04-20 | 주식회사 케이티 | 정수형의 데이터를 갖는 자료구조에서 구간탐색에 의한이분검출 방법 및 그 장치 |
| WO2003107352A1 (en) * | 2002-06-13 | 2003-12-24 | Intel Corporation | Method and system for performing inserts and lookups in memory |
| US7249216B2 (en) | 2002-12-12 | 2007-07-24 | Fujitsu Limited | Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method |
Also Published As
| Publication number | Publication date |
|---|---|
| US6457001B1 (en) | 2002-09-24 |
| US20020174116A1 (en) | 2002-11-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH11272676A (ja) | 分割検索方法及び装置 | |
| US6775281B1 (en) | Method and apparatus for a four-way hash table | |
| US7277426B2 (en) | Method and apparatus for reordering entries in a multi probe lookup | |
| US5452451A (en) | System for plural-string search with a parallel collation of a first partition of each string followed by finite automata matching of second partitions | |
| US6526474B1 (en) | Content addressable memory (CAM) with accesses to multiple CAM arrays used to generate result for various matching sizes | |
| US6606681B1 (en) | Optimized content addressable memory (CAM) | |
| US5327431A (en) | Method and apparatus for source routing bridging | |
| US20020138648A1 (en) | Hash compensation architecture and method for network address lookup | |
| US5276829A (en) | Data processing system including cache memory for rapidly converting a logical address into a physical address using shared memory flag | |
| EP1290542B1 (en) | Determination of a minimum or maximum value in a set of data | |
| JP3190700B2 (ja) | アドレス変換装置 | |
| US6809944B2 (en) | CAM with automatic next free address pointer | |
| TWI276955B (en) | Method, apparatus, machine accessible medium, and system for performing inserts and lookups in memory | |
| JP2939584B1 (ja) | 検索回路 | |
| JP2001160291A (ja) | 連想メモリ | |
| JP2004187114A (ja) | アドレスフィルタリング装置 | |
| JPS5994287A (ja) | 高速アドレス変換装置 | |
| JPH03122739A (ja) | キャッシュメモリ | |
| WO2003052765A1 (en) | Finding free space in a content addressable memory | |
| TW200917750A (en) | Content scanning circuit and method | |
| KR20010054699A (ko) | 에이티엠 셀의 채널연결정보를 검색하기 위한 방법 및 장치 | |
| JPH07334359A (ja) | 半導体集積回路装置 | |
| JPH052608A (ja) | データ検索装置 | |
| JPH05324478A (ja) | 情報処理装置 | |
| JPH03232037A (ja) | キャッシュ方法およびキャッシュメモリ装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050307 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080415 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20080826 |