JPS61294545A - 探索装置 - Google Patents

探索装置

Info

Publication number
JPS61294545A
JPS61294545A JP61139403A JP13940386A JPS61294545A JP S61294545 A JPS61294545 A JP S61294545A JP 61139403 A JP61139403 A JP 61139403A JP 13940386 A JP13940386 A JP 13940386A JP S61294545 A JPS61294545 A JP S61294545A
Authority
JP
Japan
Prior art keywords
random access
access memory
node
bit
bits
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
Application number
JP61139403A
Other languages
English (en)
Inventor
ニコラス　ピーター　ホルト
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.)
ICL PLC
Original Assignee
ICL PLC
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 ICL PLC filed Critical ICL PLC
Publication of JPS61294545A publication Critical patent/JPS61294545A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/44—Arrangements for executing specific programs
    • G06F9/448—Execution paradigms, e.g. implementations of programming paradigms
    • G06F9/4494—Execution paradigms, e.g. implementations of programming paradigms data driven
    • 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 この発明は所定基準を満足するアイテムをアイテムの集
合体の中で突き止めるための探索装置に関する。
この発明は、特に、従来のフォノ・ノイマン型アーキテ
クチャの場合とは異なり、命令が順次実行されるのでは
なく、命令の実行の準備ができた後、例えば、全ての必
要なオペランドが利用できるようになった時にいつでも
実行することができる並列データ処理システムに適応す
ることができるが、これのみに限定されるものではない
。このようなシステムでは、任意の与えられた瞬間にい
くつかの命令が実行の準備できた状態に有り得るので、
これらの命令を迅速に突き止める何らかの方法を提供す
ることは必要である。このことは、実行の準備のできた
これらの命令を示す標識のリストを維持することによっ
てなすことができよう。しかしながら、このリストを維
持するに必要な記憶装置のコスト及び記憶装置のアクセ
スの点でかなりの費用がかかることを意味する。又別の
方法は表示フラグで実行に適したこれらの命令をマーク
することであろう。問題は記憶装置内の全ての命令の中
でそれらのフラッグがセットされているものを突き止め
ることである。これは記憶装置の各記憶場所を順番に走
査することにエリなし得るであろうが、これにはかなり
長い時間がかかる。又この代わりに、フラグは内容をア
ドレス可能なメモリに記憶できるが、これらのメモリは
非常に高価である。
同様な問題は並列データ処理装置内での記憶装置の割り
当ての場合に起こる。一般的には、記憶装置は、必要に
応じて割り当てられると共に必要がなくなった時は木状
のセルよりなるプールに開放される１組のセルとして組
織化される。自由なセルを突き止めるタスクは実行可能
な命令を見つけるタスク−に厳密に類似している。
この発明の目的は上述の欠点を蒙らない改良された探索
装置を提供することである。
発明の概要 この発明によれば、 （ａ）根源節点と複数の端末節点を有する複数の接続さ
れた節点を有し、この各節点の従属節点のうちの任意の
１つが所定状態にセットされた場合にその節点が所定状
態にセットされるようにした木の構造の表現を維持する
ための手段（２０）、及び （ｂ）前記根源節点から始めて所定状態にセットされて
いるすべての一連の節点を通り所定状態にある端末節点
に到達するまで前記水を通る通路を追跡するための手段
（２１，２４）を備えていることを特徴とする探索装置
が提供される。
この発明の１つの実施例を添付図面に関し例として次に
記載する。
発明の詳細な説明 第１図を見ると、この図は４つのレベルに配列された円
に工って表される複数の節点よりなる木の構造を示す。
最高のレベル（レベルＯ）は根源節点と呼ばれる単一の
節点を有し、最低のレベル（レベル３）は端末節点又は
端末葉と呼ばれる６４個の節点を有している。各非端末
節点（即ち端末葉身外の他の節点）は木の次の最低レベ
ルにある４つの従属節点に接続されている。即ち、この
木は４という分岐係数を有している。
この６４個の端末葉は、それぞれ６４個のアイテムに対
応し、そして、これらのアイテムが所定の基準を満足す
るかどうかを示すようにセットされる。例えば、端末葉
は記憶装置内の命令に対応することができ、そして、そ
の命令が実行の準備ができているかどうかを示すように
セットされる。あるいは又、端末葉はデータの記憶セル
に対応することができ、そしてこのデータの記憶セルが
自由かどうかを示すようにセットされる。
（根源節点以外の）各節点はｙ４Ｊ１図に示したように
、数Ｘ％　　ｙを割り当てられている。
見られるように、レベル１０４つの節点は数１．０ない
し１．３を割り当てられており、節点１．０に付属する
４つの節点は数４．０ないし４．３を割り当てられてい
る。以下同じ。一般的に、節Ｑｘｓｙに付属する４つの
節点は数４ｘ＋ｙ、Ｏないし４ｘ＋ｙ、３を割り当てら
れている。
非端末節点はその従属節点又は従属葉の任意の１つがセ
ットされる場合にセットされる。
例えば、もしも端末葉２１．２がセットされると、節点
５．１と１．１及び又根源節点が設定されなければなら
ない。セットされた端末葉の節点は、根源節点から始め
てセットされたその従属節点のうちの１つまで各節点を
通り端末葉の節点に到達するまで木を通る通路を追跡す
ることにより迅速に突き止めることができるということ
がわかる。このような通路は第１図で太線で示されてい
る。アイテムの状態が変わる時はいつも、木の対応する
端末集を更新する必要がある。例えば、実行される命令
が得られると、対応する端末葉はセットされ、逆に、命
令が実行されてしまうと、対応する端末葉はその元の未
セツト状態にリセットされる。端未来が更新される時は
いつも、変化は次の規則に従って木のエリ高いレベルへ
伝ばんされなければならない、（１）する節点の従属節
点が全て未セットであって１つが丁度設定された場合に
その節点はセットされる。
（ｉｉ）もしもある節点の従属節点のうちの１つを除く
全てが未セットで１つが丁度リセットされた場合にその
節点はリセットされる。
例えば、第１図の端末葉２２．１がセットされると、次
のレベルまで変化が伝わって、レベル２の節点５．２を
セットしなければならない。節点２１．２の以前のセッ
トの結果として、レベル１の関連する節点１．１は既に
セットされているので、更に変化を伝えることは必要で
はない。
次に第２図を見ると、この図は上述の木の構造を利用す
る探索装置を示す。この木の構造は、各々４ビツトの位
置（０ないし３）を有する３２個の記憶場所（０ないし
３１）を備えたランダム・アクセス・メモリ（ＲＡＭ）
２０内に記憶されている。この木の構造の各節点は、根
源節点を除き、ＲＡＭの１ビツトにより表される。特に
、第１図の各節点ｘ１ｙはＲＡＭ２０の記憶場所Ｘのビ
ット桁ｙにより表される。したがって、レベル１０４つ
の節点はＲＡＭ２０の記憶場所１０４ビツトにより表現
され、レベル２の１６個の節点は、記憶場所４ないし７
に工す表現され、そして、レベル３の６４個の端末葉は
記憶場所１６ないし３１により表現される。ＲＡＭ２０
の他の記憶場所は使用されない。同、記憶場所Ｘのビッ
トｙに対応する節点は、記憶場所４ｘ＋ｙの４つのビッ
トに記憶される４つの従属節点（又は葉）を有している
。
ＲＡＭ２１；Ｊ８ビットのアドレス・レジスタ２１０５
個の最下位のビットによりアドレスされる。このレジス
タは自体を値１にリセットするリセット制御部、入力通
路２２から並列に自体に格納するロード制御部、及び、
自体を左又は右にシフトさせるシフト・レフト及びシフ
ト・ライト制御部を有している。
ＲＡＭ２０のデータ出力は４ビツトのデータ・レジスタ
２３に供給される。それは又優先順位エンコーダ２４に
供給される。この優先順位エンコーダ２４はデータ出力
の最初の（即ち最も左側の）セットされたビット桁を表
す２ビツト優先順位符号を発生する。そのデータ・ビッ
トのいずれもがセットされない場合は優先１噴位エンコ
ーダ２４は信号ＮＢＳを発生する。その２ビツトの優先
順位符号はアドレス・レジスタ２１０２つの最下位（即
ち、最も右側）のビット桁に挿入することができる。又
はその代わりに、これらの２つの最下位のビット桁の内
容は２ビツトの制御レジスタ２５に格納することができ
る。
ＲＡＭ２０へのデータ入力は、論理回路２６から来るが
、この論理回路はデータ・レジスタ２３に接続されて、
制御レジスタ２５の内容及び制御信号ＳＥＴにより制御
される。
次に第３図を見ると、この図は論理回路２６を詳細に示
す。この回路は４つの選択回路３０を有し、この選択回
路の出力はＲＡＭ２０のデータ入力点に接続されている
。選択回路３０の第１の入力はデータ・レジスタ２３か
らデータを受けるように接続されている。他の入力全て
はＳＥＴ信号を受ける。論理回路２６は、又、制御レジ
スタ２５の内容をデコードして４本の線３２０１つに信
号を発生するためのデコーダ３１を有している。
これに工す、４個の回路３０の１つはその第２の入力を
選択し、他の３つの選択回路３゜は全てそれらの第１の
入力を選択する。
したがって、論理回路２６はデータ・レジスタ２３を介
してＲＡＭ２０のデータ出力を受けるということがわか
る。論理回路２６は、次に、制御レジスタ２５にエリ明
示されたビットを信号ＳＥＴにより明示された値にセッ
トすることによりデータを更新するが、他のビットは変
化されないままである。次に、その更新されたデータｆ
ｌＲＡＭ２０の中に書き戻される。論理回路２６への４
個の入力データ・ビットはＯＲゲート３３で組み合わさ
れて、信号ＢＷＳを発生する。この信号はデータ・ビッ
トの少なくとも１つが論理回路２６による更新前に既に
設定されていたということを示す信号である。その４つ
の出力ビットはＯＲゲート３４で組み合わされて、その
データ・ビットの少なくとも１つが更新後セットされた
ということを示す信号ＲＡＳを発生する。信号ＢＷＳと
ＢＡＳは非等価ゲート３５で組み合わされて信号Ｐ　Ｒ
ＯＰ　ＡＧ　ＡＴ　Ｅを発生する。
この信号は、上に特定した規則に従って、更新が木の次
のより高いレベルへ伝ばんされなければならない時はい
つも真であるということがわかる。
セットされた端末葉を見つけるためにこの探索装置を動
作する仕方は次の通りである。
（１）最初に、レベル１０４個の節点を保持するＲＡＭ
２０内の場所をアドレス・レジスタ２１が示すようにア
ドレス・レジスタ２１は値１にセットされる。
（２）　ＲＡ　Ｍ　２　Ｑは次にアドレス・レジスタ２
１により定められた記憶場所においてアクセスされる。
（３１ＲＡＭ２０からのデータ出力はデータ・レジスタ
２３に格納される。
（４）ＲＡＭ２０からのデータ出力は、ＲＡＭ出力の最
初にセットされたビット桁を示す符号を発生する工うに
、優先順位エンコーダ２４により処理される。それらの
ビットのいずれもがセットされてない場合、信号ＮＢＳ
が発生される。この信号は、端末葉のどれもがセットさ
れていないので探索が終了されたということを意味する
。
（５）アドレス・レジスタ２１は２個のビット桁だけ左
ヘシフトされ、優先順位エンコーダ２４からの符号はア
ドレス・レジスタ２１の最下位（即ち右側）端に挿入さ
れる。これにエリ、アドレス（ｘ）［４倍され、優先順
位エンコーダ２４の出力（ｙ）に加えられて、ビットＸ
、ｙＫ工り表される節点の４つの従属節点を含む記憶場
所のアドレス４　ｘ＋ｙを形成するようになる。
（６）もしもアドレス・レジスタ２１の内容が今６４！
り大きいか又は６４に等しい場合、探索は終了される。
次に、その最下位の６個のビットは、（範囲Ｏないし６
３の）セットされた端末葉との同一性を示し、そして、
探索装置の出力を表す。データ・レジスタ２３の内容は
次のより高いレベルにある同一の節点に従属する任意の
他のセットされた端末葉が存在する。
か否かを示す。
一方、アドレス・レジスタ２１の内容が６４より少い場
合、上記のシーケンスはステップ（２）から繰り返され
る。
同、ステップ（４）はＲＡＭ２０の現在アドレスされて
いる記憶場所からセットされた節点を選択するというこ
とがわかる。次に、ステップ（５）は、選択された節点
に従属する４個の節点を含む場所を指摘するようにアド
レス・レジスタ２１を更新する。このサイクルは繰り返
されて、各サイクルで木の次の低いレベルに進み、つい
に端末葉の節点が選択される。したがって、この方法は
根源節点からセットされた端末葉へ木を通る通路を追跡
する。
木の構造を更新する方法を次に記載する。
（１）　（＠囲Ｏないし６３の）更新されるべき端末集
の節点と同一のものには６４が加えられ、その結果がア
ドレス・レジスタ２１に格納される。
（２）アドレス・レジスタ２１は次に２個のビット桁だ
け右にシフトされ、０をアドレス・レジスタ２１の最上
位（即ち左端）端に挿入する。最下位の２個のビット桁
の元の内容は制御レジスタ２５に格納される。これによ
り、アドレス・レジスタ２１の内容は４で割られて剰余
は制御レジスタ２５に置かれる。
（３）アドレス・レジスタ２１により定められたＲＡＭ
２０の記憶場所は次にアクセスされる。
（４）ＲＡＭ２０からの出力データはデータ・レジスタ
２３に格納される。
（５）データ・レジスタ２３からのデータは次に論理回
路２゛６により処理されて、ＳＥＴ制御信号の状態に従
って、制御レジスタ２５の内容により示されるビッート
をセット又はクリアする。データの他のビットは変化さ
れないままである。
（６）論理回路２６の出力は次にアドレス・レジスタ２
１によりアドレスされるＲＡＭ２０の記憶場所へ書き戻
されて前の内容の上に書き込まれる。
（７）もしも信号ＰＲＯＰＡＧＡＴＥが真の場合、上記
のシーケンスはステップ（２）から繰り返される。そう
でない場合は方法は終了される。
更新段階はまず明示された葉の節点を更新するというこ
とがわかる。次に、更新段階は根源節点の方へ木を登る
通路を追跡して、更新される必要のない節７へ（即ち、
ＰＲＯＰＡＧＡＴＥが真、でないもの）に到達する。
同、上記の装置は木の構造の適当な選択により任意所望
の数のアイテムを収容するように容易に拡張することが
できるということが理解されよう。一般的に、木の分岐
係数が（簡単化のために２の累乗に等しいと仮定された
）ｂであり、木の深さく即ち、木の枝の桁数）がｄであ
るとすると、Ｎ＝ｂｄ　の端末集が存在する。このよう
な木は各々がｂビットを有する２Ｎ／ｂ個の記憶場所を
持つＲＡＭ内に保持することができ、レベルｉにおける
節点は記憶場所ｂ１−１ないし２ｂｉ−１−１に記憶さ
れる。この一般的な場合に、制御レジスタ２５はｌｏｇ
２ｂ個のビットを有しており、アドレス・レジスタ２１
は探索過程のステップ（５）及び更新過程のステップ（
２）においてこの数のビット桁だけシフトされる。
伺、一般的に、セットされた端末葉を突き止めるに必要
なＲＡＭ２０に対するアクセスの数は１ｏｇｂＮ　　に
なり、その最も近い完全数に四捨五入され、これにより
同時にｂ個のセットされた端末葉まで突き止めることが
できるということがわかる。
【図面の簡単な説明】
第１図は木の構造を表す図であり、 第２図は本発明による探索装置のブロック線図であり、 第３図はその探索装置の一部を更に詳細に示す論理回路
１１ビある。 〔主要部分の符号の説明〕

Claims (1)

  1. 【特許請求の範囲】 １、（ａ）根源節点と複数の端末節点を有する複数の接
    続された節点を有し、この各節点の 従属節点のうちの任意の１つが所定状態 にセットされた場合にその節点が所定状 態にセットされるようにした木の構造の 表現を維持するための手段、及び （ｂ）前記根源節点から始めて所定状態にセットされて
    いるすべての一連の節点を通り 所定状態にある端末節点に到達するまで 前記木を通る通路を追跡するための手段 を備えている ことを特徴とする探索装置。 ２、特許請求の範囲第１項による探索装置であつて、前
    記木の構造の表現を維持するための前記手段は複数の個
    々にアドレス可能な記憶場所を備えたランダム・アクセ
    ス・メモリを有し、前記個々にアドレス可能な記憶場所
    の各々は複数ビットを保持しており、前記根源節点以外
    の木の各節点は前記ビットのうちの１つにより表現され
    ることを特徴とする探索装置。 ３、特許請求の範囲第２項による探索装置であつて、前
    記ランダム・アクセス・メモリの各場所はｂ個のビット
    を含んでおり、そして、前記ランダム・アクセス・メモ
    リの記憶場所ｘのビットｙにより表現される節点は前記
    ランダム・アクセス・メモリの記憶場所ｂｘ＋ｙのｂ個
    のビットにより表されるｂ個の従属節点を有しているこ
    とを特徴とする探索装置。 ４、特許請求の範囲第３項による探索装置であつて、前
    記木を通る通路を追跡するための前記手段は前記ランダ
    ム・アクセス・メモリの記憶場所ｘからワードを読み出
    すために前記ランダム・アクセス・メモリをアドレスｘ
    でアドレスためのアドレス・レジスタ、前記ワードの任
    意のビットがセットされているかどうかを決定するため
    に前記ランダム・アクセス・メモリから読み出されたワ
    ードを調査するための手段、及び新しいアドレスｂｘ＋
    ｙにより前記アドレス・レジスタのアドレスｘを置き換
    えるようにビットｙがセットされた場合に動作可能な手
    段を有することを特徴とする探索装置。 ５、特許請求の範囲第４項による探索装置であつて、前
    記メモリから読み出されたワードを調査するための前記
    手段はもしもそのワードに第１のセットされたビットが
    ある場合、その第１のセットされたビットのビット桁ｙ
    を示す符号を発生する優先順位エンコーダを有している
    ことを特徴とする探索装置。 ６、特許請求の範囲第４項又は第５項による探索装置で
    あつて、前記アドレス・レジスタの内容ｂｘ＋ｙをｂで
    割つてアドレスｘと剰余ｙを発生すると共に、前記ラン
    ダム・アクセス・メモリの記憶場所ｘのビットｙを更新
    するための手段を有している、前記木の構造の表現を更
    新するための手段を備えていることを特徴とする探索装
    置。 ７、特許請求の範囲第６項による探索装置であつて、前
    記更新するための手段は、 （ａ）前記ランダム・アクセス・メモリの現在アドレス
    された記憶場所の全てのビット がもともと未セットであつて前記更新す るための手段がその１つを丁度セットし たか、又は、 （ｂ）前記ランダム・アクセス・メモリの現在アドレス
    された記憶場所のビットの１つ を除く全てがもともと未セットであつて 前記更新するための手段がその１つのビ ットを丁度未セットにしたか、 の何れかの条件を検出するための論理手段を有している
    ことを特徴とする探索装置。 ８、アイテムの集合体の中で所定基準を満足するアイテ
    ムを突き止める方法であつて、 （ａ）根源節点と複数の端末節点を有する複数の相互接
    続された節点を備えていて、各 端末節点は前記アイテムのうちの１つに 対応するようにした、木の構造の表現を 維持し、 （ｂ）各端末節点に対応するアイテムが前記所定基準を
    満足する場合その端末節点を所 定状態にセットし、 （ｃ）端末節点以外の各節点の従属節点のうちの任意の
    １つがその所定状態にセットさ れた場合に、その節点を所定状態にセッ トし、そして （ｄ）前記根源節点から始めてそれぞれの所定状態にセ
    ットされた全ての一連の節点を 通り、その所定状態の端末節点に到達す るまで前記木を通る通路を追跡すること を特徴とする、所定基準を満足するアイテムをアイテム
    の集合体の中で突き止める方法。 ９、特許請求の範囲第８項による方法であつて、前記ア
    イテムはデータ処理装置による実行のための命令であり
    、そして、前記所定基準は命令の実行の準備ができたと
    いうことであることを特徴とする所定基準を満足するア
    イテムをアイテムの集合体の中で追跡する方法。 １０、特許請求の範囲第８項による方法であつて、前記
    アイテムはデータ記憶セルであり、前記所定基準は前記
    データ記憶セルが自由であるということであるというこ
    とを特徴とする、所定基準を満足するアイテムをアイテ
    ムの集合体の中で追跡する方法。 １１、特許請求の範囲第８項ないし第１０項のうちの任
    意の１つによる方法であつて、前記木の構造の表現は、
    各々が複数のビットを保持する複数の個々にアドレス可
    能な記憶場所を有するランダム・アクセス・メモリで維
    持され、前記根源節点以外の木の各節点が前記ビットの
    うちの１つにより表現されるようにしたことを特徴とす
    る、所定基準を満足するアイテムをアイテムの集合体の
    中で追跡する方法。 １２、特許請求の範囲第１１項による方法であつて、前
    記ランダム・アクセス・メモリの各記憶場所はｂ個のビ
    ットを含んでおり、前記ランダム・アクセス・メモリの
    記憶場所ｘのビットｙにより表される節点は、前記ラン
    ダム・アクセス・メモリの記憶場所ｂｘ＋ｙにおけるｂ
    個のビットにより表されるそのｂ個の従属節点を有して
    いることを特徴とする、所定基準を満足するアイテムを
    アイテムの集合体の中で追跡する方法。 １３、特許請求の範囲第１２項による方法であつて、前
    記木を通る道を追跡する段階は、 （ａ）前記ランダム・アクセス、メモリをアドレスｘで
    アドレスして前記ランダム・ア クセス・メモリの記憶場所ｘからワード を読み出し、 （ｂ）前記ランダム・アクセス・メモリから読み出され
    たワードのビットの任意のもの がセットされているかどうかを決定する ためにその読み出されたワードを調査し、 そして、もしもビットｙがセットされて いる場合、新しいアドレスｂｘ＋ｙを形 成する小段階を含むことを特徴とする、 所定基準を 満足するアイテムをアイテムの集合体の中で追跡する方
    法。 １４、特許請求の範囲第１３項による方法であつて、 （ａ）アドレスｂｘ＋ｙをｂで割つて新しいアドレスｘ
    と剰余ｙを発生し、 （ｂ）その新しいアドレスｘと剰余ｙを使用して前記ラ
    ンダム・アクセス・メモリの記 憶場所ｘのビットｙにアクセスし、且つ、 そのビットを更新し、そして （ｃ）（ｉ）前記ランダム・アクセス・メモリの記憶場
    所ｘの全てのビットが最初未セッ トでそのうちの１つが丁度セットされ たか、又は、 （ｉｉ）前記ランダム・アクセス・メモリの記憶場所ｘ
    のビットの１つを除く全てが もともと未セットであつて、その１つ のビットが丁度未セットにされたかの いずれかである場合、前のアドレスｂ ｘ＋ｙの代わりに新しいアドレスｘを 用いて上記の段階（ａ）と（ｂ）を繰り返すことを特徴
    とする、所定基準を満足するアイテムをアイテムの集合
    体の中で追跡する方法。
JP61139403A 1985-06-19 1986-06-17 探索装置 Pending JPS61294545A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB8515482 1985-06-19
GB858515482A GB8515482D0 (en) 1985-06-19 1985-06-19 Search apparatus

Publications (1)

Publication Number Publication Date
JPS61294545A true JPS61294545A (ja) 1986-12-25

Family

ID=10580962

Family Applications (1)

Application Number Title Priority Date Filing Date
JP61139403A Pending JPS61294545A (ja) 1985-06-19 1986-06-17 探索装置

Country Status (7)

Country Link
US (1) US4751684A (ja)
EP (1) EP0206504B1 (ja)
JP (1) JPS61294545A (ja)
AU (1) AU585026B2 (ja)
DE (1) DE3688640T2 (ja)
GB (2) GB8515482D0 (ja)
ZA (1) ZA863960B (ja)

Families Citing this family (25)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS61245188A (ja) * 1985-04-24 1986-10-31 株式会社日立製作所 デ−タ処理装置
GB8515482D0 (en) * 1985-06-19 1985-07-24 Int Computers Ltd Search apparatus
NL8600848A (nl) * 1986-04-03 1987-11-02 Philips Nv Geheugen met gelijktijdig adresseerbare geheugenelementen.
JP2514365B2 (ja) * 1987-06-16 1996-07-10 三菱電機株式会社 機能ブロックのアドレスデコ−ド装置
US4873671A (en) * 1988-01-28 1989-10-10 National Semiconductor Corporation Sequential read access of serial memories with a user defined starting address
US5784712A (en) * 1995-03-01 1998-07-21 Unisys Corporation Method and apparatus for locally generating addressing information for a memory access
DE19810843B4 (de) * 1998-03-12 2004-11-25 Telefonaktiebolaget Lm Ericsson (Publ) Verfahren und Zugriffseinrichtung zum Bestimmen der Speicheradresse eines Datenwerts in einer Speichereinrichtung
US7797271B1 (en) * 2001-06-18 2010-09-14 Versata Development Group, Inc. Custom browse hierarchies for subsets of items in a primary hierarchy
DE10231970B3 (de) * 2002-07-15 2004-02-26 Siemens Ag Verfahren zur Codierung von Positionen von Datenelementen in einer Datenstruktur sowie Vorrichtungen zur entsprechenden Codierung und/oder Decodierung
US6941292B2 (en) * 2002-11-22 2005-09-06 International Business Machines Corporation Method and system for optimizing data searches in tree structures
US7362909B2 (en) * 2003-04-10 2008-04-22 Sharp Kabushiki Kaisha Coding device and method and decoding device and method
US8037102B2 (en) 2004-02-09 2011-10-11 Robert T. and Virginia T. Jenkins Manipulating sets of hierarchical data
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
US7882147B2 (en) * 2004-06-30 2011-02-01 Robert T. and Virginia T. Jenkins File location naming hierarchy
US7627591B2 (en) 2004-10-29 2009-12-01 Skyler Technology, Inc. Method and/or system for manipulating tree expressions
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
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
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
US7899821B1 (en) 2005-04-29 2011-03-01 Karl Schiffmann Manipulation and/or analysis of hierarchical data
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

Family Cites Families (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA588601A (en) * 1959-12-08 C. Sibley Henry Electronic code communication system
US3577141A (en) * 1968-11-14 1971-05-04 United Merchants & Mfg Binary to decimal tree relay decoder circuit with memory display
UST916004I4 (en) * 1973-01-16 1973-11-27 Data tree structure and maintenance method
UST948010I4 (ja) * 1975-04-10 1976-07-06
US4103349A (en) * 1977-06-16 1978-07-25 Rockwell International Corporation Output address decoder with gating logic for increased speed and less chip area
JPS6051732B2 (ja) * 1978-08-31 1985-11-15 富士通株式会社 デ−タ・ベ−スを有するデ−タ処理システム
US4318184A (en) * 1978-09-05 1982-03-02 Millett Ronald P Information storage and retrieval system and method
EP0111689A3 (en) * 1982-12-21 1987-04-08 International Business Machines Corporation Method of storing a b-tree type index file on rotating media devices
US4507752A (en) * 1983-02-22 1985-03-26 International Business Machines Corporation In-place index compression
US4606002A (en) * 1983-05-02 1986-08-12 Wang Laboratories, Inc. B-tree structured data base using sparse array bit maps to store inverted lists
JPH0644264B2 (ja) * 1983-12-23 1994-06-08 シャープ株式会社 単語記憶方式
BR8503162A (pt) * 1984-07-31 1986-03-25 Int Standard Electric Corp Metodo para investigar bases de dados esparsas usando uma tecnica associativa
US4616315A (en) * 1985-01-11 1986-10-07 Burroughs Corporation System memory for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes
GB8515482D0 (en) * 1985-06-19 1985-07-24 Int Computers Ltd Search apparatus

Also Published As

Publication number Publication date
GB2176919B (en) 1989-07-12
GB2176919A (en) 1987-01-07
ZA863960B (en) 1987-02-25
AU5882386A (en) 1986-12-24
EP0206504A3 (en) 1991-01-16
AU585026B2 (en) 1989-06-08
DE3688640T2 (de) 1993-12-09
GB8609856D0 (en) 1986-05-29
EP0206504B1 (en) 1993-06-30
DE3688640D1 (de) 1993-08-05
EP0206504A2 (en) 1986-12-30
GB8515482D0 (en) 1985-07-24
US4751684A (en) 1988-06-14

Similar Documents

Publication Publication Date Title
JPS61294545A (ja) 探索装置
EP0069570B1 (en) Memory for multi-word data bus
GB1532278A (en) Data processing system and memory module therefor
KR920022117A (ko) 메모리 억세스 장치
KR980004059A (ko) 데이타 처리장치 및 그 레지스터 어드레스 변환방법
KR910003592B1 (ko) 부분 서입 제어장치
JP3703518B2 (ja) 連想メモリシステム
KR890002773A (ko) 디지탈 비데오 신호의 기억 장치 및 그 방법
US4916649A (en) Method and apparatus for transforming a bit-reversed order vector into a natural order vector
US4020470A (en) Simultaneous addressing of different locations in a storage unit
US4479180A (en) Digital memory system utilizing fast and slow address dependent access cycles
JPS62264498A (ja) 内容アドレス式メモリ
US4488260A (en) Associative access-memory
TW267222B (en) Improved method and system of addressing
KR950012218A (ko) 연상 메모리
US4415890A (en) Character generator capable of storing character patterns at different addresses
JPH0795269B2 (ja) 命令コードのデコード装置
SU1649568A1 (ru) Электронный словарь дл изучени иностранного зыка
SU1341641A2 (ru) Запоминающее устройство
KR100624286B1 (ko) 플래시 메모리의 리페어 장치
EP1050818A1 (en) Computer memory access
JPS586970B2 (ja) Ｒｏｍアドレスのシ−ケンス制御方式
JPS60160444A (ja) リスト処理方法
SU809206A1 (ru) Устройство дл поиска информацииВ пАМ Ти
KR970022776A (ko) 메모리 억세스 장치 및 방법