专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明申请

US20140081930A1 COMPRESSION SCHEME FOR IMPROVING CACHE BEHAVIOR IN DATABASE SYSTEMS 有权
标题翻译：用于改进数据库系统中的缓存行为的压缩方案
公开(公告)号：US20140081930A1
公开(公告)日：2014-03-20
申请号：US14083209
申请日：2013-11-18
申请人： Sang K. Cha , Kihong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Kihong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： The apparatuses and methods described herein may operate to identify, from an index structure stored in memory, a reference minimum bounding shape that encloses at least one minimum bounding shape. Each of the at least one minimum bounding shape may correspond to a data object associated with a leaf node of the index structure. Coordinates of a point of the at least one minimum bounding shape may be associated with a set of first values to produce a relative representation of the at least one minimum bounding shape. The set of first values may be calculated relative to coordinates of a reference point of the reference minimum bounding shape such that each of the set of first values comprises a first number of significant bits fewer than a second number of significant bits representing a second value associated with a corresponding one of absolute coordinates of the point.
摘要翻译：本文描述的装置和方法可以操作以从存储在存储器中的索引结构中识别包围至少一个最小边界形状的参考最小边界形状。所述至少一个最小边界形状中的每一个可对应于与所述索引结构的叶节点相关联的数据对象。所述至少一个最小边界形状的点的坐标可以与一组第一值相关联，以产生所述至少一个最小边界形状的相对表示。可以相对于参考最小限制形状的参考点的坐标来计算第一值集合，使得该组第一值中的每一个包括少于第二数量的有效位，第二数量的有效位少于表示相关联的第二值的第二数量的有效位与点的绝对坐标相对应。

2. 发明授权

US08121987B2 Compression scheme for improving cache behavior in database systems 有权
标题翻译：用于提高数据库系统中缓存行为的压缩方案
公开(公告)号：US08121987B2
公开(公告)日：2012-02-21
申请号：US12847475
申请日：2010-07-30
申请人： Sang K. Cha , Kihong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Kihong Kim , Keun-Joo Kwon
IPC分类号： G06F17/00
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： A scheme for accessing an index structure using a reference minimum bounding shape is disclosed. In one example embodiment, a reference minimum bounding shape that encloses two or more minimum bounding shapes may be identified from an index structure stored in memory. Each of the two or more minimum bounding shapes may correspond to a data object associated with a corresponding leaf node of the index structure. In one example embodiment, the index structure may be accessed using the reference minimum bounding shape. In one example embodiment, at least one minimum bounding shape of the two or more minimum bounding shapes may be represented in a relative representation calculated relative to the reference minimum bounding shape. Also disclosed are a method, a system and a non-transitory computer-readable storage medium for accomplishing the same scheme as described above.
摘要翻译：公开了一种使用参考最小边界形状访问索引结构的方案。在一个示例实施例中，可以从存储在存储器中的索引结构来识别包围两个或更多个最小边界形状的参考最小边界形状。两个或更多个最小边界形状中的每一个可以对应于与索引结构的相应叶节点相关联的数据对象。在一个示例实施例中，索引结构可以使用参考最小边界形状来访问。在一个示例性实施例中，可以以相对于参考最小边界形状计算的相对表示来表示两个或更多个最小边界形状的至少一个最小边界形状。还公开了用于实现如上所述的相同方案的方法，系统和非暂时的计算机可读存储介质。

3. 发明授权

US07305421B2 Parallelized redo-only logging and recovery for highly available main memory database systems 有权
标题翻译：用于高可用性主内存数据库系统的并行重做唯一记录和恢复
公开(公告)号：US07305421B2
公开(公告)日：2007-12-04
申请号：US10195822
申请日：2002-07-15
申请人： Sang K. Cha , Juchang Lee , Kihong Kim
发明人： Sang K. Cha , Juchang Lee , Kihong Kim
IPC分类号： G06F17/30
CPC分类号： G06F11/2094 , G06F11/1471 , G06F11/1662 , G06F2201/80 , Y10S707/99933 , Y10S707/99953
摘要： A parallel logging and recovery scheme for highly available main-memory database systems is presented. A preferred embodiment called parallel redo-only logging (“PROL”) combines physical logging and selective replay of redo-only log records. During physical logging, log records are generated with an update sequence number representing the sequence of database update. The log records are replayed selectively during recovery based on the update sequence number. Since the order of replaying log records doesn't matter in physical logging, PROL makes parallel operations possible. Since the physical logging does not depend on the state of the object to which the log records are applied, the present invention also makes it easy to construct a log-based hot standby system.
摘要翻译：提出了一种用于高可用性主内存数据库系统的并行日志记录和恢复方案。称为并行重做日志记录（“PROL”）的优选实施例组合物理记录和仅重做日志记录的选择性重放。在物理日志记录期间，生成日志记录，其中更新序列号表示数据库更新的顺序。基于更新序列号在恢复期间有选择地重播日志记录。由于重放日志记录的顺序在物理日志记录中无关紧要，因此PROL使并行操作成为可能。由于物理日志记录不依赖于应用日志记录的对象的状态，本发明还使得易于构建基于日志的热备用系统。

4. 发明授权

US09454560B2 Cache-conscious concurrency control scheme for database systems 有权
标题翻译：数据库系统的缓存意识并发控制方案
公开(公告)号：US09454560B2
公开(公告)日：2016-09-27
申请号：US11934986
申请日：2007-11-05
申请人： Sang K. Cha , Sangyong Hwang , Kihong Kim , Keunjoo Kwon
发明人： Sang K. Cha , Sangyong Hwang , Kihong Kim , Keunjoo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30356 , G06F17/30351 , Y10S707/99933
摘要： An optimistic, latch-free index traversal (“OLFIT”) concurrency control scheme is disclosed for an index structure for managing a database system. In each node of an index tree, the OLFIT scheme maintains a latch, a version number, and a link to the next node at the same level of the index tree. Index traversal involves consistent node read operations starting from the root. To ensure the consistency of node read operations without latching, every node update operation first obtains a latch and increments the version number after update of the node contents. Every node read operation begins with reading the version number into a register and ends with verifying if the current version number is consistent with the register-stored version number. If they are the same, the read operation is consistent. Otherwise, the node read is retried until the verification succeeds. The concurrency control scheme of the present invention is applicable to many index structures such as the B+-tree and the CSB+-tree.
摘要翻译：公开了一种用于管理数据库系统的索引结构的乐观，无锁定索引遍历（“OLFIT”）并发控制方案。在索引树的每个节点中，OLFIT方案维护锁存器，版本号和到索引树的同一级别的下一个节点的链接。索引遍历涉及从根开始的一致的节点读取操作。为了确保节点读取操作的一致性，无需锁存，每个节点更新操作首先获取锁存器，并在更新节点内容后增加版本号。每个节点读取操作都从读取寄存器中的版本号开始，并结束验证当前版本号是否与寄存器存储的版本号一致。如果它们相同，则读取操作是一致的。否则，重新尝试节点读取，直到验证成功。本发明的并发控制方案适用于诸如B +树和CSB +树的许多索引结构。

5. 发明授权

US07283987B2 Compression scheme for improving cache behavior in database systems 有权
标题翻译：用于提高数据库系统中缓存行为的压缩方案
公开(公告)号：US07283987B2
公开(公告)日：2007-10-16
申请号：US10087360
申请日：2002-03-01
申请人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30 , G06F17/00
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： A cache-conscious version of the R-tree, called the CR-tree, is disclosed. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy substantial part of the index data. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading 0's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. The experimental and analytical results show that the two-dimensional CR-tree performs search faster than the ordinary R-tree while maintaining similar update performance and consuming less memory space.
摘要翻译：公开了一种称为CR-tree的R-tree缓存意识版本。为了在节点中打包更多条目，CR树压缩MBR密钥，占用索引数据的很大一部分。它首先表示相对于其父MBR的左下角的MBR密钥的坐标，以消除相对坐标表示中的前导0。然后，它以固定位数量化相对坐标，以进一步切断尾随的较低有效位。因此，CR树变得比普通的R树显着更宽和更小。实验和分析结果表明，二维CR树比普通R-tree更快地进行搜索，同时保持类似的更新性能并消耗更少的内存空间。

6. 发明申请

US20100287144A1 COMPRESSION SCHEME FOR IMPROVING CACHE BEHAVIOR IN DATABASE SYSTEMS 有权
标题翻译：用于改进数据库系统中的缓存行为的压缩方案
公开(公告)号：US20100287144A1
公开(公告)日：2010-11-11
申请号：US12847475
申请日：2010-07-30
申请人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： A scheme for accessing an index structure using a reference minimum bounding shape is disclosed. In one example embodiment, a reference minimum bounding shape that encloses two or more minimum bounding shapes may be identified from an index structure stored in memory. Each of the two or more minimum bounding shapes may correspond to a data object associated with a corresponding leaf node of the index structure. In one example embodiment, the index structure may be accessed using the reference minimum bounding shape. In one example embodiment, at least one minimum bounding shape of the two or more minimum bounding shapes may be represented in a relative representation calculated relative to the reference minimum bounding shape. Also disclosed are a method, a system and a non-transitory computer-readable storage medium for accomplishing the same scheme as described above.
摘要翻译：公开了一种使用参考最小边界形状访问索引结构的方案。在一个示例实施例中，可以从存储在存储器中的索引结构来识别包围两个或更多个最小边界形状的参考最小边界形状。两个或更多个最小边界形状中的每一个可以对应于与索引结构的相应叶节点相关联的数据对象。在一个示例实施例中，索引结构可以使用参考最小边界形状来访问。在一个示例性实施例中，可以以相对于参考最小边界形状计算的相对表示来表示两个或更多个最小边界形状的至少一个最小边界形状。还公开了用于实现如上所述的相同方案的方法，系统和非暂时的计算机可读存储介质。

7. 发明授权

US08589369B2 Compression scheme for improving cache behavior in database systems 有权
公开(公告)号：US08589369B2
公开(公告)日：2013-11-19
申请号：US13360483
申请日：2012-01-27
申请人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： The apparatuses and methods described herein may operate to identify, from an index structure stored in memory, a reference minimum bounding shape that encloses at least one minimum bounding shape. Each of the at least one minimum bounding shape may correspond to a data object associated with a leaf node of the index structure. Coordinates of a point of the at least one minimum bounding shape may be associated with a set of first values to produce a relative representation of the at least one minimum bounding shape. The set of first values may be calculated relative to coordinates of a reference point of the reference minimum bounding shape such that each of the set of first values comprises a first number of significant bits fewer than a second number of significant bits representing a second value associated with a corresponding one of absolute coordinates of the point.

8. 发明申请

US20120124010A1 COMPRESSION SCHEME FOR IMPROVING CACHE BEHAVIOR IN DATABASE SYSTEMS 有权
标题翻译：用于改进数据库系统中的缓存行为的压缩方案
公开(公告)号：US20120124010A1
公开(公告)日：2012-05-17
申请号：US13360483
申请日：2012-01-27
申请人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： The apparatuses and methods described herein may operate to identify, from an index structure stored in memory, a reference minimum bounding shape that encloses at least one minimum bounding shape. Each of the at least one minimum bounding shape may correspond to a data object associated with a leaf node of the index structure. Coordinates of a point of the at least one minimum bounding shape may be associated with a set of first values to produce a relative representation of the at least one minimum bounding shape. The set of first values may be calculated relative to coordinates of a reference point of the reference minimum bounding shape such that each of the set of first values comprises a first number of significant bits fewer than a second number of significant bits representing a second value associated with a corresponding one of absolute coordinates of the point.
摘要翻译：本文描述的装置和方法可以操作以从存储在存储器中的索引结构中识别包围至少一个最小边界形状的参考最小边界形状。所述至少一个最小边界形状中的每一个可对应于与所述索引结构的叶节点相关联的数据对象。所述至少一个最小边界形状的点的坐标可以与一组第一值相关联，以产生所述至少一个最小边界形状的相对表示。可以相对于参考最小限制形状的参考点的坐标来计算第一值集合，使得该组第一值中的每一个包括少于第二数量的有效位，第二数量的有效位少于表示相关联的第二值的第二数量的有效位与点的绝对坐标相对应。

9. 发明授权

US07797296B2 Compression scheme for improving cache behavior in database systems 有权
标题翻译：用于提高数据库系统中缓存行为的压缩方案
公开(公告)号：US07797296B2
公开(公告)日：2010-09-14
申请号：US11867115
申请日：2007-10-04
申请人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
发明人： Sang K. Cha , Ki-Hong Kim , Keun-Joo Kwon
IPC分类号： G06F17/30
CPC分类号： G06F17/30321 , G06F17/30327 , G06F17/30333 , Y10S707/99931 , Y10S707/99932 , Y10S707/99933 , Y10S707/99942
摘要： A scheme for accessing a multi-dimensional index structure resident in main memory to refer to data objects stored in a database is disclosed. To reduce the amount of accessed index data, the scheme compresses a minimum bounding rectangle (“MBR”). The first step to compress the MBR is to represent the MBR relatively to a reference MBR. The relative representation of an MBR (“RMBR”) is coordinates of the MBR represented relative to coordinates of the reference MBR. In addition, quantization may be performed as an additional step for further compression. In this step, the RMBR is quantized using a finite level of quantization chosen from a given set of quantization levels. Alternatively, a proper node size can be chosen to reduce the index search time. The present invention also includes several alternative embodiments of the accessing scheme including whether to eliminate pointer in internal node's entries except the first entry, whether to store a reference MBR in non-root nodes, whether to apply the proposed compression technique by quantization to leaf nodes or not, and whether to place the database in main memory or in disk. Also, the present invention includes an apparatus, a system and a computer readable medium for accomplishing the same scheme as described above.
摘要翻译：公开了一种访问存储在主存储器中的多维索引结构以引用存储在数据库中的数据对象的方案。为了减少访问的索引数据量，该方案压缩最小边界矩形（“MBR”）。压缩MBR的第一步是相对于参考MBR来表示MBR。 MBR的相对表示（“RMBR”）是相对于参考MBR的坐标表示的MBR的坐标。此外，可以执行量化作为用于进一步压缩的附加步骤。在这一步骤中，使用从给定的一组量化级选择的有限的量化量来量化RMBR。或者，可以选择适当的节点大小以减少索引搜索时间。本发明还包括访问方案的若干替代实施例，包括是否消除除第一条目之外的内部节点条目中的指针，是否在非根节点中存储引用MBR，是否将所提出的压缩技术通过量化应用于叶节点是否将数据库放在主内存或磁盘中。而且，本发明包括用于实现与上述相同方案的装置，系统和计算机可读介质。

10. 发明授权

US07293028B2 Cache-conscious concurrency control scheme for database systems 有权
标题翻译：数据库系统的缓存意识并发控制方案
公开(公告)号：US07293028B2
公开(公告)日：2007-11-06
申请号：US10162731
申请日：2002-06-04
申请人： Sang K. Cha , Sangyong Hwang , Kihong Kim , Keunjoo Kwon
发明人： Sang K. Cha , Sangyong Hwang , Kihong Kim , Keunjoo Kwon
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： G06F17/30356 , G06F17/30351 , Y10S707/99933
摘要： An optimistic, latch-free index traversal (“OLFIT”) concurrency control scheme is disclosed for an index structure for managing a database system. In each node of an index tree, the OLFIT scheme maintains a latch, a version number, and a link to the next node at the same level of the index tree. Index traversal involves consistent node read operations starting from the root. To ensure the consistency of node read operations without latching, every node update operation first obtains a latch and increments the version number after update of the node contents. Every node read operation begins with reading the version number into a register and ends with verifying if the current version number is consistent with the register-stored version number. If they are the same, the read operation is consistent. Otherwise, the node read is retried until the verification succeeds. The concurrency control scheme of the present invention is applicable to many index structures such as the B+-tree and the CSB+-tree.
摘要翻译：公开了一种用于管理数据库系统的索引结构的乐观，无锁定索引遍历（“OLFIT”）并发控制方案。在索引树的每个节点中，OLFIT方案维护锁存器，版本号和到索引树的同一级别的下一个节点的链接。索引遍历涉及从根开始的一致的节点读取操作。为了确保节点读取操作的一致性，无需锁存，每个节点更新操作首先获取锁存器，并在更新节点内容后增加版本号。每个节点读取操作都从读取寄存器中的版本号开始，并结束验证当前版本号是否与寄存器存储的版本号一致。如果它们相同，则读取操作是一致的。否则，重新尝试节点读取，直到验证成功。本发明的并发控制方案适用于诸如B +树和CSB +树的许多索引结构。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式