JPH1063675A - データ探索方法及びそれを適用したデータ探索装置 - Google Patents
データ探索方法及びそれを適用したデータ探索装置Info
- Publication number
- JPH1063675A JPH1063675A JP8217547A JP21754796A JPH1063675A JP H1063675 A JPH1063675 A JP H1063675A JP 8217547 A JP8217547 A JP 8217547A JP 21754796 A JP21754796 A JP 21754796A JP H1063675 A JPH1063675 A JP H1063675A
- Authority
- JP
- Japan
- Prior art keywords
- search
- data
- program
- storage device
- tree structure
- 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
- 238000000034 method Methods 0.000 title description 31
- 238000013500 data storage Methods 0.000 abstract description 35
- 238000010586 diagram Methods 0.000 description 6
- 230000006870 function Effects 0.000 description 2
- 238000000547 structure data Methods 0.000 description 2
- 238000012795 verification Methods 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】
【課題】 データ記憶装置の処理速度の影響を受けずに
高速にデータ探索を実行できるデータ探索装置を提供す
ること。 【解決手段】 このデータ探索装置は、探索対象となる
データを木構造でデータベースとして格納したデータ記
憶装置１１と、データベースから木構造に対応する条件
分岐を有する探索プログラムを生成する探索プログラム
生成部１２と、探索プログラムを格納するプログラム記
憶装置１３と、探索キーの入力に従って探索プログラム
を実行してデータ探索を行う探索プログラム実行部１４
と、探索キーを入力すると共に、探索プログラム実行部
１４によるデータ探索の探索結果を出力する入出力イン
ターフェイス１５とを備えて構成される。これにより、
探索プログラムの実行に際してデータ記憶装置１１を使
用する必要が無く、データ記憶装置１１の処理速度に依
存せずに高速なデータ探索が可能となる。
高速にデータ探索を実行できるデータ探索装置を提供す
ること。 【解決手段】 このデータ探索装置は、探索対象となる
データを木構造でデータベースとして格納したデータ記
憶装置１１と、データベースから木構造に対応する条件
分岐を有する探索プログラムを生成する探索プログラム
生成部１２と、探索プログラムを格納するプログラム記
憶装置１３と、探索キーの入力に従って探索プログラム
を実行してデータ探索を行う探索プログラム実行部１４
と、探索キーを入力すると共に、探索プログラム実行部
１４によるデータ探索の探索結果を出力する入出力イン
ターフェイス１５とを備えて構成される。これにより、
探索プログラムの実行に際してデータ記憶装置１１を使
用する必要が無く、データ記憶装置１１の処理速度に依
存せずに高速なデータ探索が可能となる。
Description
【０００１】
【発明の属する技術分野】本発明は、主としてＬＳＩ等
のレイアウトにおける大容量の図形データの高速な探索
が可能なデータベースに関するデータ探索方法及びそれ
を適用したデータ探索装置に関する。
のレイアウトにおける大容量の図形データの高速な探索
が可能なデータベースに関するデータ探索方法及びそれ
を適用したデータ探索装置に関する。
【０００２】
【従来の技術】従来、この種のデータベースに関するデ
ータ探索は、ＬＳＩレイアウトにおけるチップ内配線や
検証システム等において与えられた点を含む図形や近傍
の図形を探索するために適用されている。このような関
連技術としては、例えば特開平７−３１９８９４号公報
に開示された高速データ探索装置および高速データ探索
方法が挙げられる。
ータ探索は、ＬＳＩレイアウトにおけるチップ内配線や
検証システム等において与えられた点を含む図形や近傍
の図形を探索するために適用されている。このような関
連技術としては、例えば特開平７−３１９８９４号公報
に開示された高速データ探索装置および高速データ探索
方法が挙げられる。
【０００３】図９は、この高速データ探索装置の基本構
成を示したブロック図である。この高速データ探索装置
は、データベース中の特定の一部のデータ集合を対象と
して図形探索を行うものであり、探索範囲決定部９２，
探索範囲記憶用レジスタ９３，探索処理部９５，データ
格納用メモリ９３，及び入出力インターフェイス９１か
ら構成されている。
成を示したブロック図である。この高速データ探索装置
は、データベース中の特定の一部のデータ集合を対象と
して図形探索を行うものであり、探索範囲決定部９２，
探索範囲記憶用レジスタ９３，探索処理部９５，データ
格納用メモリ９３，及び入出力インターフェイス９１か
ら構成されている。
【０００４】この高速データ探索装置では、探索範囲及
び探索キーを入出力インターフェイス９１に入力し、探
索範囲決定部９２で探索範囲アドレスを決定し、このア
ドレスを探索範囲記憶用レジスタ９４に記憶し、探索処
理部９５でこのアドレスを用いて探索し、入出力インタ
ーフェイス９１から探索結果を出力することにより、デ
ータベースの木構造の根元よりも末端方向の特定の節部
から探索を行うようになっている。
び探索キーを入出力インターフェイス９１に入力し、探
索範囲決定部９２で探索範囲アドレスを決定し、このア
ドレスを探索範囲記憶用レジスタ９４に記憶し、探索処
理部９５でこのアドレスを用いて探索し、入出力インタ
ーフェイス９１から探索結果を出力することにより、デ
ータベースの木構造の根元よりも末端方向の特定の節部
から探索を行うようになっている。
【０００５】
【発明が解決しようとする課題】上述した高速データ探
索装置による高速データ探索の場合、データ格納用メモ
リに記憶されたデータベースの木構造を探索するために
データ格納用メモリ及び探索処理部間のデータ転送が頻
繁に行われることにより、データ探索速度がデータ格納
用メモリ，即ち、データ記憶装置の処理速度の影響を受
けてしまうため、探索処理部の演算処理速度を速くして
もデータ探索速度が速くならないという問題がある。
索装置による高速データ探索の場合、データ格納用メモ
リに記憶されたデータベースの木構造を探索するために
データ格納用メモリ及び探索処理部間のデータ転送が頻
繁に行われることにより、データ探索速度がデータ格納
用メモリ，即ち、データ記憶装置の処理速度の影響を受
けてしまうため、探索処理部の演算処理速度を速くして
もデータ探索速度が速くならないという問題がある。
【０００６】本発明は、このような問題点を解決すべく
なされたもので、その技術的課題は、データ記憶装置の
処理速度の影響を受けずに高速にデータ探索を実行でき
るデータ探索方法及びそれを適用したデータ探索装置を
提供することにある。
なされたもので、その技術的課題は、データ記憶装置の
処理速度の影響を受けずに高速にデータ探索を実行でき
るデータ探索方法及びそれを適用したデータ探索装置を
提供することにある。
【０００７】
【課題を解決するための手段】本発明によれば、木構造
を用いてデータが格納されたデータベースから木構造に
対応する条件分岐を有する探索プログラムを生成する探
索プログラム生成段階と、探索プログラムに探索キーを
入力して該探索プログラムを実行し、且つ探索結果を出
力する探索結果出力段階とを有するデータ探索方法が得
られる。
を用いてデータが格納されたデータベースから木構造に
対応する条件分岐を有する探索プログラムを生成する探
索プログラム生成段階と、探索プログラムに探索キーを
入力して該探索プログラムを実行し、且つ探索結果を出
力する探索結果出力段階とを有するデータ探索方法が得
られる。
【０００８】一方、本発明によれば、木構造を用いてデ
ータが格納されたデータベースから木構造に対応する条
件分岐を有する探索プログラムを生成する探索プログラ
ム生成部と、探索プログラムを格納するプログラム記憶
装置と、探索キーの入力に従って探索プログラムを実行
してデータ探索を行う探索プログラム実行部と、探索キ
ーを入力すると共に、探索プログラム実行部によるデー
タ探索の探索結果を出力する入出力インターフェイスと
を備えたデータ探索装置が得られる。
ータが格納されたデータベースから木構造に対応する条
件分岐を有する探索プログラムを生成する探索プログラ
ム生成部と、探索プログラムを格納するプログラム記憶
装置と、探索キーの入力に従って探索プログラムを実行
してデータ探索を行う探索プログラム実行部と、探索キ
ーを入力すると共に、探索プログラム実行部によるデー
タ探索の探索結果を出力する入出力インターフェイスと
を備えたデータ探索装置が得られる。
【０００９】又、本発明によれば、上記データ探索装置
において、探索プログラム実行部によりデータ探索を行
ったときの探索キーと探索結果のデータとを格納する探
索結果記憶装置を備え、探索プログラム実行部は現行の
データ探索に際して探索結果記憶装置を参照して探索キ
ーに関する同一なものに対しては探索プログラムの実行
を省略するデータ探索装置が得られる。
において、探索プログラム実行部によりデータ探索を行
ったときの探索キーと探索結果のデータとを格納する探
索結果記憶装置を備え、探索プログラム実行部は現行の
データ探索に際して探索結果記憶装置を参照して探索キ
ーに関する同一なものに対しては探索プログラムの実行
を省略するデータ探索装置が得られる。
【００１０】
【発明の実施の形態】以下に実施例を挙げ、本発明のデ
ータ探索方法及びそれを適用したデータ探索装置につい
て、図面を参照して詳細に説明する。
ータ探索方法及びそれを適用したデータ探索装置につい
て、図面を参照して詳細に説明する。
【００１１】最初に、本発明のデータ探索方法の概要を
簡単に説明する。このデータ探索方法は、木構造を用い
てデータが格納されたデータベースから木構造に対応す
る条件分岐を有する探索プログラムを生成する探索プロ
グラム生成段階と、探索プログラムに探索キーを入力し
て該探索プログラムを実行し、且つ探索結果を出力する
探索結果出力段階とを実行するものである。
簡単に説明する。このデータ探索方法は、木構造を用い
てデータが格納されたデータベースから木構造に対応す
る条件分岐を有する探索プログラムを生成する探索プロ
グラム生成段階と、探索プログラムに探索キーを入力し
て該探索プログラムを実行し、且つ探索結果を出力する
探索結果出力段階とを実行するものである。
【００１２】このようなデータ探索方法に従えば、デー
タベースから木構造に対応する条件分岐構造をもった探
索プログラムを生成し、その探索プログラムを実行する
ことによりデータの探索を行うため、探索プログラムの
実行に際してデータ記憶装置を使用する必要が無く、こ
れによりデータ記憶装置の速度に依存しない高速なデー
タ探索が可能となる。
タベースから木構造に対応する条件分岐構造をもった探
索プログラムを生成し、その探索プログラムを実行する
ことによりデータの探索を行うため、探索プログラムの
実行に際してデータ記憶装置を使用する必要が無く、こ
れによりデータ記憶装置の速度に依存しない高速なデー
タ探索が可能となる。
【００１３】図１は、このデータ探索方法を適用した一
実施例に係るデータ探索装置の基本構成を示したもので
ある。
実施例に係るデータ探索装置の基本構成を示したもので
ある。
【００１４】このデータ探索装置は、探索対象となるデ
ータを木構造でデータベースとして格納したデータ記憶
装置１１と、木構造を用いてデータが格納されたデータ
ベースから木構造に対応する条件分岐を有する探索プロ
グラムを生成する探索プログラム生成部１２と、探索プ
ログラムを格納するプログラム記憶装置１３と、探索キ
ーの入力に従って探索プログラムを実行してデータ探索
を行う探索プログラム実行部１４と、探索キーを入力す
ると共に、探索プログラム実行部１４によるデータ探索
の探索結果を出力する入出力インターフェイス１５とを
備えて構成される。
ータを木構造でデータベースとして格納したデータ記憶
装置１１と、木構造を用いてデータが格納されたデータ
ベースから木構造に対応する条件分岐を有する探索プロ
グラムを生成する探索プログラム生成部１２と、探索プ
ログラムを格納するプログラム記憶装置１３と、探索キ
ーの入力に従って探索プログラムを実行してデータ探索
を行う探索プログラム実行部１４と、探索キーを入力す
ると共に、探索プログラム実行部１４によるデータ探索
の探索結果を出力する入出力インターフェイス１５とを
備えて構成される。
【００１５】このデータ探索装置では、データ記憶装置
１１に探索対象となるデータが木構造でデータベースと
して格納されているため、探索プログラム生成部１２が
データ記憶装置１１から木構造のデータを読み出し、生
成した探索プログラムをプログラム記憶装置１３に格納
する。探索プログラム実行部１４は、プログラム記憶装
置１３から探索プログラムを読み出し、入出力インター
フェイス１５から探索キーを入力し、探索プログラムを
実行すると共に、探索結果を入出力インターフェイス１
５に出力する。
１１に探索対象となるデータが木構造でデータベースと
して格納されているため、探索プログラム生成部１２が
データ記憶装置１１から木構造のデータを読み出し、生
成した探索プログラムをプログラム記憶装置１３に格納
する。探索プログラム実行部１４は、プログラム記憶装
置１３から探索プログラムを読み出し、入出力インター
フェイス１５から探索キーを入力し、探索プログラムを
実行すると共に、探索結果を入出力インターフェイス１
５に出力する。
【００１６】図２は、データ記憶装置１１に格納された
探索対象となるデータの多分木構造を例示したものであ
る。ここで多分木とは１個以下の親とｎ個以下の子とを
含む複数のノード２１から構成される木構造であり、各
ノード２１にはそのノードへのデータ格納条件２２とそ
の条件を満たす任意個のデータ２３とが格納されてい
る。因みに、多分木構造において親を持たないノードは
根と呼ばれる。
探索対象となるデータの多分木構造を例示したものであ
る。ここで多分木とは１個以下の親とｎ個以下の子とを
含む複数のノード２１から構成される木構造であり、各
ノード２１にはそのノードへのデータ格納条件２２とそ
の条件を満たす任意個のデータ２３とが格納されてい
る。因みに、多分木構造において親を持たないノードは
根と呼ばれる。
【００１７】上述したデータ探索装置の場合、探索プロ
グラム生成部１２が多分木構造のデータをデータ記憶装
置１１から読み出し、その多分木構造の各ノード２１を
根から再帰的に辿りながら多分木構造に対応する条件分
岐構造を持つ探索プログラムを生成し、その探索プログ
ラムをプログラム格納メモリ１３に格納する。そこで、
以降の処理は上述したように、探索プログラム実行部１
４が生成された探索プログラムをプログラム記憶装置１
３から読み出し、入出力インターフェイス１５から入力
した探索キーを探索プログラムに入力し、探索プログラ
ムを実行する。最後に探索プログラムの出力結果，即
ち、探索結果を入出力インターフェイス１５へ出力す
る。
グラム生成部１２が多分木構造のデータをデータ記憶装
置１１から読み出し、その多分木構造の各ノード２１を
根から再帰的に辿りながら多分木構造に対応する条件分
岐構造を持つ探索プログラムを生成し、その探索プログ
ラムをプログラム格納メモリ１３に格納する。そこで、
以降の処理は上述したように、探索プログラム実行部１
４が生成された探索プログラムをプログラム記憶装置１
３から読み出し、入出力インターフェイス１５から入力
した探索キーを探索プログラムに入力し、探索プログラ
ムを実行する。最後に探索プログラムの出力結果，即
ち、探索結果を入出力インターフェイス１５へ出力す
る。
【００１８】図３は、探索プログラム生成部１２におけ
る多分木構造のデータに対応する条件分岐構造を持つ探
索プログラムの生成処理を示したフローチャートであ
る。
る多分木構造のデータに対応する条件分岐構造を持つ探
索プログラムの生成処理を示したフローチャートであ
る。
【００１９】ここでの本手続きは再帰的手続きであり、
最初に多分木の根のノードに対して本手続きを呼び出し
てノードのデータ格納条件を調べ、「探索キーがノード
のデータ格納条件を満たすデータに対応するならば次の
命令文を実行せよ」という命令文を生成（ステップＳ３
１）する。
最初に多分木の根のノードに対して本手続きを呼び出し
てノードのデータ格納条件を調べ、「探索キーがノード
のデータ格納条件を満たすデータに対応するならば次の
命令文を実行せよ」という命令文を生成（ステップＳ３
１）する。
【００２０】次に、ノードにデータが格納されているか
否かを判定（ステップＳ３２）し、データが格納されて
いれば、そのすべてのデータを出力する命令文又は命令
文の列を生成（ステップＳ３３）するが、データが格納
されていなければ、何も実行しない命令文を生成（ステ
ップＳ３４）する。
否かを判定（ステップＳ３２）し、データが格納されて
いれば、そのすべてのデータを出力する命令文又は命令
文の列を生成（ステップＳ３３）するが、データが格納
されていなければ、何も実行しない命令文を生成（ステ
ップＳ３４）する。
【００２１】引き続き、そのノードの子のノードがある
か否かを判定（ステップＳ３５）し、子のノードがなけ
れば本手続きを終了（ステップＳ３９）するが、子のノ
ードがあれば、そのうちの一つを選択（ステップＳ３
６）し、そのノードに対して本手続きを再帰的に呼び出
す（ステップＳ３７）処理を行う。
か否かを判定（ステップＳ３５）し、子のノードがなけ
れば本手続きを終了（ステップＳ３９）するが、子のノ
ードがあれば、そのうちの一つを選択（ステップＳ３
６）し、そのノードに対して本手続きを再帰的に呼び出
す（ステップＳ３７）処理を行う。
【００２２】更に、選択されていない子のノードがある
か否かを判定（ステップＳ３８）し、なければ本手続き
を終了（ステップＳ３９）するが、あれば子のノードの
一つを選択（ステップＳ３６）する処理にリターンし、
ステップＳ３６〜ステップＳ３８の処理を繰り返すこと
で現在のノードのすべての子のノードについて本手続き
を再帰的に呼び出す。
か否かを判定（ステップＳ３８）し、なければ本手続き
を終了（ステップＳ３９）するが、あれば子のノードの
一つを選択（ステップＳ３６）する処理にリターンし、
ステップＳ３６〜ステップＳ３８の処理を繰り返すこと
で現在のノードのすべての子のノードについて本手続き
を再帰的に呼び出す。
【００２３】このようにして探索対象となるデータから
探索プログラムを生成し、その探索プログラムを直接実
行してデータ探索を行えば、データ探索時にデータ記憶
装置１１を使用する必要が無く、このためにデータ記憶
装置１１の処理速度の影響を受けずに高速なデータ探索
が具現される。
探索プログラムを生成し、その探索プログラムを直接実
行してデータ探索を行えば、データ探索時にデータ記憶
装置１１を使用する必要が無く、このためにデータ記憶
装置１１の処理速度の影響を受けずに高速なデータ探索
が具現される。
【００２４】ところで、図１に示したデータ探索装置を
具体的に構築すれば、図４のような細部構成となる。
具体的に構築すれば、図４のような細部構成となる。
【００２５】ここでは、先のデータ記憶装置１１にはデ
ータＲＡＭ４１が用いられ、プログラム記憶装置１３に
は探索プログラム・オブジェクトファイル４３が用いら
れ、入出力インターフェイス１５には入出力端末４５が
用いられている。又、探索プログラム生成部１２を具体
化した探索プログラム生成部４２は、探索プログラム生
成プログラム４２１，探索プログラム・ソースファイル
４２２，及びコンパイラ４２３から構成されており、探
索プログラム実行部１４を具体化した探索プログラム実
行部４４は、プログラム・ローダ４４１及びプログラム
ＲＡＭ４４２から構成されている。
ータＲＡＭ４１が用いられ、プログラム記憶装置１３に
は探索プログラム・オブジェクトファイル４３が用いら
れ、入出力インターフェイス１５には入出力端末４５が
用いられている。又、探索プログラム生成部１２を具体
化した探索プログラム生成部４２は、探索プログラム生
成プログラム４２１，探索プログラム・ソースファイル
４２２，及びコンパイラ４２３から構成されており、探
索プログラム実行部１４を具体化した探索プログラム実
行部４４は、プログラム・ローダ４４１及びプログラム
ＲＡＭ４４２から構成されている。
【００２６】そこで、以下はこのデータ探索装置の動作
について詳細に説明する。但し、ここでは探索対象とな
るデータが１次元の線分であり、探索キーとして与えら
れた１点を含む線分をすべて探索するものとする。又、
図５は探索対象となる線分データＡ〜Ｇを例示したもの
であり、図６は図５で示した探索対象となる線分データ
を２分木構造で表現したものである。
について詳細に説明する。但し、ここでは探索対象とな
るデータが１次元の線分であり、探索キーとして与えら
れた１点を含む線分をすべて探索するものとする。又、
図５は探索対象となる線分データＡ〜Ｇを例示したもの
であり、図６は図５で示した探索対象となる線分データ
を２分木構造で表現したものである。
【００２７】先ず図６を参照すると、２分木構造の各ノ
ードのデータ格納条件として１次元の区間［ｉ，ｊ］が
割り当てられており、各ノードの左の子のノードのデー
タ格納条件には区間［ｉ，（ｉ＋ｊ）／２］，右の子の
ノードのデータ格納条件には区間［（ｉ＋ｊ）／２＋
１，ｊ］が割り当てられている。ある線分に区間［ｉ，
ｊ］が含まれる場合、具体的にはある線分の両端の座標
ｘ１，ｘ２（但し、ｘ１≦ｘ２）がｘ１≦ｉ，且つｊ≦
ｘ２である場合、その線分のデータは区間［ｉ，ｊ］を
格納条件として持つノードに格納される。この２分木で
表現された線分データがデータＲＡＭ４１に格納されて
いるものとする。
ードのデータ格納条件として１次元の区間［ｉ，ｊ］が
割り当てられており、各ノードの左の子のノードのデー
タ格納条件には区間［ｉ，（ｉ＋ｊ）／２］，右の子の
ノードのデータ格納条件には区間［（ｉ＋ｊ）／２＋
１，ｊ］が割り当てられている。ある線分に区間［ｉ，
ｊ］が含まれる場合、具体的にはある線分の両端の座標
ｘ１，ｘ２（但し、ｘ１≦ｘ２）がｘ１≦ｉ，且つｊ≦
ｘ２である場合、その線分のデータは区間［ｉ，ｊ］を
格納条件として持つノードに格納される。この２分木で
表現された線分データがデータＲＡＭ４１に格納されて
いるものとする。
【００２８】又、図４を参照すると、探索プログラム生
成プログラム４２１はデータＲＡＭ４１から２分木のデ
ータを読み出し、２分木の根から各ノードを再帰的に辿
り、２分木の構造に対応する条件分岐の構造を有する探
索プログラム・ソースファイル４２２を生成する。
成プログラム４２１はデータＲＡＭ４１から２分木のデ
ータを読み出し、２分木の根から各ノードを再帰的に辿
り、２分木の構造に対応する条件分岐の構造を有する探
索プログラム・ソースファイル４２２を生成する。
【００２９】図７は、２分木構造のノードから探索プロ
グラムを生成する再帰的手続きの動作処理を示したフロ
ーチャートである。
グラムを生成する再帰的手続きの動作処理を示したフロ
ーチャートである。
【００３０】ここでの本手続きは最初に２分木の根のノ
ードに対して呼び出される。先ずノードのデータ格納条
件を［ｉ，ｊ］とすると、「探索キーの点の座標がｉ以
上ｊ以下ならば次の命令文を実行せよ」という命令文を
生成（ステップＳ７１）する。次に、ノードにデータが
格納されているか否かを判定（ステップＳ７２）し、ノ
ードにデータが格納されていればそのすべての線分デー
タを出力する命令文又は命令文の列を出力（ステップＳ
７３）するが、ノードにデータが格納されていなけれ
ば、何も実行しない命令文を生成（ステップＳ７４）す
る。
ードに対して呼び出される。先ずノードのデータ格納条
件を［ｉ，ｊ］とすると、「探索キーの点の座標がｉ以
上ｊ以下ならば次の命令文を実行せよ」という命令文を
生成（ステップＳ７１）する。次に、ノードにデータが
格納されているか否かを判定（ステップＳ７２）し、ノ
ードにデータが格納されていればそのすべての線分デー
タを出力する命令文又は命令文の列を出力（ステップＳ
７３）するが、ノードにデータが格納されていなけれ
ば、何も実行しない命令文を生成（ステップＳ７４）す
る。
【００３１】次に、ノードに左の子のノードがあるか否
かを判定（ステップＳ７５）し、あればその左の子のノ
ードに対して本手続きを再帰的に呼び出す（ステップＳ
７６）処理を行ってから、左の子のノードが無い場合と
同様に、引き続いてノードに右の子のノードがあるか否
かを判定（ステップＳ７７）し、あればその右の子のノ
ードに対して本手続きを再帰的に呼び出す（ステップＳ
７８）処理を行ってから、右の子のノードが無い場合と
同様に、一連の処理をリターン（ステップＳ７９）す
る。
かを判定（ステップＳ７５）し、あればその左の子のノ
ードに対して本手続きを再帰的に呼び出す（ステップＳ
７６）処理を行ってから、左の子のノードが無い場合と
同様に、引き続いてノードに右の子のノードがあるか否
かを判定（ステップＳ７７）し、あればその右の子のノ
ードに対して本手続きを再帰的に呼び出す（ステップＳ
７８）処理を行ってから、右の子のノードが無い場合と
同様に、一連の処理をリターン（ステップＳ７９）す
る。
【００３２】図４に示すデータ探索装置では、探索プロ
グラム生成プログラム４２１から生成された探索プログ
ラム・ソースファイル４２２がコンパイラ４２３により
コンパイルされ、探索プログラム・オブジェクトファイ
ル４３が生成される。プログラム・ローダ４４１は探索
プログラム・オブジェクトファイル４３をプログラムＲ
ＡＭ４４２に格納した後、探索プログラムを起動して入
出力端末４５から探索キー，即ち、点の座標のデータを
入力して探索プログラムに入力する。探索プログラムの
実行結果，即ち、探索された結果である線分データは入
出力端末３５へ出力される。
グラム生成プログラム４２１から生成された探索プログ
ラム・ソースファイル４２２がコンパイラ４２３により
コンパイルされ、探索プログラム・オブジェクトファイ
ル４３が生成される。プログラム・ローダ４４１は探索
プログラム・オブジェクトファイル４３をプログラムＲ
ＡＭ４４２に格納した後、探索プログラムを起動して入
出力端末４５から探索キー，即ち、点の座標のデータを
入力して探索プログラムに入力する。探索プログラムの
実行結果，即ち、探索された結果である線分データは入
出力端末３５へ出力される。
【００３３】図８は、本発明の他の実施例に係るデータ
探索装置の基本構成を示したブロック図である。
探索装置の基本構成を示したブロック図である。
【００３４】このデータ探索装置は、図１に示した一実
施例のものと比べ、同等な機能のデータ記憶装置８１，
探索プログラム生成部８２，プログラム記憶装置８３，
探索プログラム実行部８４，及び入出力インターフェイ
ス８５を備える他、探索プログラム実行部８４により以
前にデータ探索を行ったときの探索キーと探索結果のデ
ータとを格納する探索結果記憶装置８６を備えて構成さ
れる。
施例のものと比べ、同等な機能のデータ記憶装置８１，
探索プログラム生成部８２，プログラム記憶装置８３，
探索プログラム実行部８４，及び入出力インターフェイ
ス８５を備える他、探索プログラム実行部８４により以
前にデータ探索を行ったときの探索キーと探索結果のデ
ータとを格納する探索結果記憶装置８６を備えて構成さ
れる。
【００３５】このデータ探索装置においても、データ記
憶装置８１には探索対象となるデータが木構造で格納さ
れているため、探索プログラム生成部８２がデータ記憶
装置８１から木構造のデータを読み出し、生成した探索
プログラムをプログラム記憶装置８３に格納する。探索
プログラム実行部８４は、入出力インターフェイス８５
から探索キーを入力し、その探索キーが探索結果記憶装
置８６に存在するか否かを検索する。この結果、存在し
ていれば対応する探索結果データを探索結果記憶装置８
６から読み出して入出力インターフェイス８５に出力す
ると共に、探索プログラムの実行を省略するが、存在し
ていなければプログラム記憶装置８３から探索プログラ
ムを読み出して実行し、探索結果を入出力インターフェ
イス８５に出力すると共に、その探索キーと探索結果の
データとを探索結果記憶装置８６に格納する。
憶装置８１には探索対象となるデータが木構造で格納さ
れているため、探索プログラム生成部８２がデータ記憶
装置８１から木構造のデータを読み出し、生成した探索
プログラムをプログラム記憶装置８３に格納する。探索
プログラム実行部８４は、入出力インターフェイス８５
から探索キーを入力し、その探索キーが探索結果記憶装
置８６に存在するか否かを検索する。この結果、存在し
ていれば対応する探索結果データを探索結果記憶装置８
６から読み出して入出力インターフェイス８５に出力す
ると共に、探索プログラムの実行を省略するが、存在し
ていなければプログラム記憶装置８３から探索プログラ
ムを読み出して実行し、探索結果を入出力インターフェ
イス８５に出力すると共に、その探索キーと探索結果の
データとを探索結果記憶装置８６に格納する。
【００３６】即ち、このデータ探索装置の場合、先の一
実施例のものと同様な働きを有する他、同一な探索キー
に対しては探索プログラムの実行を省略できる機能が構
築されているため、一層高速な探索を行うことができ
る。
実施例のものと同様な働きを有する他、同一な探索キー
に対しては探索プログラムの実行を省略できる機能が構
築されているため、一層高速な探索を行うことができ
る。
【００３７】
【発明の効果】以上に述べた通り、本発明のデータ探索
方法及びそれを適用したデータ探索装置によれば、木構
造を用いてデータが格納されたデータベースから探索プ
ログラムを生成し、その探索プログラムを直接実行する
ため、データ探索時にデータ記憶装置を使用する必要が
無く、データ記憶装置の処理速度の影響を受けずに高速
にデータ探索を実行できるようになる。又、データ探索
装置では、更に探索プログラム実行部により以前にデー
タ探索を行ったときの探索キーと探索結果のデータとを
格納する探索結果記憶装置を備え、探索プログラム実行
部による探索プログラムの実行に際して探索結果記憶装
置を参照して同一な探索キーに対しては探索プログラム
の実行を省略できるようにしているため、一層高速な探
索を行うことができるようになる。
方法及びそれを適用したデータ探索装置によれば、木構
造を用いてデータが格納されたデータベースから探索プ
ログラムを生成し、その探索プログラムを直接実行する
ため、データ探索時にデータ記憶装置を使用する必要が
無く、データ記憶装置の処理速度の影響を受けずに高速
にデータ探索を実行できるようになる。又、データ探索
装置では、更に探索プログラム実行部により以前にデー
タ探索を行ったときの探索キーと探索結果のデータとを
格納する探索結果記憶装置を備え、探索プログラム実行
部による探索プログラムの実行に際して探索結果記憶装
置を参照して同一な探索キーに対しては探索プログラム
の実行を省略できるようにしているため、一層高速な探
索を行うことができるようになる。
【図１】本発明のデータ探索方法を適用した一実施例に
係るデータ探索装置の基本構成を示したブロック図であ
る。
係るデータ探索装置の基本構成を示したブロック図であ
る。
【図２】図１に示すデータ探索装置のデータ記憶装置に
格納されるデータの多分木構造を例示したものである。
格納されるデータの多分木構造を例示したものである。
【図３】図１に示すデータ探索装置の探索プログラム生
成部における多分木構造のデータに対応する条件分岐構
造を持つ探索プログラムの生成処理を示したフローチャ
ートである。
成部における多分木構造のデータに対応する条件分岐構
造を持つ探索プログラムの生成処理を示したフローチャ
ートである。
【図４】図１に示したデータ探索装置を具体的に構築し
た細部構成を示したブロック図である。
た細部構成を示したブロック図である。
【図５】図４に示すデータ探索装置において探索対象と
なる線分データを例示したものである。
なる線分データを例示したものである。
【図６】図５に示す線分データを２分木構造で表現した
ものである。
ものである。
【図７】図４に示すデータ探索装置において図６に示す
２分木構造のノードから探索プログラムを生成する再帰
的手続きの動作処理を示したフローチャートである。
２分木構造のノードから探索プログラムを生成する再帰
的手続きの動作処理を示したフローチャートである。
【図８】本発明の他の実施例に係るデータ探索装置の基
本構成を示したブロック図である。
本構成を示したブロック図である。
【図９】従来の高速データ探索装置の基本構成を示した
ブロック図である。
ブロック図である。
１１，８１ データ記憶装置 １２，４２，８２ 探索プログラム生成部 １３，８３ プログラム記憶装置 １４，４４，８４ 探索プログラム実行部 １５，８５，９１ 入出力インターフェイス ２１ ノード ２２ データ格納条件 ２３ データ ４１ データＲＡＭ ４３ 探索プログラム・オブジェクトファイル ４５ 入出力端末 ８６ 探索結果記憶装置 ９２ 探索範囲決定部 ９３ データ格納用メモリ ９４ 探索範囲記憶用レジスタ ９５ 探索処理部 ４２１ 探索プログラム生成プログラム ４２２ 探索プログラム・ソースファイル ４２３ コンパイラ ４４１ プログラム・ローダ ４４２ プログラムＲＡＭ
Claims (3)
- 【請求項１】 木構造を用いてデータが格納されたデー
タベースから木構造に対応する条件分岐を有する探索プ
ログラムを生成する探索プログラム生成段階と、前記探
索プログラムに探索キーを入力して該探索プログラムを
実行し、且つ探索結果を出力する探索結果出力段階とを
有することを特徴とするデータ探索方法。 - 【請求項２】 木構造を用いてデータが格納されたデー
タベースから木構造に対応する条件分岐を有する探索プ
ログラムを生成する探索プログラム生成部と、前記探索
プログラムを格納するプログラム記憶装置と、探索キー
の入力に従って前記探索プログラムを実行してデータ探
索を行う探索プログラム実行部と、前記探索キーを入力
すると共に、前記探索プログラム実行部による前記デー
タ探索の探索結果を出力する入出力インターフェイスと
を備えたことを特徴とするデータ探索装置。 - 【請求項３】 請求項２記載のデータ探索装置におい
て、前記探索プログラム実行部により前記データ探索を
行ったときの前記探索キーと前記探索結果のデータとを
格納する探索結果記憶装置を備え、前記探索プログラム
実行部は現行のデータ探索に際して前記探索結果記憶装
置を参照して前記探索キーに関する同一なものに対して
は前記探索プログラムの実行を省略することを特徴とす
るデータ探索装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8217547A JPH1063675A (ja) | 1996-08-19 | 1996-08-19 | データ探索方法及びそれを適用したデータ探索装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8217547A JPH1063675A (ja) | 1996-08-19 | 1996-08-19 | データ探索方法及びそれを適用したデータ探索装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH1063675A true JPH1063675A (ja) | 1998-03-06 |
Family
ID=16705976
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8217547A Pending JPH1063675A (ja) | 1996-08-19 | 1996-08-19 | データ探索方法及びそれを適用したデータ探索装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH1063675A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6742018B1 (en) * | 1999-01-08 | 2004-05-25 | International Business Machines Corporation | System and method for storing and retrieving data by keywords converted into divided long integers |
| JP2019144705A (ja) * | 2018-02-16 | 2019-08-29 | 富士通株式会社 | バス配線探索プログラム、バス配線探索方法および情報処理装置 |
-
1996
- 1996-08-19 JP JP8217547A patent/JPH1063675A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6742018B1 (en) * | 1999-01-08 | 2004-05-25 | International Business Machines Corporation | System and method for storing and retrieving data by keywords converted into divided long integers |
| JP2019144705A (ja) * | 2018-02-16 | 2019-08-29 | 富士通株式会社 | バス配線探索プログラム、バス配線探索方法および情報処理装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH01188951A (ja) | データフロープログラムの実行制御方式 | |
| JPH02264329A (ja) | プログラム自動生成装置 | |
| JP2788850B2 (ja) | 最適メニュー問い合わせ方式及び階層的メニュー問い合わせによる構造データの編集方式 | |
| EP0369699A2 (en) | Updating pattern-matching networks | |
| JPH06290086A (ja) | 構造データ処理装置 | |
| JP3741544B2 (ja) | 順序回路の状態探索方法および装置並びに状態探索プログラムを記録した記録媒体 | |
| CN112506503A (zh) | 一种编程方法、装置、终端设备及存储介质 | |
| JPH1063675A (ja) | データ探索方法及びそれを適用したデータ探索装置 | |
| JP2002527816A (ja) | プログラム最適化装置および方法 | |
| US5587918A (en) | Circuit pattern comparison apparatus | |
| JPH06274328A (ja) | 複数の処理モジュールからなるプログラムの実行方法 | |
| JP3602231B2 (ja) | テストパターン作成装置 | |
| US20240202522A1 (en) | Device and method for generating deep learning model graph and abstract syntax tree for integrated compiler | |
| JP3502440B2 (ja) | 高速データ検索装置および高速データ検索方法 | |
| JP2722684B2 (ja) | ファイルシステムの検索装置 | |
| JP2616451B2 (ja) | データチェック装置 | |
| JP2714015B2 (ja) | 論理回路合成装置 | |
| JP2932987B2 (ja) | 計算機システムの自動試験装置 | |
| JPS6015772A (ja) | ル−プ内配列処理ベクトル化処理方式 | |
| JP3111081B2 (ja) | データ検索装置 | |
| JP2001075831A (ja) | プログラム処理装置、ｉｃ試験システム、プログラム処理方法及び記憶媒体 | |
| JP2835082B2 (ja) | 論理回路合成装置 | |
| JPH06332719A (ja) | コンパイラコード発生装置 | |
| JP3018579B2 (ja) | 名前検索処理装置 | |
| JP2626549B2 (ja) | 水平型マイクロプログラム最適化方法およびその装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 19990526 |