专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US06477534B1 Method and system for generating a statistical summary of a database using a join synopsis 有权
标题翻译：使用连接概要生成数据库的统计摘要的方法和系统
公开(公告)号：US06477534B1
公开(公告)日：2002-11-05
申请号：US09480261
申请日：2000-01-11
申请人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala
发明人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala
IPC分类号： G06F1730
CPC分类号： G06F17/30457 , G06F17/30489 , G06F17/30536 , Y10S707/99933 , Y10S707/99935
摘要： A method for generating an approximate answer to a query in a database environment in which the database has a plurality of base relations. A query relating to a database is received, and an approximate answer to the query is generated such that the approximate answer is based on at least one join synopsis formed from the database. The method further includes steps of forming a sample-tuple set for at least one selected base relation of a plurality of base relations of a database such that each sample-tuple set contains at least one sample tuple from a corresponding base relation, and forming a join synopsis set for each selected base relation such that each join synopsis set contains a join synopsis for each sample tuple in a sample-tuple set. A join synopsis of a sample tuple is based on a join of the sample tuple and at least one descendent relation of the sample tuple. All join synopsis sets form a statistical summary of the database and are stored.
摘要翻译：一种在数据库具有多个基本关系的数据库环境中生成关于查询的近似答案的方法。接收到与数据库相关的查询，并且产生查询的近似答案，使得近似答案基于从数据库形成的至少一个连接概要。该方法还包括以下步骤：为数据库的多个基本关系中的至少一个选定的基本关系形成样本组元组，使得每个样本组元组包含来自相应基础关系的至少一个样本元组，并形成为每个选定的基础关系加入概要集，使得每个连接概要集包含样本元组中每个样本元组的连接概要。样本元组的连接概要基于样本元组的连接和样本元组的至少一个后代关系。所有连接概要集形成数据库的统计摘要，并存储。

2. 发明授权

US06912524B2 Join synopsis-based approximate query answering 有权
标题翻译：加入基于概要的近似查询回答
公开(公告)号：US06912524B2
公开(公告)日：2005-06-28
申请号：US10216295
申请日：2002-08-12
申请人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy
发明人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy
IPC分类号： G06F17/30
CPC分类号： G06F17/30489 , G06F17/30536 , Y10S707/99933 , Y10S707/99934
摘要： A method for generating an approximate answer to a query in a database environment in which the database has a plurality of base relations. A query relating to a database is received, and an approximate answer to the query is generated such that the approximate answer is based on at least one join synopsis formed from the database. The method further includes steps of forming a sample-tuple set for at least one selected base relation of a plurality of base relations of a database such that each sample-tuple set contains at least one sample tuple from a corresponding base relation, and forming a join synopsis set for each selected base relation such that each join synopsis set contains a join synopsis for each sample tuple in a sample-tuple set. A join synopsis of a sample tuple is based on a join of the sample tuple and at least one descendent relation of the sample tuple. All join synopsis sets form a statistical summary of the database and are stored.
摘要翻译：一种在数据库具有多个基本关系的数据库环境中生成关于查询的近似答案的方法。接收到与数据库相关的查询，并且产生查询的近似答案，使得近似答案基于从数据库形成的至少一个连接概要。该方法还包括以下步骤：为数据库的多个基本关系中的至少一个选定的基本关系形成样本组元组，使得每个样本组元组包含来自相应基础关系的至少一个样本元组，并形成为每个选定的基础关系加入概要集，使得每个连接概要集包含样本元组中每个样本元组的连接概要。样本元组的连接概要基于样本元组的连接和样本元组的至少一个后代关系。所有连接概要集形成数据库的统计摘要，并存储。

3. 发明授权

US06519604B1 Approximate querying method for databases with multiple grouping attributes 有权
标题翻译：具有多个分组属性的数据库的近似查询方法
公开(公告)号：US06519604B1
公开(公告)日：2003-02-11
申请号：US09619902
申请日：2000-07-19
申请人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala
发明人： Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala
IPC分类号： G06F1730
CPC分类号： G06F17/30536 , Y10S707/99933 , Y10S707/99943 , Y10S707/99945
摘要： An approximate querying method comprising grouping tuples within a database according to grouping attributes, determining how many tuples are needed to represent each group, selecting the tuples from a corresponding group to create a database sample, and querying the database sample. The database sample yields statistically unbiased answers when queried. The sample may be created and maintained without a priori knowledge of the data distribution within the database or the queries to be performed.
摘要翻译：一种近似查询方法，包括根据分组属性对数据库内的元组进行分组，确定需要多少元组来表示每个组，从对应的组中选择元组以创建数据库样本，以及查询数据库样本。数据库样本在查询时产生统计学上无偏见的答案。可以创建和维护样本，而无需对数据库中的数据分布或要执行的查询的先验知识。

4. 发明授权

US5870752A Incremental maintenance of an approximate histogram in a database system 失效
标题翻译：在数据库系统中增加一个近似直方图的维护
公开(公告)号：US5870752A
公开(公告)日：1999-02-09
申请号：US915804
申请日：1997-08-21
申请人： Phillip B. Gibbons , Yossi Matias , Viswanath Poosala , Andrew Witkowski
发明人： Phillip B. Gibbons , Yossi Matias , Viswanath Poosala , Andrew Witkowski
IPC分类号： G06F17/30
CPC分类号： G06F17/30368 , Y10S707/99942 , Y10S707/99943 , Y10S707/99945
摘要： Techniques for maintaining an approximate histogram of a relation in a database, in the presence of updates to the relation. The histogram includes a number of subsets, or "buckets," each representing at least one possible value of an attribute of the relation. Each of the subsets has a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute. After an update to the relation, the counts associated with the subsets are compared to a threshold. If the count associated with a given subset exceeds the threshold, the given subset is separated at its median into two separate subsets. After the separation operation, the two subsets with the lowest counts are combined such that a constant number of subsets are maintained in the histogram, if the total combined count of the subsets does not exceed the threshold. If no two subsets have a total combined count which does not exceed the threshold, the histogram is recomputed from a random sample of the relation. The invention substantially reduces the number of times the histogram must be recomputed from the random sample, and is particularly well-suited for use with approximate equi-depth and compressed histograms.
摘要翻译：在关系更新的情况下维护数据库中关系的近似直方图的技术。直方图包括多个子集或“桶”，每个子集表示该关系属性的至少一个可能的值。每个子集具有与其相关联的计数，指示属性的相应值的出现频率。在更新关系后，将与子集关联的计数与阈值进行比较。如果与给定子集相关联的计数超过阈值，则给定子集在其中间被分离成两个单独的子集。在分离操作之后，组合具有最低计数的两个子集，使得如果子集的总组合计数不超过阈值，则在直方图中维持恒定数量的子集。如果没有两个子集具有不超过阈值的总组合计数，则从该关系的随机样本重新计算直方图。本发明基本上减少了从随机样本重新计算直方图的次数，并且特别适用于近似等深度和压缩的直方图。

5. 发明授权

US6012064A Maintaining a random sample of a relation in a database in the presence of updates to the relation 失效
标题翻译：在关系更新的情况下，在数据库中维护关系的随机抽样
公开(公告)号：US6012064A
公开(公告)日：2000-01-04
申请号：US915774
申请日：1997-08-21
申请人： Phillip B. Gibbons , Yossi Matias , Viswanath Poosala
发明人： Phillip B. Gibbons , Yossi Matias , Viswanath Poosala
IPC分类号： G06F17/30
CPC分类号： G06F17/30595 , Y10S707/954 , Y10S707/99933 , Y10S707/99934 , Y10S707/99942 , Y10S707/99943 , Y10S707/99944
摘要： Techniques for maintaining a random sample of a relation in a database in the presence of updates to the relation. The random sample of the relation is referred to as a "backing sample," and it is maintained in the presence of insert, modify and delete operations involving the relation. When a new tuple is inserted into the relation, a sample of the given tuple is added to the backing sample if the size of the backing sample is below an upper bound. Otherwise, a randomly-selected tuple of the backing sample is replaced with the new tuple if a sample of the new tuple must be inserted into the backing sample to maintain randomness or another characteristic. When a tuple in the relation is the subject of a modify operation, the backing sample is left unchanged if the modify operation does not affect an attribute of interest to an application which uses the backing sample. Otherwise, a value field in a sample of the tuple in the backing sample is updated. When a tuple is deleted from the relation, any sample of that tuple in the backing sample is removed. A new backing sample may be computed if this removal causes the size of the backing sample to fall below a prespecified lower bound. The backing sample can be of a size which is negligible in comparison to the relation, and need only be modified very infrequently. As a result, its overhead in terms of computation time and storage space is minimal.
摘要翻译：在存在关系更新的情况下，在数据库中维护关系随机抽样的技术。该关系的随机样本被称为“后备样本”，并且在存在涉及该关系的插入，修改和删除操作的情况下保持该样本。当一个新元组被插入关系中时，如果背景样本的大小低于上限，则将给定元组的样本添加到背景样本中。否则，如果必须将新元组的样本插入到背景样本中以保持随机性或其他特征，则将随机选择的背衬样本的元组替换为新的元组。当关系中的元组是修改操作的主题时，如果修改操作不影响使用后备样本的应用程序感兴趣的属性，则后备样本将保持不变。否则，将更新背景样本中的元组样本中的值字段。当从该关系中删除元组时，将删除该背景样本中该元组的任何样本。如果这种去除导致背衬样品的尺寸低于预先指定的下限，则可以计算新的背衬样品。背衬样本的尺寸可以与关系相比可以忽略不计，并且只需要非常频繁地修改。因此，其在计算时间和存储空间方面的开销是最小的。

6. 发明授权

US06772179B2 System and method for improving index performance through prefetching 有权
标题翻译：通过预取来提高指数表现的系统和方法
公开(公告)号：US06772179B2
公开(公告)日：2004-08-03
申请号：US10034450
申请日：2001-12-28
申请人： Shimin Chen , Phillip B. Gibbons , Todd C. Mowry
发明人： Shimin Chen , Phillip B. Gibbons , Todd C. Mowry
IPC分类号： G06F1730
CPC分类号： G06F12/0862 , Y10S707/99937 , Y10S707/99942 , Y10S707/99955
摘要： The present invention provides a prefetch system for use with a cache memory associated with a database employing indices. In one embodiment, the prefetch system includes a search subsystem configured to prefetch cache lines containing an index of a node of a tree structure associated with the database. Additionally, the prefetch system also includes a scan subsystem configured to prefetch cache lines based on an index prefetch distance between first and second leaf nodes of the tree structure.
摘要翻译：本发明提供一种与使用索引的数据库相关联的高速缓冲存储器使用的预取系统。在一个实施例中，预取系统包括被配置为预取包含与数据库相关联的树结构的节点的索引的高速缓存行的搜索子系统。另外，预取系统还包括被配置为基于树结构的第一和第二叶节点之间的索引预取距离来预取高速缓存行的扫描子系统。

7. 发明授权

US5689696A Method for maintaining information in a database used to generate high biased histograms using a probability function, counter and threshold values 失效
标题翻译：用于使用概率函数，计数器和阈值在用于生成高偏向直方图的数据库中维护信息的方法
公开(公告)号：US5689696A
公开(公告)日：1997-11-18
申请号：US579753
申请日：1995-12-28
申请人： Phillip B. Gibbons , Yossi Matias , Andrew Witkowski
发明人： Phillip B. Gibbons , Yossi Matias , Andrew Witkowski
IPC分类号： G07G1/14 , G06F19/00 , G06Q30/02 , G06F17/30
CPC分类号： G06Q30/02 , Y10S707/99931 , Y10S707/99935
摘要： A method maintains information associated with items in a database of limited memory which information is used to generate representations of the information such as high-biased histograms. In a first embodiment of the inventive method, information associated with all items with sales above a threshold, together with approximate counts of the items, is maintained. Appropriate choice of a threshold limits the amount of information required to be maintained so as to generate accurate representations of the information with high probability. In a second embodiment of the inventive method, information used to generate a high-biased histogram is maintained within a fixed allotment of memory by dynamic adjusting a threshold which threshold is used to determine a probability with which information is retained in the database.
摘要翻译：一种方法维护与有限存储器的数据库中的项目相关联的信息，该信息用于生成诸如高偏置直方图的信息的表示。在本发明方法的第一实施例中，保持与销售高于阈值的所有项目相关联的信息以及项目的近似计数。阈值的适当选择限制了需要维护的信息量，从而以高概率生成信息的准确表示。在本发明方法的第二实施例中，用于产生高偏差直方图的信息通过动态调整阈值而被保持在固定的存储器分配中，该阈值用于确定信息在数据库中被保留的概率。

8. 发明授权

US06591291B1 System and method for providing anonymous remailing and filtering of electronic mail 失效
标题翻译：提供电子邮件匿名退款和过滤的系统和方法
公开(公告)号：US06591291B1
公开(公告)日：2003-07-08
申请号：US09041209
申请日：1998-03-12
申请人： Eran Gabber , Phillip B. Gibbons , David Morris Kristol , Yossi Matias , Alain J. Mayer
发明人： Eran Gabber , Phillip B. Gibbons , David Morris Kristol , Yossi Matias , Alain J. Mayer
IPC分类号： G06F1338
CPC分类号： H04L51/28 , G06Q10/107 , H04L29/06 , H04L29/12009 , H04L29/12594 , H04L51/12 , H04L51/14 , H04L61/3065 , H04L63/0407 , H04L63/0435 , H04L69/04
摘要： A system for, and method of, generating an alias source address for an electronic mail (“e-mail”) message having a real source address and a destination address and a computer network, such as the Internet, including the system or the method. In one embodiment, the system includes an alias source address generator that employs the destination address to generate the alias source address. The system further includes an alias source address substitutor that substitutes the alias source address for the real source address. This removes the real source address from the e-mail message and thereby renders the sender, located at the real source address, anonymous. Further-described are systems and methods for forwarding reply e-mail and filtering reply e-mail based on alias source address.
摘要翻译：用于生成具有真实源地址和目的地地址的电子邮件（“电子邮件”）消息的别名源地址的系统和方法以及诸如因特网的计算机网络，包括系统或方法。在一个实施例中，系统包括使用目的地地址来生成别名源地址的别名源地址生成器。该系统还包括将别名源地址替换为实际源地址的别名源地址替换器。这将从电子邮件消息中删除真实的源地址，从而使位于真实源地址的发件人匿名。进一步描述了基于别名源地址转发回复电子邮件和过滤回复电子邮件的系统和方法。

9. 发明授权

US06434590B1 Methods and apparatus for scheduling parallel processors 失效
标题翻译：调度并行处理器的方法和装置
公开(公告)号：US06434590B1
公开(公告)日：2002-08-13
申请号：US09053873
申请日：1998-04-01
申请人： Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Girija J. Narlikar
发明人： Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Girija J. Narlikar
IPC分类号： G06F900
CPC分类号： G06F9/5066 , G06F2209/5021
摘要： A parallel processing method involves the steps of determining a sequential ordering of tasks for processing, assigning priorities to available tasks on the basis of the earliest and then later in the sequential ordering, selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and executing the tasks in the groups in the parallel processing elements. The determining step establishes an ordering with a specific predetermined sequential schedule that is independent of the parallel execution, and the assigning step assigns priorities for parallel execution on the basis of the sequential schedule that is independent of the parallel execution.
摘要翻译：并行处理方法包括以下步骤：确定用于处理的任务的顺序排序，基于顺序排序中的最早然后稍后的顺序为可用任务分配优先级，选择大于总数的可用并行处理来自具有最高优先级的所有可用任务的元素，将所选择的任务划分成等于可用数量的并行处理元素的多个组，以及在并行处理元素中执行组中的任务。确定步骤建立具有独立于并行执行的特定预定顺序调度的排序，并且分配步骤基于独立于并行执行的顺序调度分配用于并行执行的优先级。

10. 发明授权

US07047230B2 Distinct sampling system and a method of distinct sampling for optimizing distinct value query estimates 失效
标题翻译：不同的抽样系统和不同抽样的方法来优化不同的价值查询估计
公开(公告)号：US07047230B2
公开(公告)日：2006-05-16
申请号：US10237993
申请日：2002-09-09
申请人： Phillip B. Gibbons
发明人： Phillip B. Gibbons
IPC分类号： G06F17/30
CPC分类号： G06F17/30536 , G06F17/30457 , G06F17/30489 , Y10S707/99932 , Y10S707/99944
摘要： For use with a database that accommodates distinct value queries having predicates, a distinct sampling system and a method of distinct sampling. In one embodiment, the distinct sampling system includes a scanning subsystem that is configured to scan each row in the database for a distinct target attribute, employ a hash function to map the distinct target attribute to an attribute priority level, maintain random samples of each row based on a sample priority level and a sample size, and produce a distinct sample therefrom. The distinct sampling system further includes a distinct query estimator that is configured to receive the distinct value queries, cause the distinct value queries to be executed on the distinct sample to retrieve a result, and adjust the result to produce a distinct estimate therefrom.
摘要翻译：用于容纳具有谓词的不同值查询的数据库，独特的采样系统和不同采样的方法。在一个实施例中，不同采样系统包括扫描子系统，其被配置为扫描数据库中的每一行以获得不同的目标属性，采用散列函数将不同的目标属性映射到属性优先级，维护每行的随机采样基于样本优先级和样本大小，并从中产生不同的样本。不同的采样系统还包括被配置为接收不同值查询的不同查询估计器，导致在不同样本上执行不同值查询以检索结果，并且调整结果以从其产生不同的估计。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式