公开(公告)号：US20070214163A1

公开(公告)日：2007-09-13

申请号：US11373022

申请日：2006-03-10

Applicant: Gang Luo ,  Kun-Lung Wu ,  Philip Yu

Inventor： Gang Luo ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F7/00

CPC classification number: G06F17/30442 ,  Y10S707/99942

Abstract: There are provided methods, computer program products, and systems for indexing a data stream. A method for indexing a data stream having attribute values includes the steps of parsing the data stream, and forming an index of tuples for a subset of attribute values of the data stream. The index is configured for retrieving the top-K tuples that optimize linearly weighted sums of at least some of the attribute values in the subset.

Abstract translation: 提供了用于索引数据流的方法，计算机程序产品和系统。 用于索引具有属性值的数据流的方法包括解析数据流以及为数据流的属性值的子集形成元组的索引的步骤。 索引被配置用于检索优化子集中的至少一些属性值的线性加权和的顶部K元组。

公开(公告)号：US08271409B2

公开(公告)日：2012-09-18

申请号：US12061218

申请日：2008-04-02

Applicant: Gang Luo ,  Kun-Lung Wu ,  Philip Shi-lung Yu

Inventor： Gang Luo ,  Kun-Lung Wu ,  Philip Shi-lung Yu

IPC: G06E1/00 ,  G06E3/00

CPC classification number: G06F17/30442 ,  Y10S707/99942

Abstract: There are provided methods, computer program products, and systems for indexing a data stream. A method for indexing a data stream having attribute values includes the steps of parsing the data stream, and forming an index of tuples for a subset of attribute values of the data stream. The index is configured for retrieving the top-K tuples that optimize linearly weighted sums of at least some of the attribute values in the subset.

Abstract translation: 提供了用于索引数据流的方法，计算机程序产品和系统。 用于索引具有属性值的数据流的方法包括解析数据流以及为数据流的属性值的子集形成元组的索引的步骤。 索引被配置用于检索优化子集中的至少一些属性值的线性加权和的顶部K元组。

公开(公告)号：US07552099B2

公开(公告)日：2009-06-23

申请号：US11373022

申请日：2006-03-10

Applicant: Gang Luo ,  Kun-Lung Wu ,  Philip Shi-lung Yu

Inventor： Gang Luo ,  Kun-Lung Wu ,  Philip Shi-lung Yu

IPC: G06E1/00 ,  G06E3/00

CPC classification number: G06F17/30442 ,  Y10S707/99942

Abstract: There are provided methods, computer program products, and systems for indexing a data stream. A method for indexing a data stream having attribute values includes the steps of parsing the data stream, and forming an index of tuples for a subset of attribute values of the data stream. The index is configured for retrieving the top-K tuples that optimize linearly weighted sums of at least some of the attribute values in the subset.

Abstract translation: 提供了用于索引数据流的方法，计算机程序产品和系统。 用于索引具有属性值的数据流的方法包括解析数据流以及为数据流的属性值的子集形成元组的索引的步骤。 索引被配置用于检索优化子集中的至少一些属性值的线性加权和的顶部K元组。

公开(公告)号：US20080104038A1

公开(公告)日：2008-05-01

申请号：US11966537

申请日：2007-12-28

Applicant: Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/30

CPC classification number: G06F17/30938 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99942 ,  Y10S707/99943

Abstract: Techniques are provided for performing structural joins for answering containment queries. Such inventive techniques may be used to perform efficient structural joins of two interval lists which are neither sorted nor pre-indexed. For example, in an illustrative aspect of the invention, a technique for performing structural joins of two element sets of a tree-structured document, wherein one of the two element sets is an ancestor element set and the other of the two element sets is a descendant element set, and further wherein each element is represented as an interval representing a start position and an end position of the element in the document, comprises the following steps/operations. An index is dynamically built for the ancestor element set. Then, one or more structural joins are performed by searching the index with the interval start position of each element in the descendant element set.

Abstract translation: 提供技术来执行用于回答遏制查询的结构连接。 这样的创造性技术可以用于执行两个间隔列表的有效结构连接，这两个间隔列表既不被分类也未预索引。 例如，在本发明的说明性方面，一种用于执行树结构化文档的两个元素集合的结构连接的技术，其中两个元素集合中的一个是祖先元素集合，并且两个元素集合中的另一个是 后代元素集合，并且其中每个元素被表示为表示文档中元素的开始位置和结束位置的间隔，包括以下步骤/操作。 为祖先元素集动态构建索引。 然后，通过用后代元素集中的每个元素的间隔开始位置搜索索引来执行一个或多个结构连接。

公开(公告)号：US20050246262A1

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

申请号：US10834767

申请日：2004-04-29

Applicant: Charu Aggarwal ,  Murray Campbell ,  Yuan-Chi Chang ,  Matthew Hill ,  Chung-Sheng Li ,  Milind Naphade ,  Sriram Padmanabhan ,  John Smith ,  Min Wang ,  Kun-Lung Wu ,  Philip Yu

Inventor： Charu Aggarwal ,  Murray Campbell ,  Yuan-Chi Chang ,  Matthew Hill ,  Chung-Sheng Li ,  Milind Naphade ,  Sriram Padmanabhan ,  John Smith ,  Min Wang ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/30 ,  G06Q10/00 ,  H04L12/18 ,  H04L12/58 ,  H04L29/08 ,  G06F17/60

CPC classification number: H04L12/1859 ,  G06Q10/06 ,  G06Q10/10 ,  G06Q40/04 ,  G16H50/80 ,  H04L51/14 ,  H04L67/125 ,  H04L67/2823

Abstract: Interoperability is enabled between participants in a network by determining values associated with a value metric defined for at least a portion of the network. Information flow is directed between two or more of the participants based at least in part on semantic models corresponding to the participants and on the values associated with the value metric. The semantic models may define interactions between the participants and define at least a portion of information produced or consumed by the participants. The determination of the values and the direction of the information flow may be performed multiple times in order to modify the one or more value metrics. The direction of information flow may allow participants to be deleted from the network, may allow participants to be added to the network, or may allow behavior of the participants to be modified.

Abstract translation: 通过确定与为网络的至少一部分定义的值度量相关联的值来在网络中的参与者之间启用互操作性。 至少部分地基于与参与者对应的语义模型以及与值度量相关联的值，在两个或多个参与者之间引导信息流。 语义模型可以定义参与者之间的交互，并定义参与者产生或消费的信息的至少一部分。 可以多次执行信息流的值和方向的确定，以便修改一个或多个值度量。 信息流的方向可以允许从网络中删除参与者，可以允许参与者被添加到网络中，或者允许参与者的行为被修改。

公开(公告)号：US20050071322A1

公开(公告)日：2005-03-31

申请号：US10673651

申请日：2003-09-29

Applicant: Shyh-Kwei Chen ,  Mark Mei ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Mark Mei ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/30 ,  G06F7/00

CPC classification number: G06F17/30324 ,  G06F17/30516 ,  Y10S707/99933 ,  Y10S707/99934

Abstract: This invention introduces a new concept called virtual construct intervals (VCI), where each predicate interval is decomposed into one or more of these construct intervals. These VCIs strictly cover the predicate interval. Namely, every attribute value covered by the predicate interval is also covered by at least one of the decomposed VCIs, and vice versa. Each construct interval has a unique ID or interval coordinate and a set of endpoints. A construct interval is considered activated when a predicate interval using it in its decomposition is added to the system. The predicate ID is then inserted into the ID lists associated with the decomposed VCIs. To facilitate fast search, a bitmap vector is used to indicate the activation of VCIs that cover an event value. The challenge is to find an appropriate set of construct intervals to make predicate decomposition simple and, more importantly, to build efficient bitmap indexes. Because each construct interval covers only a small range of attribute values, the invention also uses bitmap clipping to cut unnecessary bitmap storage. To facilitate bitmap clipping, the invention introduce the covering segment concept. Bit positions outside a covering segment are pruned.

Abstract translation: 本发明引入了称为虚拟构建间隔（VCI）的新概念，其中每个谓词间隔被分解成这些构建间隔中的一个或多个。 这些VCI严格覆盖谓词间隔。 即，由谓词间隔覆盖的每个属性值也被分解的VCI中的至少一个覆盖，反之亦然。 每个构造间隔具有唯一的ID或间隔坐标和一组端点。 当在其分解中使用它的谓词间隔被添加到系统时，构造间隔被认为被激活。 然后将谓词ID插入到与分解的VCI相关联的ID列表中。 为了便于快速搜索，使用位图向量来指示覆盖事件值的VCI的激活。 挑战是找到适当的构造间隔集，使谓词分解变得简单，更重要的是构建有效的位图索引。 因为每个构造间隔仅覆盖一小段属性值，本发明还使用位图限幅来减少不必要的位图存储。 为了便于位图剪辑，本发明引入了覆盖段概念。 修剪覆盖段外的位位置。

公开(公告)号：US20060287984A1

公开(公告)日：2006-12-21

申请号：US11155221

申请日：2005-06-17

Applicant: Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/30

CPC classification number: G06F17/30516 ,  G06F17/30241 ,  G06F17/30312 ,  G06F17/30463

Abstract: Range query techniques are disclosed for use in accordance with data stream processing systems. In one aspect of the invention, a technique is provided for indexing continual range queries for use in data stream processing. For example, a technique for use in processing a data stream comprises obtaining at least one range query to be associated with the data stream, and building a range query index based on the at least one range query using one or more virtual constructs such that the query index is adaptive to one or more changes in a distribution of range query sizes. The step/operation of building the range query index may further comprise building the range query index such that the range query index accommodates one or more changes in query positions outside a monitoring area of the at least one range query. In another aspect of the invention, a technique is provided for incrementally processing continual range queries against moving objects. For example, a technique for evaluating one and more continual range queries over one and more moving objects comprises maintaining a query index with one and more containment-encoded virtual constructs associated with the one and more continual range queries over the one and more moving objects, and incrementally evaluating the one or more continual range queries using the query index.

公开(公告)号：US20060101056A1

公开(公告)日：2006-05-11

申请号：US10982583

申请日：2004-11-05

Applicant: Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/00 ,  G06F7/00

CPC classification number: G06F17/30938 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99942 ,  Y10S707/99943

Abstract: Techniques are provided for performing structural joins for answering containment queries. Such inventive techniques may be used to perform efficient structural joins of two interval lists which are neither sorted nor pre-indexed. For example, in an illustrative aspect of the invention, a technique for performing structural joins of two element sets of a tree-structured document, wherein one of the two element sets is an ancestor element set and the other of the two element sets is a descendant element set, and further wherein each element is represented as an interval representing a start position and an end position of the element in the document, comprises the following steps/operations. An index is dynamically built for the ancestor element set. Then, one or more structural joins are performed by searching the index with the interval start position of each element in the descendant element set.

Abstract translation: 提供技术来执行用于回答遏制查询的结构连接。 这样的创造性技术可以用于执行两个间隔列表的有效结构连接，这两个间隔列表既不被分类也未预索引。 例如，在本发明的说明性方面，一种用于执行树结构化文档的两个元素集合的结构连接的技术，其中两个元素集合中的一个是祖先元素集合，并且两个元素集合中的另一个是 后代元素集合，并且其中每个元素被表示为表示文档中元素的开始位置和结束位置的间隔，包括以下步骤/操作。 为祖先元素集动态构建索引。 然后，通过用后代元素集中的每个元素的间隔开始位置搜索索引来执行一个或多个结构连接。

公开(公告)号：US20060101045A1

公开(公告)日：2006-05-11

申请号：US10982570

申请日：2004-11-05

Applicant: Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

IPC: G06F17/00 ,  G06F7/00

CPC classification number: G06F16/2246

Abstract: Interval query indexing techniques for use in accordance with data stream processing systems are disclosed. For example, in an illustrative aspect of the invention, a technique for use in processing a data stream comprises the following steps/operations. First, an attribute range of query intervals associated with the data stream is partitioned into one or more segments. Then, a set of virtual intervals is defined for each of the one or more segments. A query interval index is then built using the set of virtual intervals. The query interval index may be built by decomposing each query interval into one or more of the virtual intervals, and associating a query identifier with the decomposed virtual intervals.

Abstract translation: 公开了根据数据流处理系统使用的间隔查询索引技术。 例如，在本发明的说明性方面，用于处理数据流的技术包括以下步骤/操作。 首先，与数据流相关联的查询间隔的属性范围被划分为一个或多个段。 然后，为一个或多个段中的每一个定义一组虚拟间隔。 然后使用该组虚拟间隔构建查询间隔索引。 可以通过将每个查询间隔分解为虚拟间隔中的一个或多个，并将查询标识符与分解的虚拟间隔相关联来构建查询间隔索引。

公开(公告)号：US20050071083A1

公开(公告)日：2005-03-31

申请号：US10671932

申请日：2003-09-29

Applicant: Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

Inventor： Shyh-Kwei Chen ,  Kun-Lung Wu ,  Philip Yu

IPC: G01C21/26 ,  G01C21/28 ,  G01C21/34 ,  G01C21/36 ,  G01S19/34 ,  G06F17/30 ,  G06Q10/00 ,  G06Q30/00 ,  G08G1/123 ,  G09B29/10 ,  H04Q7/20

CPC classification number: G06Q10/08 ,  G06Q10/087 ,  G06Q30/02 ,  G08G1/20 ,  G09B29/106

Abstract: A method and structure for monitoring continual queries over moving objects, including identifying a query region in a digital format. Each query region is strictly covered by at least one shingle such that each query region is completely covered by the at least one shingle and no section of any of the at least one shingle falls outside the query region.

Abstract translation: 一种用于监视运动对象的连续查询的方法和结构，包括以数字格式识别查询区域。 每个查询区域被至少一个瓦片严格地覆盖，使得每个查询区域被至少一个瓦片完全覆盖，并且该至少一个瓦板中的任一个的任何部分都不在查询区域的外部。