公开(公告)号：US08990173B2

公开(公告)日：2015-03-24

申请号：US12056979

申请日：2008-03-27

申请人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

发明人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

IPC分类号： G06F7/00 ,  H03M7/30

CPC分类号： H03M7/30

摘要： Techniques are disclosed for selecting a delete-safe compression method for a plurality of delta encoded data values (e.g., delta encoded integers or deltas). For example, a computer-implemented method for selecting an optimal delete-safe compression algorithm from among two or more compression algorithms for use on a plurality of delta encoded data values includes the following steps. The maximum number of data values eliminated by each of the two or more compression algorithms is computed. For the plurality of delta encoded data values to be compressed, the minimum size of the plurality of delta encoded data values before compression thereof is computed. A delete-safe threshold value is computed based on the minimum size of the plurality of delta encoded data values. Then, the compression algorithm is selected from the two or more compression algorithms that achieves the delete-safe threshold value.

摘要翻译： 公开了用于为多个增量编码的数据值（例如，增量编码的整数或三角形）选择删除安全的压缩方法的技术。 例如，用于从用于多个增量编码数据值的两个或更多个压缩算法中选择最佳删除安全压缩算法的计算机实现的方法包括以下步骤。 计算由两个或更多个压缩算法中的每一个消除的数据值的最大数目。 对于要压缩的多个delta编码数据值，计算其压缩之前的多个Δ编码数据值的最小大小。 基于多个增量编码数据值的最小大小来计算删除安全阈值。 然后，从实现删除安全​​阈值的两个或更多个压缩算法中选择压缩算法。

公开(公告)号：US08126929B2

公开(公告)日：2012-02-28

申请号：US12057012

申请日：2008-03-27

申请人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

发明人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

IPC分类号： G06F17/30

CPC分类号： G06F17/30958 ,  G06F17/30286

摘要： Techniques are disclosed for encoding a variable length structure such that it facilitates forward and reverse scans of a list of such structures as needed. While the techniques are applicable to a wide variety of applications, they are particularly well-suited for use with structures such as those found in compressed database indexes. For example, a computer-implemented method for processing one or more variable length data structures includes the following steps. Each variable length data structure is obtained. Each variable length structure comprises one or more data block. A variable length encoding process is applied to the one or more blocks of each variable length data structure which comprises setting a continuation data value in each block to a first value or a second value, wherein the setting of the continuation data values enables bi-directional scanning of each variable length structure.

摘要翻译： 公开了用于编码可变长度结构的技术，使得其有助于正向和反向扫描所需的这种结构的列表。 虽然这些技术适用于各种各样的应用，但它们特别适用于诸如在压缩数据库索引中发现的结构。 例如，用于处理一个或多个可变长度数据结构的计算机实现的方法包括以下步骤。 获得每个可变长度数据结构。 每个可变长度结构包括一个或多个数据块。 可变长度编码处理被应用于每个可变长度数据结构的一个或多个块，其包括将每个块中的连续数据值设置为第一值或第二值，其中，连续数据值的设置允许双向 扫描每个可变长度结构。

公开(公告)号：US20090248724A1

公开(公告)日：2009-10-01

申请号：US12057012

申请日：2008-03-27

申请人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

发明人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

IPC分类号： G06F17/30

CPC分类号： G06F17/30958 ,  G06F17/30286

摘要： Techniques are disclosed for encoding a variable length structure such that it facilitates forward and reverse scans of a list of such structures as needed. While the techniques are applicable to a wide variety of applications, they are particularly well-suited for use with structures such as those found in compressed database indexes. For example, a computer-implemented method for processing one or more variable length data structures includes the following steps. Each variable length data structure is obtained. Each variable length structure comprises one or more data block. A variable length encoding process is applied to the one or more blocks of each variable length data structure which comprises setting a continuation data value in each block to a first value or a second value, wherein the setting of the continuation data values enables bi-directional scanning of each variable length structure.

摘要翻译： 公开了用于编码可变长度结构的技术，使得其有助于正向和反向扫描所需的这种结构的列表。 虽然这些技术适用于各种各样的应用，但它们特别适用于诸如在压缩数据库索引中发现的结构。 例如，用于处理一个或多个可变长度数据结构的计算机实现的方法包括以下步骤。 获得每个可变长度数据结构。 每个可变长度结构包括一个或多个数据块。 可变长度编码处理被应用于每个可变长度数据结构的一个或多个块，其包括将每个块中的连续数据值设置为第一值或第二值，其中，连续数据值的设置允许双向 扫描每个可变长度结构。

公开(公告)号：US20090248723A1

公开(公告)日：2009-10-01

申请号：US12056979

申请日：2008-03-27

申请人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

发明人： Bishwaranjan Bhattacharjee ,  Lipyeow Lim ,  Timothy Ray Malkemus ,  George Andrei Mihaila

IPC分类号： G06F17/30

CPC分类号： H03M7/30

摘要： Techniques are disclosed for selecting a delete-safe compression method for a plurality of delta encoded data values (e.g., delta encoded integers or deltas). For example, a computer-implemented method for selecting an optimal delete-safe compression algorithm from among two or more compression algorithms for use on a plurality of delta encoded data values includes the following steps. The maximum number of data values eliminated by each of the two or more compression algorithms is computed. For the plurality of delta encoded data values to be compressed, the minimum size of the plurality of delta encoded data values before compression thereof is computed. A delete-safe threshold value is computed based on the minimum size of the plurality of delta encoded data values. Then, the compression algorithm is selected from the two or more compression algorithms that achieves the delete-safe threshold value.

摘要翻译： 公开了用于为多个增量编码的数据值（例如，增量编码的整数或三角形）选择删除安全的压缩方法的技术。 例如，用于从用于多个增量编码数据值的两个或更多个压缩算法中选择最佳删除安全压缩算法的计算机实现的方法包括以下步骤。 计算由两个或更多个压缩算法中的每一个消除的数据值的最大数目。 对于要压缩的多个delta编码数据值，计算其压缩之前的多个Δ编码数据值的最小大小。 基于多个增量编码数据值的最小大小来计算删除安全阈值。 然后，从实现删除安全​​阈值的两个或更多个压缩算法中选择压缩算法。

公开(公告)号：US20080183657A1

公开(公告)日：2008-07-31

申请号：US11627475

申请日：2007-01-26

申请人： Yuan-Chi Chang ,  Lipyeow Lim ,  George Andrei Mihaila

发明人： Yuan-Chi Chang ,  Lipyeow Lim ,  George Andrei Mihaila

IPC分类号： G06F17/30 ,  G06F7/00 ,  G06F17/00 ,  G06F3/00

CPC分类号： G06F16/83

摘要： A computer implemented method, data processing system, and computer usable program code are provided for accessing unique hierarchical data. A tree structure for a document is analyzed. A determination is made as to whether a set of unique paths exist in the tree structure. Responsive to an existence of the set of unique paths, a unique path identifier is assigned to each of the set of unique paths to create a set of unique path identifiers and assigned unique path pairs. Then, the unique path identifier and a node address for the unique hierarchical data for each of the set of unique path identifiers and assigned unique path pairs is stored into a header in the document disk page.

摘要翻译： 提供计算机实现的方法，数据处理系统和计算机可用程序代码用于访问唯一分层数据。 分析文档的树结构。 确定树结构中是否存在一组唯一路径。 响应于唯一路径集合的存在，将唯一路径标识符分配给每组唯一路径，以创建一组唯一的路径标识符和分配的唯一路径对。 然后，唯一路径标识符和用于唯一路径标识符集合和分配的唯一路径对中的每一个的唯一分层数据的节点地址被存储在文档盘页面中的报头中。

公开(公告)号：US20070271218A1

公开(公告)日：2007-11-22

申请号：US11435353

申请日：2006-05-16

申请人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

发明人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

IPC分类号： G06F17/30

CPC分类号： G06F17/30442 ,  G06F17/30306 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99944 ,  Y10S707/99953

摘要： A method, system, and computer readable medium for collecting statistics associated with data in a database are disclosed. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory is allocated as determined for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated. The performing includes at least determining a total number of instances of at least one path-identifier associated with a given value within a given set of documents.

摘要翻译： 公开了一种用于收集与数据库中的数据相关联的统计信息的方法，系统和计算机可读介质。 该方法包括确定为关系数据库中与定义的数据类型相关联的数据收集统计信息所需的存储器量。 定义的数据类型基于使用具有一个或多个根到节点路径的树结构的标记语言。 分配的内存量被确定为收集定义的数据类型的数据的统计信息。 在通过数据库的单次传递中以及已经分配的内存量中，对定义的数据类型的数据执行统计信息收集。 执行包括至少确定与给定文档集合内的给定值相关联的至少一个路径标识符的实例的总数。

公开(公告)号：US20070271217A1

公开(公告)日：2007-11-22

申请号：US11435017

申请日：2006-05-16

申请人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

发明人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

IPC分类号： G06F17/30

CPC分类号： G06F17/30536 ,  G06F17/30442 ,  G06F17/30935 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99944 ,  Y10S707/99953

摘要： Disclosed are a system, method, and computer readable medium for collecting statistics associated with data in a database. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory as determined is allocated for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

摘要翻译： 公开了用于收集与数据库中的数据相关联的统计信息的系统，方法和计算机可读介质。 该方法包括确定为关系数据库中与定义的数据类型相关联的数据收集统计信息所需的存储器量。 定义的数据类型基于使用具有一个或多个根到节点路径的树结构的标记语言。 分配所确定的内存量用于收集所定义数据类型的数据的统计信息。 在通过数据库的单次传递中以及已分配的内存量内，对定义的数据类型的数据执行统计信息收集。

公开(公告)号：US07472108B2

公开(公告)日：2008-12-30

申请号：US11435353

申请日：2006-05-16

申请人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

发明人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

IPC分类号： G06F17/30 ,  G06F12/00

CPC分类号： G06F17/30442 ,  G06F17/30306 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99944 ,  Y10S707/99953

摘要： A method for collecting statistics associated with data in a database are disclosed. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory is allocated as determined for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated. The performing includes at least determining a total number of instances of at least one path-identifier associated with a given value within a given set of documents.

摘要翻译： 公开了一种用于收集与数据库中的数据相关联的统计信息的方法。 该方法包括确定为关系数据库中与定义的数据类型相关联的数据收集统计信息所需的存储器量。 定义的数据类型基于使用具有一个或多个根到节点路径的树结构的标记语言。 分配的内存量被确定为收集定义的数据类型的数据的统计信息。 在通过数据库的单次传递中以及已经分配的内存量中，对定义的数据类型的数据执行统计信息收集。 执行包括至少确定与给定文档集合内的给定值相关联的至少一个路径标识符的实例的总数。

公开(公告)号：US07613682B2

公开(公告)日：2009-11-03

申请号：US11435017

申请日：2006-05-16

申请人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

发明人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

IPC分类号： G06F17/30

CPC分类号： G06F17/30536 ,  G06F17/30442 ,  G06F17/30935 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99944 ,  Y10S707/99953

摘要： Disclosed are a method for collecting statistics associated with data in a database. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory as determined is allocated for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

摘要翻译： 公开了一种用于收集与数据库中的数据相关联的统计信息的方法。 该方法包括确定为关系数据库中与定义的数据类型相关联的数据收集统计信息所需的存储器量。 定义的数据类型基于使用具有一个或多个根到节点路径的树结构的标记语言。 分配所确定的内存量用于收集所定义数据类型的数据的统计信息。 在通过数据库的单次传递中以及已分配的内存量内，对定义的数据类型的数据执行统计信息收集。

公开(公告)号：US09117005B2

公开(公告)日：2015-08-25

申请号：US12341309

申请日：2008-12-22

申请人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

发明人： Lipyeow Lim ,  George Andrei Mihaila ,  Min Wang

IPC分类号： G06F17/00 ,  G06F17/30

CPC分类号： G06F17/30935 ,  G06F17/30911

摘要： A method, system, and computer readable medium for collecting statistics associated with data in a database are disclosed. The computer readable medium implements the method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory is allocated as determined for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated. The performing includes at least determining a total number of instances of at least one path-identifier associated with a given value within a given set of documents.

摘要翻译： 公开了一种用于收集与数据库中的数据相关联的统计信息的方法，系统和计算机可读介质。 计算机可读介质实现该方法包括确定收集与关系数据库中定义的数据类型相关联的数据的统计信息所需的存储器量。 定义的数据类型基于使用具有一个或多个根到节点路径的树结构的标记语言。 分配的内存量被确定为收集定义的数据类型的数据的统计信息。 在通过数据库的单次传递中以及已经分配的内存量中，对定义的数据类型的数据执行统计信息收集。 执行包括至少确定与给定文档集合内的给定值相关联的至少一个路径标识符的实例的总数。