公开(公告)号：US07945570B2

公开(公告)日：2011-05-17

申请号：US12551033

申请日：2009-08-31

申请人： Spyridon Papadimitriou ,  Philip S. Yu

发明人： Spyridon Papadimitriou ,  Philip S. Yu

IPC分类号： G06F17/30

CPC分类号： G06K9/00496

摘要： A computer-implemented method, system, and a computer readable article of manufacture identify local patterns in at least one time series data stream. A data stream is received that comprises at least one set of time series data. The at least one set of time series data is formed into a set of multiple ordered levels of time series data. Multiple ordered levels of hierarchical approximation functions are generated directly from the multiple ordered levels of time series data. A set of approximating functions are created for each level. A current window with a current window length is selected from a set of varying window lengths. The set of approximating functions created at one level in the multiple ordered levels is passed to a subsequent level as a set of time series data. The multiple ordered levels of hierarchical approximation functions are stored into memory after being generated.

摘要翻译： 计算机实现的方法，系统和计算机可读制造商标识至少一个时间序列数据流中的局部模式。 接收包括至少一组时间序列数据的数据流。 至少一组时间序列数据被形成为一组时间序列数据的多个有序级别。 分层近似函数的多个有序级别直接从多个有序级别的时间序列数据生成。 为每个级别创建一组近似函数。 从一组变化的窗口长度中选择具有当前窗口长度的当前窗口。 在多个有序等级中在一个级别创建的一组近似函数作为一组时间序列数据传递到后续级别。 分层近似函数的多个有序等级在生成后被存储到存储器中。

公开(公告)号：US20100063974A1

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

申请号：US12551033

申请日：2009-08-31

申请人： SPYRIDON PAPADIMITRIOU ,  Philip S. Yu

发明人： SPYRIDON PAPADIMITRIOU ,  Philip S. Yu

IPC分类号： G06F17/30

CPC分类号： G06K9/00496

摘要： A computer-implemented method, system, and a computer readable article of manufacture identify local patterns in at least one time series data stream. A data stream is received that comprises at least one set of time series data. The at least one set of time series data is formed into a set of multiple ordered levels of time series data. Multiple ordered levels of hierarchical approximation functions are generated directly from the multiple ordered levels of time series data. A set of approximating functions are created for each level. A current window with a current window length is selected from a set of varying window lengths. The set of approximating functions created at one level in the multiple ordered levels is passed to a subsequent level as a set of time series data. The multiple ordered levels of hierarchical approximation functions are stored into memory after being generated.

摘要翻译： 计算机实现的方法，系统和计算机可读制造商标识至少一个时间序列数据流中的局部模式。 接收包括至少一组时间序列数据的数据流。 至少一组时间序列数据被形成为一组时间序列数据的多个有序级别。 分层近似函数的多个有序级别直接从多个有序级别的时间序列数据生成。 为每个级别创建一组近似函数。 从一组变化的窗口长度中选择具有当前窗口长度的当前窗口。 在多个有序等级中在一个级别创建的一组近似函数作为一组时间序列数据传递到后续级别。 分层近似函数的多个有序等级在生成后被存储到存储器中。

公开(公告)号：US07676458B2

公开(公告)日：2010-03-09

申请号：US11846397

申请日：2007-08-28

申请人： Charu Chandra Aggarwal ,  Philip S. Yu

发明人： Charu Chandra Aggarwal ,  Philip S. Yu

IPC分类号： G06F7/00 ,  G06F17/30 ,  G06F15/173 ,  G06F15/177

CPC分类号： G06K9/00979

摘要： A method of querying a hierarchically organized sensor network, said network being sensor network with a global coordinator node at a top level which receives data from lower level intermediate nodes which are either leader nodes for lower level nodes or sensor nodes, wherein a sensor node i at a lowest level receives a signal Y(i,t) at time t, said method including constructing a sketch Swkt=(Swkt1, . . . , Swktn) for an internal node k from S wkt j = ∑ i ∈ LeafDescendents ⁡ ( k ) ⁢ ∑ q = 1 i ⁢ b wiq · r iq j , wherein component Swktj is a sketch of a descendent of node k, ritj is a random variable associated with each sensor node i and time instant t wherein index j refers to independently drawn instantiations of the random variable, bit bwit represents a state of sensor node i for signal value w=Y(i,t) at time t, and LeafDescendents(k) are the lowest level sensor nodes under node k, wherein said sketch is adapted for responding to queries regarding a state of said network.

摘要翻译： 一种查询分级组织的传感器网络的方法，所述网络是具有在顶层的全局协调器节点的传感器网络，其从作为下级节点或传感器节点的前导节点的较低级中间节点接收数据，其中传感器节点i 在最低级别，在时间t接收信号Y（i，t），所述方法包括从S wkt j =Σi∈LeafDescendents including（...）构建内部节点k的草图Swkt =（Swkt1，...，Swktn） k）Σq = 1 i b wiq·r iq j，其中分量Swktj是节点k的后代的草图，ritj是与每个传感器节点i和时刻t相关联的随机变量，其中索引j独立地指 随机变量的抽取实例，位bwit表示在时间t处信号值w = Y（i，t）的传感器节点i的状态，LeafDescendents（k）是节点k处的最低级传感器节点，其中所述草图是 适于响应关于所述网络的状态的查询 k。

公开(公告)号：US07562355B2

公开(公告)日：2009-07-14

申请号：US11068785

申请日：2005-03-01

申请人： Xiaohui Gu ,  Philip S. Yu

发明人： Xiaohui Gu ,  Philip S. Yu

IPC分类号： G06F9/45

CPC分类号： H04L12/4641

摘要： A system and method are provided for optimizing component composition in a distributed stream-processing environment having a plurality of nodes capable of being associated with one or more of a plurality of stream processing components. The system includes an adaptive composition probing (ACP) module and a hierarchical state manager. The ACP module probes a subset of the plurality of stream processing components to determine the optimal component composition in response to a stream processing request. The hierarchical state manager manages local and global information for use by said ACP module in determining the optimal component composition.

摘要翻译： 提供了一种用于在分布式流处理环境中优化组件组成的系统和方法，其具有能够与多个流处理组件中的一个或多个相关联的多个节点。 该系统包括自适应组合探测（ACP）模块和分级状态管理器。 ACP模块探测多个流处理组件的子集，以响应于流处理请求来确定最佳组件组成。 层级状态管理器管理本地和全局信息，供所述ACP模块在确定最佳组件组成时使用。

公开(公告)号：US20090119238A1

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

申请号：US11935079

申请日：2007-11-05

申请人： Lisa Amini ,  Henrique Andrade ,  Wei Fan ,  James R. Giles ,  Kirsten W. Hildrum ,  Deepak Rajan ,  Deepak S. Turaga ,  Rohit Wagle ,  Joel L. Wolf ,  Philip S. Yu

发明人： Lisa Amini ,  Henrique Andrade ,  Wei Fan ,  James R. Giles ,  Kirsten W. Hildrum ,  Deepak Rajan ,  Deepak S. Turaga ,  Rohit Wagle ,  Joel L. Wolf ,  Philip S. Yu

IPC分类号： G06N5/04

CPC分类号： G06N99/005

摘要： A method is provided for generating a resource function estimate of resource usage by an instance of a processing element configured to consume zero or more input data streams in a stream processing system having a set of available resources that comprises receiving at least one specified performance metric for the zero or more input data streams and a processing power of the set of available resources, wherein one specified performance metric is stream rate; generating a multi-part signature of executable-specific information for the processing element and a multi-part signature of context-specific information for the instance; accessing a database of resource functions to identify a static resource function corresponding to the executable-specific information and a context-dependent resource function corresponding to the context-specific information; combining the static resource function and the context-dependent resource function to form a composite resource function for the instance; and applying the resource function to the at least one specified performance metric and the processing power to generate the resource function estimate of the at least one specified performance metric for processing by the instance.

摘要翻译： 提供了一种用于通过被配置为在具有一组可用资源的流处理系统中消耗零个或多个输入数据流的处理元件的实例来生成资源使用的资源功能估计的方法，所述流处理系统包括：一组可用资源，其包括接收至少一个指定的性能度量 零个或多个输入数据流和可用资源集合的处理能力，其中一个指定的性能度量是流速率; 生成用于处理元件的可执行特定信息的多部分签名和该实例的上下文特定信息的多部分签名; 访问资源功能的数据库以识别与所述可执行特定信息相对应的静态资源功能以及与所述上下文特定信息相对应的与上下文相关的资源功能; 结合静态资源功能和上下文相关资源功能，形成实例的复合资源功能; 以及将所述资源功能应用于所述至少一个指定的性能度量和所述处理能力以生成所述至少一个指定的性能度量的所述资源功能估计，以供所述实例处理。

公开(公告)号：US20090063432A1

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

申请号：US11846397

申请日：2007-08-28

申请人： Charu Chandra Aggarwal ,  Philip S. Yu

发明人： Charu Chandra Aggarwal ,  Philip S. Yu

IPC分类号： G06F17/30

CPC分类号： G06K9/00979

摘要： A method of querying a hierarchically organized sensor network, said network being sensor network with a global coordinator node at a top level which receives data from lower level intermediate nodes which are either leader nodes for lower level nodes or sensor nodes, wherein a sensor node i at a lowest level receives a signal Y(i,t) at time t, said method including constructing a sketch Swkt=(Swkt1, . . . ,Swktn) for an internal node k from S wkt j = ∑ i ∈ LeafDescendents  ( k )  ∑ q = 1 i  b wiq · r iq j , wherein component Swktj is a sketch of a descendent of node k, ritj is a random variable associated with each sensor node i and time instant t wherein index j refers to independently drawn instantiations of the random variable, bit bwit represents a state of sensor node i for signal value w=Y(i,t) at time t, and LeafDescendents(k) are the lowest level sensor nodes under node k, wherein said sketch is adapted for responding to queries regarding a state of said network.

公开(公告)号：US20090049187A1

公开(公告)日：2009-02-19

申请号：US12165524

申请日：2008-06-30

申请人： BUGRA GEDIK ,  Kun-Lung Wu ,  Philip S. Yu

发明人： BUGRA GEDIK ,  Kun-Lung Wu ,  Philip S. Yu

IPC分类号： G06F15/16

CPC分类号： H04L49/90

摘要： One embodiment of the present method and apparatus adaptive load shedding includes receiving at least one data stream (comprising a plurality of tuples, or data items) into a first sliding window of memory. A subset of tuples from the received data stream is then selected for processing in accordance with at least one data stream operation, such as a data stream join operation. Tuples that are not selected for processing are ignored. The number of tuples selected and the specific tuples selected depend at least in part on a variety of dynamic parameters, including the rate at which the data stream (and any other processed data streams) is received, time delays associated with the received data stream, a direction of a join operation performed on the data stream and the values of the individual tuples with respect to an expected output.

摘要翻译： 本发明的方法和设备的一个实施例是自适应负载脱落包括将至少一个数据流（包括多个元组或数据项）接收到存储器的第一滑动窗口中。 然后根据至少一个数据流操作（例如数据流加入操作）选择来自接收到的数据流的元组的子集用于处理。 未选择处理的元组将被忽略。 所选择的元组的数量和所选择的特定元组至少部分取决于各种动态参数，包括接收数据流（和任何其他处理的数据流）的速率，与接收到的数据流相关联的时间延迟， 对数据流执行的连接操作的方向和相对于预期输出的单个元组的值。

公开(公告)号：US07493346B2

公开(公告)日：2009-02-17

申请号：US11058944

申请日：2005-02-16

申请人： Yun Chi ,  Haixun Wang ,  Philip S. Yu

发明人： Yun Chi ,  Haixun Wang ,  Philip S. Yu

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

CPC分类号： G06K9/6297 ,  H04L43/028

摘要： Load shedding schemes for mining data streams. A scoring function is used to rank the importance of stream elements, and those elements with high importance are investigated. In the context of not knowing the exact feature values of a data stream, the use of a Markov model is proposed herein for predicting the feature distribution of a data stream. Based on the predicted feature distribution, one can make classification decisions to maximize the expected benefits. In addition, there is proposed herein the employment of a quality of decision (QoD) metric to measure the level of uncertainty in decisions and to guide load shedding. A load shedding scheme such as presented herein assigns available resources to multiple data streams to maximize the quality of classification decisions. Furthermore, such a load shedding scheme is able to learn and adapt to changing data characteristics in the data streams.

摘要翻译： 挖掘数据流的加载脱落方案。 使用评分函数对流元素的重要性进行排序，并调查那些具有重要意义的元素。 在不知道数据流的精确特征值的上下文中，本文提出了使用马尔可夫模型来预测数据流的特征分布。 基于预测的特征分布，可以进行分类决定，以最大限度地提高预期效益。 此外，在此提出采用质量决策（QoD）度量来衡量决策中的不确定性水平并指导负荷脱落。 诸如此处呈现的负载脱落方案将可用资源分配给多个数据流以最大化分类决定的质量。 此外，这种负载脱落方案能够学习和适应数据流中不断变化的数据特性。

公开(公告)号：US20080275671A1

公开(公告)日：2008-11-06

申请号：US12115824

申请日：2008-05-06

申请人： Vittorio Castelli ,  Michail Vlachos ,  Philip S. Yu

发明人： Vittorio Castelli ,  Michail Vlachos ,  Philip S. Yu

IPC分类号： G06F15/00

CPC分类号： G06K9/00523 ,  Y10S706/90 ,  Y10S707/99936 ,  Y10S707/99937 ,  Y10S707/99945 ,  Y10S707/99953

摘要： Arrangements and methods for performing structural clustering between different time series. Time series data relating to a plurality of time series is accepted, structural features relating to the time series data are ascertained, and at least one distance between different time series via employing the structural features is determined. The different time series may be partitioned into clusters based on the at least one distance, and/or the k closest matches to a given time series query based on the at least one distance may be returned.

摘要翻译： 在不同时间序列之间进行结构聚类的布置和方法。 接收与多个时间序列相关的时间序列数据，确定与时间序列数据相关的结构特征，并且确定通过采用结构特征的不同时间序列之间的至少一个距离。 可以基于至少一个距离将不同的时间序列划分成簇，并且可以返回基于至少一个距离的/或与给定时间序列查询的k个最接近的匹配。

公开(公告)号：US20080168179A1

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

申请号：US12054207

申请日：2008-03-24

申请人： XIAOHUI GU ,  Philip S. Yu

发明人： XIAOHUI GU ,  Philip S. Yu

IPC分类号： G06F15/16

CPC分类号： G06F17/30985 ,  Y10S707/99932

摘要： A computer implemented method, apparatus, and computer usable program code for performing load diffusion to process data stream pairs. A data stream pair is received for correlation. The data stream pair is partitioned into portions to meet correlation constraints for correlating data in the data stream pair to form a partitioned data stream pair. The partitioned data stream pair is sent to a set of nodes for correlation processing to perform the load diffusion.

摘要翻译： 用于执行负载扩散以处理数据流对的计算机实现的方法，装置和计算机可用程序代码。 接收数据流对以进行相关。 将数据流对划分成部分以满足用于使数据流对中的数据相关的相关约束，以形成分区数据流对。 分区数据流对被发送到一组节点进行相关处理以执行负载扩散。