公开(公告)号：US3593309A

公开(公告)日：1971-07-13

申请号：US3593309D

申请日：1969-01-03

Applicant: IBM

Inventor： CLARK WILLIAM A ,  SALMOND KENT A ,  STAFFORD THOMAS S

IPC: G06F12/00 ,  G06F17/30 ,  H03M7/30 ,  G11B13/00

CPC classification number: G06F17/30955 ,  H03M7/30

Abstract: Electronically compressing a sorted sequence of uncompressed keys, each having an associated pointer address for accessing the information represented by the key. Compression is by electronic transfer of the remaining part of any key after removing some or all of (1) high-order ''''factored'''' bytes, and (2) low-order ''''noise'''' bytes. The transferred parts of a key are delineated using an electronic device for comparing like-ordered bytes in their sorting order in adjacent uncompressed keys. The comparing device determines a difference-byte position as the highestordered unequal byte position in every pair of adjacent keys. The ''''noise'''' bytes are electronically sensed as the bytes having a lower-order than the difference byte. The ''''factored'''' bytes are electronically sensed at higher-order positions than the difference-byte; and they are vicariously represented in prior compressed keys due to the sorted nature of the key sequence. In some cases, the ''''factored'''' bytes include the difference byte; and in other cases the ''''factored'''' bytes do not include all bytes having a higher-order than the difference-byte position. The pointer with each uncompressed key is associated with a related compressed key. A count field is generated with each compressed key to indicate the size of the factor field and number of transferred key bytes.

公开(公告)号：US3368207A

公开(公告)日：1968-02-06

申请号：US45505865

申请日：1965-05-12

Applicant: IBM

Inventor： BEAUSOLEIL WILLIAM F ,  CLARK WILLIAM A ,  HILL PETER R ,  SMITH RONALD M

IPC: G06F7/50 ,  G06F12/14 ,  G06F13/12

CPC classification number: G06F12/1441 ,  G06F7/50 ,  G06F13/122

公开(公告)号：US3704452A

公开(公告)日：1972-11-28

申请号：US3704452D

申请日：1970-12-31

Applicant: IBM

Inventor： BEAUSOLEIL WILLIAM F ,  BROWN DAVID T ,  CLARK WILLIAM A

IPC: G06F3/00 ,  G06F7/78 ,  G11C19/28 ,  G06F9/20 ,  H03K5/00

CPC classification number: G06F7/78 ,  G06F3/007 ,  G11C19/287

Abstract: A data storage unit is provided in which groups or ''''pages'''' of data including their addresses are stored in shift registers in successive positions, the registers being operable on a signal requesting access to shift their contents repetitively to the next position in one or more loops which include a position wherein a page may be accessed and in one or more loops which excludes said access position. Controls are provided for varying the shifting in said loops such that the positions of some or all of the pages of separately accessed classes are dynamically reordered so that they are presented to said access position on such signal in approximately or exactly the order in which they were last requested, thus reducing average access time in programs involving considerable repeated reference to a limited group of pages of the class.

Abstract translation: 提供了一种数据存储单元，其中包括其地址的数据的组或“页”在连续位置中被存储在移位寄存器中，该寄存器可以在请求访问的信号上操作以将它们的内容重复地移动到一个或多个循环中的下一个位置 其包括可以访问页面的位置以及排除所述访问位置的一个或多个循环。 提供控制以改变所述环路中的移位，使得单独访问的类别的一些或全部页面的位置被动态地重新排序，使得它们以大致或恰好其大致或顺序的顺序被呈现给该信号上的所述访问位置 最后请求，从而减少程序中的平均访问时间，重复参考有限的一组页面。

公开(公告)号：US3651483A

公开(公告)日：1972-03-21

申请号：US3651483D

申请日：1969-01-03

Applicant: IBM

Inventor： CLARK WILLIAM A ,  SALMOND KENT A ,  STAFFORD THOMAS S

IPC: G06F12/00 ,  G06F7/02 ,  G06F13/12 ,  G06F17/30 ,  G06F7/10

CPC classification number: G06F17/30955 ,  G06F7/02 ,  G06F13/12 ,  Y10S707/99931

Abstract: Electronically searching a Compressed Index for a representation of a search argument (SA). The index comprises a sequence of compressed keys (CK''s) generated with the method in patent application Ser. No. 788,807, in which the sequence of compressed keys represents a sorted sequence of uncompressed keys, and each compressed key (CK) has the FLK format as defined therein. As ascending sorted index is assumed for the described embodiments. An Equal Counter is used during the search to represent which byte (called A-byte) of the SA is being searched for. The A bytes are handled one byte at a time beginning with the highest order byte in the SA. The counter is initially set to reflect this beginning and it is incremented each time the A-byte compares equal with one of the key bytes (called K byte) in a current CK being searched. Electronic means compares the Equal-Counter setting, Ec, with a factor-byte count, F, the latter being obtained from the F field in a CK. If Ec is greater than F, the search is completed. If Ec is less than F, the search continues using the next sequential CK in the compressed index. But, if Ec is equal to F, the highest order K-byte in the current CK is compared against the current Abyte. If K A, the search of the compressed index ends with the current CK. However, if K A, the Equal Counter is incremented as indicated previously, the next lower order A-byte being obtained from the SA, and the next lower order K-byte being obtained from the current CK. These next A- and K-bytes are then compared; and if they are equal, the process is repeated until the last K-byte in the current CK has been found equal to an A-byte. If no A-byte remains in the SA for comparison to a remaining K-byte, the search of the compressed index is completed. If uncompared Abytes remain in the SA, and no K-bytes remain uncompared in the current CK, the search continues using the next sequential CK. Whenever the search ends at a CK, that CK is expected to represent the SA. A pointer associated with that CK is readout as part of the search ending operation. A data item addressed by that pointer is obtained, and the SA is verified against the data item to assure that the SA also represents the retrieved data item.

Abstract translation: 电子搜索压缩索引以表示搜索参数（SA）。 该索引包括利用专利申请系列中的方法产生的一系列压缩密钥（CK）。 No.788,807，其中压缩密钥的序列表示未压缩密钥的排序顺序，并且每个压缩密钥（CK）具有其中定义的FLK格式。 对于所描述的实施例，假定上升排序索引。 在搜索期间使用等于计数器来表示正在搜索SA的哪个字节（称为A字节）。 A字节从SA中的最高位字节开始处理一个字节。 计数器最初设置为反映这一开始，并且每当A字节比较与正在搜索的当前CK中的一个关键字节（称为K字节）相等时，其递增。

公开(公告)号：US3646524A

公开(公告)日：1972-02-29

申请号：US3646524D

申请日：1969-12-31

Applicant: IBM

Inventor： CLARK WILLIAM A ,  DAVIES CHARLES T JR ,  SALMOND KENT A ,  STAFFORD THOMAS S

IPC: G06F17/30 ,  H03M7/30 ,  G05B19/22 ,  G06F7/04

CPC classification number: H03M7/30 ,  Y10S707/99942

Abstract: High-level index-factoring system generates a multilevel compressed index in which the compressed key format in all levels of the index (i.e., high and low) are searchable by a single method, such as the method in allowed application Ser. No. 788,835. The generation process includes the factoring of high-order bytes common to all uncompressed keys contributing to any compressed index block at any level; the factored high-order bytes are transferred into a compressed key in the next higher level compressed index block. The high levels in the compressed index are built by selectively passing to the high levels the last uncompressed key (UK) used in the generation of each low-level compressed index block. The determination to pass the UK to a next higher level is made when the UK is the last UK used to generate the last-compressed key (CK) in the compressed index block at the current level. The propagation of a UK to successive high levels ends whenever the UK is used to generate a CK which does not complete a compressed index block. Thus the UK passing depends on the block completion function at successive levels. A different sequence of UK''s is received by each high level. The CK''s at any high level are generated from the sequence of UK''s passed to that level; each high-level CK is generated from the current and prior UK''s passed to the same level. Thus each UK passed to a high level is used to generate a current CK for that level, and then the UK is stored for that level so that it can later be used in the generation of the next CK for that level when a next UK is passed to it. The key bytes in each high-level CK are taken from the UK currently passed to that level, beginning from a leftmost byte which is dependent on whether the currently passed UK is a rightshift type, a left-shift type, or no-shift type at the respective high level. The UK type at a high level is independent of its type at a lower level because the UK sequence is different. The rightmost key byte for the respective high level CK is determined by the low-level difference byte in the same UK determined by its use in generating a CK for the low-level index; this rightmost byte is independent of the UK type at the respective high level. If the passed UK is a left- or no-shift type at the respective high level, the key bytes for the high-level CK are taken from the high-level difference byte through the low-level difference byte. If it is a right-shift type of CK at the respective high level, the key bytes are taken from its position after the highlevel difference byte in the prior UK