公开(公告)号：US06505205B1

公开(公告)日：2003-01-07

申请号：US10037923

申请日：2002-01-03

申请人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee

发明人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee

IPC分类号： G06F1730

CPC分类号： G06F17/30327 ,  G06F17/30333 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99937 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99945

摘要： A system and method for indexing and storing multi-dimensional or multi-attribute data. Data items are recursively sorted in a selected dimension (e.g., the dimension having the greatest variance) and divided until each subdivision fits into a leaf node having a specified fanout. Intermediate nodes and a root node are constructed to complete the index. Each node of the index is stored in a database as a separate object or record and may include a node identifier of the unique, an identifier of a parent and/or a sibling node and an entry for each child of the node, which may be data items or other nodes. Each record entry for a child includes an associated bounding area encompassing descendant data items. Another database table or module may store information about the index, such as the dimensionality of the data, the index fanout and an identifier of a root of the index.

摘要翻译： 一种用于索引和存储多维或多属性数据的系统和方法。 数据项在所选维度（例如，具有最大方差的维度）上被递归地排序，并且被划分，直到每个细分适合于具有指定扇出的叶节点。 构建中间节点和根节点以完成索引。 索引的每个节点作为单独的对象或记录存储在数据库中，并且可以包括唯一的节点标识符，父节点和/或兄弟节点的标识符以及节点的每个子节点的条目，其可以是 数据项或其他节点。 每个儿童记录条目包括一个包含后代数据项的相关联的边界区域。 另一个数据库表或模块可以存储关于索引的信息，例如数据的维度，索引扇出和索引的根的标识符。

公开(公告)号：US06381605B1

公开(公告)日：2002-04-30

申请号：US09322901

申请日：1999-05-29

申请人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee

发明人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee

IPC分类号： G06F1730

CPC分类号： G06F17/30327 ,  G06F17/30333 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99937 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99945

摘要： A system and method for indexing and storing multi-dimensional or multi-attribute data. Data items are recursively sorted in a selected dimension (e.g., the dimension having the greatest variance) and divided until each subdivision fits into a leaf node having a specified fanout. Intermediate nodes and a root node are constructed to complete the index. Each node of the index is stored in a database as a separate object or record and may include a node identifier of the unique, an identifier of a parent and/or a sibling node and an entry for each child of the node, which may be data items or other nodes. Each record entry for a child includes an associated bounding area encompassing descendant data items. Another database table or module may store information about the index, such as the dimensionality of the data, the index fanout and an identifier of a root of the index.

摘要翻译： 一种用于索引和存储多维或多属性数据的系统和方法。 数据项在所选维度（例如，具有最大方差的维度）上被递归地排序，并且被划分，直到每个细分适合于具有指定扇出的叶节点。 构建中间节点和根节点以完成索引。 索引的每个节点作为单独的对象或记录存储在数据库中，并且可以包括唯一的节点标识符，父节点和/或兄弟节点的标识符以及节点的每个子节点的条目，其可以是 数据项或其他节点。 每个儿童记录条目包括一个包含后代数据项的相关联的边界区域。 另一个数据库表或模块可以存储关于索引的信息，例如数据的维度，索引扇出和索引的根的标识符。

公开(公告)号：US06470344B1

公开(公告)日：2002-10-22

申请号：US09384648

申请日：1999-08-27

申请人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee ,  Ambuj Singh

发明人： Ravi Kothuri ,  Siva Ravada ,  Jayant Sharma ,  Jayanta Banerjee ,  Ambuj Singh

IPC分类号： G06F1730

CPC分类号： G06F17/30327 ,  G06F17/30333 ,  G06F17/30592 ,  Y10S707/957 ,  Y10S707/99945

摘要： Methods are provided for buffering nodes of a hierarchical index (e.g., R-tree, bang file, hB-tree) during operations on multi-dimensional data represented by the index. The methods are particularly suited for query operations, and a different method may be more suitable for one pattern of queries than another. Where queries are distributed in a relatively uniform manner across the domain or dataspace of an index, a node-area buffering method is provided. In this method nodes are cached or buffered in order of their respective areas (e.g., their minimum bounding areas), and a node having a smaller area will be replaced in cache before a node having a larger area. When, however, queries are not uniformly distributed, then a least frequently accessed buffering technique may be applied. According to this method statistics are maintained concerning the frequency with which individual index nodes are accessed. Those accessed less frequently are replaced in cache before those accessed more frequently. Yet another, generic, buffering strategy is provided that is suitable for all patterns of query distribution. In accordance with this method, whenever a node must be removed from cache in order to make room for a newly accessed node, cached nodes are compared to each other to determine which provides the least caching benefit and may therefore be ejected. A comparison may involve three factors—the difference in the nodes' areas, the difference in the frequency with which they have been accessed and the difference between their latest access times. These factors may be weighted to give them more or less effect in relation to each other.

摘要翻译： 提供了用于在由索引表示的多维数据的操作期间缓冲分层索引（例如，R-tree，bang文件，hB-树）的节点的方法。 这些方法特别适用于查询操作，并且不同的方法可能比另一种更适合于一种查询模式。 在索引的域或数据空间中以相对均匀的方式分布查询的情况下，提供了节点区域缓冲方法。 在这种方法中，节点按照它们各自的区域（例如，它们的最小边界区域）的顺序进行缓存或缓冲，并且具有较小区域的节点将在具有较大面积的节点之前在高速缓存中被替换。 然而，当查询不是均匀分布时，则可以应用最不频繁访问的缓冲技术。 根据该方法，关于访问各个索引节点的频率来维持统计。 访问次数较少的用户在更频繁访问的缓存中被替换。 提供了另一种适用于所有查询分发模式的通用缓冲策略。 根据该方法，每当节点必须从高速缓存中移除以便为新访问的节点腾出空间时，将缓存的节点彼此进行比较，以确定哪个节点提供最小的缓存优点并且因此可以被弹出。 比较可能涉及三个因素 - 节点区域的差异，访问频率的差异以及其最新访问时间之间的差异。 这些因素可能被加权，以使他们或多或少相互影响。

公开(公告)号：US20090094010A1

公开(公告)日：2009-04-09

申请号：US12152147

申请日：2008-05-13

申请人： Ravi Kothuri ,  Baris M. Kazar ,  Siva Ravada

发明人： Ravi Kothuri ,  Baris M. Kazar ,  Siva Ravada

IPC分类号： G06G7/48

CPC分类号： G06T17/10 ,  G06T2210/21

摘要： Systems, methods, and other embodiments associated with determining whether geometries represented by geometry objects intersect are described. One example method recursively decomposes a higher order geometry (e.g., solid) into a set of lower order geometries (e.g., surfaces) and examines the lower order geometries, continuing the recursion until an intersection decision is reached. The example method includes accessing geometry objects and accessing a spatial index that stores MBVs associated with the geometry objects. The method includes extracting candidate pairs of intersecting features upon determining MBVs associated with the geometry objects intersect and providing the candidate features to a feature-feature logic. The method includes providing an intersection signal based on a features intersection signal provided by the feature-feature logic.

摘要翻译： 描述与确定由几何对象表示的几何是否相交的系统，方法和其他实施例。 一个示例性方法将较高阶几何（例如，实体）递归地分解成一组较低阶几何（例如，表面）并且检查较低阶几何，继续递归，直到达到交集决定。 示例方法包括访问几何对象和访问存储与几何对象相关联的MBV的空间索引。 该方法包括在确定与几何对象相关联的MBV之后提取相交特征的候选对，并将候选特征提供给特征特征逻辑。 该方法包括基于由特征特征逻辑提供的特征相交信号提供交叉信号。

公开(公告)号：US08228326B2

公开(公告)日：2012-07-24

申请号：US12152147

申请日：2008-05-13

申请人： Ravi Kothuri ,  Baris M. Kazar ,  Siva Ravada

发明人： Ravi Kothuri ,  Baris M. Kazar ,  Siva Ravada

IPC分类号： G06T15/00

CPC分类号： G06T17/10 ,  G06T2210/21

摘要： Systems, methods, and other embodiments associated with determining whether geometries represented by geometry objects intersect are described. One example method recursively decomposes a higher order geometry (e.g., solid) into a set of lower order geometries (e.g., surfaces) and examines the lower order geometries, continuing the recursion until an intersection decision is reached. The example method includes accessing geometry objects and accessing a spatial index that stores MBVs associated with the geometry objects. The method includes extracting candidate pairs of intersecting features upon determining MBVs associated with the geometry objects intersect and providing the candidate features to a feature-feature logic. The method includes providing an intersection signal based on a features intersection signal provided by the feature-feature logic.

摘要翻译： 描述与确定由几何对象表示的几何是否相交的系统，方法和其他实施例。 一个示例性方法将较高阶几何（例如，实体）递归地分解成一组较低阶几何（例如，表面）并且检查较低阶几何，继续递归，直到达到交集决定。 示例方法包括访问几何对象和访问存储与几何对象相关联的MBV的空间索引。 该方法包括在确定与几何对象相关联的MBV之后提取相交特征的候选对，并将候选特征提供给特征特征逻辑。 该方法包括基于由特征特征逻辑提供的特征相交信号提供交叉信号。

公开(公告)号：US20070130171A1

公开(公告)日：2007-06-07

申请号：US11292138

申请日：2005-12-01

申请人： Robert Hanckel ,  Jayanta Banerjee ,  Siva Ravada

发明人： Robert Hanckel ,  Jayanta Banerjee ,  Siva Ravada

IPC分类号： G06F7/00

CPC分类号： G06F17/30551

摘要： Techniques for history enabling a table in a database system so that past versions of rows of the history-enabled table are available for temporal querying. The table is history enabled by adding a start time column to the table and creating a history table for the history-enabled table. The history table's rows are copies of rows of the history-enabled table that have changed and include start time and end time fields whose values indicate a period in which the history table's row was in the history-enabled table. Temporal queries are performed on a view which is the union of the history-enabled table and the history table. The temporal queries are speeded up by period of time indexes in which the leaves are grouped based on time period size, identifiers are assigned to the groups, and the keys of the index include the group identifiers.

摘要翻译： 用于历史的技术，使数据库系统中的表能够使历史启用的表的行的历史版本可用于时间查询。 通过向表中添加开始时间列并为启用历史记录的表创建历史记录表，可以启用历史记录。 历史记录表的行是已更改的历史记录表的行的副本，并且包含起始时间和结束时间字段，其值表示历史记录表在历史记录启用的表中的行期。 时间查询是在具有历史记录功能的表和历史记录表的联合的视图上执行的。 时间查询通过基于时间段大小对叶片进行分组的时间段索引进行加速，标识符被分配给组，索引的密钥包括组标识符。

公开(公告)号：US07774381B2

公开(公告)日：2010-08-10

申请号：US12069089

申请日：2008-02-07

申请人： Ravi Kothuri ,  Siva Ravada ,  Edward Fisher

发明人： Ravi Kothuri ,  Siva Ravada ,  Edward Fisher

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

CPC分类号： G06T17/20

摘要： Methods and other embodiments associated with performing an in-memory triangulation of an arbitrarily large data set are described. One example method for performing in-memory triangulation of an arbitrarily large data set includes striping a data set into multiple stripes, selecting a first stripe to triangulate, and then performing an in-memory triangulation on the stripe. The method may also include removing certain triangles from the triangulated irregular network produced by the triangulation, merging another stripe with the leftover data, and repeating the process until the arbitrarily large data set has been triangulated piece-by-piece, with the triangulations occurring in memory.

摘要翻译： 描述了与执行任意大数据集的存储器内三角测量相关联的方法和其他实施例。 用于执行任意大数据集的内存中三角测量的一个示例方法包括将数据集条带化成多个条带，选择第一条带进行三角测量，然后在该条带上执行存​​储器内三角测量。 该方法还可以包括从由三角测量产生的三角形不规则网络中去除某些三角形，将另一个条带与剩余数据合并，并重复该过程，直到任意大的数据集逐段被三角测量，其中三角测量发生在 记忆。

公开(公告)号：US20090204632A1

公开(公告)日：2009-08-13

申请号：US12069089

申请日：2008-02-07

申请人： Ravi Kothuri ,  Siva Ravada ,  Edward Fisher

发明人： Ravi Kothuri ,  Siva Ravada ,  Edward Fisher

IPC分类号： G06F7/00

CPC分类号： G06T17/20

摘要： Methods and other embodiments associated with performing an in-memory triangulation of an arbitrarily large data set are described. One example method for performing in-memory triangulation of an arbitrarily large data set includes striping a data set into multiple stripes, selecting a first stripe to triangulate, and then performing an in-memory triangulation on the stripe. The method may also include removing certain triangles from the triangulated irregular network produced by the triangulation, merging another stripe with the leftover data, and repeating the process until the arbitrarily large data set has been triangulated piece-by-piece, with the triangulations occurring in memory.

摘要翻译： 描述了与执行任意大数据集的存储器内三角测量相关联的方法和其他实施例。 用于执行任意大数据集的内存中三角测量的一个示例方法包括将数据集条带化成多个条带，选择第一条带进行三角测量，然后在该条带上执行存​​储器内三角测量。 该方法还可以包括从由三角测量产生的三角形不规则网络中去除某些三角形，将另一个条带与剩余数据合并，并重复该过程，直到任意大的数据集逐段被三角测量，其中三角测量发生在 记忆。

公开(公告)号：US20090091568A1

公开(公告)日：2009-04-09

申请号：US11906785

申请日：2007-10-03

申请人： Siva Ravada ,  Ravi Kothuri ,  Baris M. Kazar

发明人： Siva Ravada ,  Ravi Kothuri ,  Baris M. Kazar

IPC分类号： G06T17/00

CPC分类号： G06F17/30241 ,  G06F17/30592

摘要： Systems, methodologies, media, and other embodiments associated with a three dimensional spatial engine in an RDBMS are described. One example system includes logic to receive and store data representing a set of spatial features of a three dimensional geometry object. The example system may also include logic to validate the three dimensional geometry object and to provide a signal concerning the validity of the object.

摘要翻译： 描述了与RDBMS中的三维空间引擎相关联的系统，方法，介质和其他实施例。 一个示例系统包括用于接收和存储表示三维几何对象的一组空间特征的数据的逻辑。 示例系统还可以包括用于验证三维几何对象并提供关于对象的有效性的信号的逻辑。

公开(公告)号：US09384222B2

公开(公告)日：2016-07-05

申请号：US13440702

申请日：2012-04-05

申请人： Jayanta Banerjee ,  Robert Hanckel ,  Siva Ravada

发明人： Jayanta Banerjee ,  Robert Hanckel ,  Siva Ravada

IPC分类号： G06F17/30

CPC分类号： G06F17/30306

摘要： Techniques for history enabling a table in a database system so that past versions of rows of the history-enabled table are available for temporal querying. The table is history enabled by adding a start time column to the table and creating a history table for the history-enabled table. The start time field's value in a row of the history-enabled table indicates when the contents of the row last changed. The rows of the history table are copies of rows of the history-enabled table that have been deleted or updated. The rows include end time fields whose values indicate when the row was updated or deleted. A history table's row thus indicates a period in which the history table's row was in the history-enabled table. Temporal queries are performed on a view which is the union of the history-enabled table and the history table.

摘要翻译： 用于历史的技术，使数据库系统中的表能够使历史启用的表的行的历史版本可用于时间查询。 通过向表中添加开始时间列并为启用历史记录的表创建历史记录表来启用表。 历史使能表中的行的起始时间字段的值指示行的内容何时更改。 历史记录表的行是已经被删除或更新的启用历史记录的表的行的副本。 这些行包括结束时间字段，其值指示行何时更新或删除。 历史表格的行因此表示历史记录表的行在启用历史记录的表中的一段时间。 时间查询是在具有历史记录功能的表和历史记录表的联合的视图上执行的。