公开(公告)号：US5946692A

公开(公告)日：1999-08-31

申请号：US848454

申请日：1997-05-08

申请人： Christos N. Faloutsos ,  Hosagrahar Visvesvaraya Jagadish ,  Philip Russell Korn

发明人： Christos N. Faloutsos ,  Hosagrahar Visvesvaraya Jagadish ,  Philip Russell Korn

IPC分类号： G06F17/30

CPC分类号： G06F17/30536 ,  G06F17/30592 ,  G06K9/6247 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99942

摘要： A method and system for compressing a data base that permits queries on the compressed representation of the data base. Another feature is that an approximation of the values of the data base are derivable directly from the compressed representation of the data base. Yet another feature is correction of poor approximations of the reconstructed data. Still another feature is the capability of performing aggregate queries of the compressed representation of the data base.

摘要翻译： 一种用于压缩允许对数据库的压缩表示进行查询的数据库的方法和系统。 另一个特征是可以从数据库的压缩表示直接导出数据库的值的近似值。 另一个特征是校正重建​​数据的差的近似。 另一个特征是执行数据库的压缩表示的聚合查询的能力。

公开(公告)号：US08103708B2

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

申请号：US12638140

申请日：2009-12-15

申请人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

发明人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

IPC分类号： G06F17/30

CPC分类号： H04L43/026 ,  H04L41/5003 ,  H04L41/5009 ,  H04L41/5029 ,  Y10S707/913 ,  Y10S707/99932

摘要： Described is a system and method for receiving a data stream of multi-dimensional items, collecting a sample of the data stream having a predetermined number of items and dividing the sample into a plurality of subsamples, each subsample corresponding to a single dimension of each of the predetermined number of items. A query is then executed on a particular item in at least two of the subsamples to generate data for the corresponding subsample. This data is combined into a single value.

摘要翻译： 描述了用于接收多维项目的数据流的系统和方法，收集具有预定数量的项目的数据流的样本并将样本分成多个子样本，每个子样本对应于每个子样本的单个维度 预定数量的物品。 然后在至少两个子样本中的特定项目上执行查询以生成相应子样本的数据。 该数据被组合成单个值。

公开(公告)号：US20090292726A1

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

申请号：US12512723

申请日：2009-07-30

申请人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

发明人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

IPC分类号： G06F17/30

CPC分类号： G06F16/24556 ,  G06F16/283 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A method including receiving a plurality of elements of a data stream, storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to the number of elements stored therein, comparing the frequency count of each node to a threshold value based on a total number of the elements stored in the nodes and identifying each node for which the frequency count is at least as great as the threshold value as a hierarchical heavy hitter (HHH) node and propagating the frequency count of each non-HHH nodes to its corresponding parent nodes.

摘要翻译： 一种方法，包括接收数据流的多个元素，将多维数据结构存储在存储器中，所述多维数据结构将多个元素存储为节点层级，每个节点具有对应于 存储在其中的元素的数量，基于存储在节点中的元素的总数，将每个节点的频率计数与阈值进行比较，并将频率计数至少等于阈值的每个节点识别为等级 重击（HHH）节点，并将每个非HHH节点的频率计数传播到其相应的父节点。

公开(公告)号：US07590657B1

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

申请号：US11149699

申请日：2005-06-10

申请人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

发明人： Graham Cormode ,  Philip Russell Korn ,  Shanmugavelayutham Muthukrishnan ,  Divesh Srivastava

IPC分类号： G06F7/00

CPC分类号： G06F17/30592 ,  G06F17/30489 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A method including receiving a plurality of elements of a data stream, storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to the number of elements stored therein, comparing the frequency count of each node to a threshold value based on a total number of the elements stored in the nodes and identifying each node for which the frequency count is at least as great as the threshold value as a hierarchical heavy hitter (HHH) node and propagating the frequency count of each non-HHH nodes to its corresponding parent nodes.

摘要翻译： 一种方法，包括接收数据流的多个元素，将多维数据结构存储在存储器中，所述多维数据结构将多个元素存储为节点层级，每个节点具有对应于 存储在其中的元素的数量，基于存储在节点中的元素的总数，将每个节点的频率计数与阈值进行比较，并将频率计数至少等于阈值的每个节点识别为等级 重击（HHH）节点，并将每个非HHH节点的频率计数传播到其相应的父节点。

公开(公告)号：US06738762B1

公开(公告)日：2004-05-18

申请号：US09994266

申请日：2001-11-26

申请人： Zhiyuan Chen ,  Philip Russell Korn ,  Nikolaos Koudas ,  Shanmugavelayutham Muthukrishnan

发明人： Zhiyuan Chen ,  Philip Russell Korn ,  Nikolaos Koudas ,  Shanmugavelayutham Muthukrishnan

IPC分类号： G06F1730

CPC分类号： G06F17/30592 ,  G06F17/30469 ,  Y10S707/957 ,  Y10S707/99933 ,  Y10S707/99942 ,  Y10S707/99943

摘要： An approach for multidimensional substring selectivity estimation utilizes set hashing to generate cross-counts as needed, instead of storing cross-counts for the most frequently co-occurring substrings. Set hashing is a Monte Carlo technique that is used to succinctly represent the set of tuples containing a given substring. Then, any combination of set hashes will yield a cross-count when intersected. Thus, the set hashing technique is useful in three-, four- and other multidimensional situations, since only an intersection function is required.

摘要翻译： 用于多维子串选择性估计的方法利用集合散列来根据需要产生交叉计数，而不是存储最频繁共同子串的交叉计数。 设置散列是一种蒙特卡罗技术，用于简洁地表示包含给定子字符串的元组集合。 然后，任何组合哈希值将在交叉时产生交叉计数。 因此，集合散列技术在三维，四维和其他多维情况下是有用的，因为只需要一个交集函数。