公开(公告)号：US5721896A

公开(公告)日：1998-02-24

申请号：US644599

申请日：1996-05-13

申请人： Sumit Ganguly ,  Phillip B. Gibbons ,  Yossi Matias ,  Abraham Silberschatz

发明人： Sumit Ganguly ,  Phillip B. Gibbons ,  Yossi Matias ,  Abraham Silberschatz

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

CPC分类号： G06F17/30466 ,  G06F17/30469 ,  Y10S707/99932 ,  Y10S707/99935

摘要： A method of estimating the query size of two databases T and R is disclosed. The method uses a threshold value to categorize the databases as dense or sparse. A dense-dense procedure is then applied to the two databases to produce a dense-dense estimate (A.sub.d). A sparse-any procedure that suppresses the dense data items coming from database T is performed which produces a first sparse-any estimate (A.sub.s1). A second sparse-any estimate (A.sub.s2) is then produced by suppressing the dense data items from database R. Ultimately a query size estimate is produced by combining the dense-dense estimate, the first sparse-any estimate and the second sparse-any estimate.

摘要翻译： 公开了一种估计两个数据库T和R的查询大小的方法。 该方法使用阈值将数据库分类为密集或稀疏。 然后将密集程序应用于两个数据库以产生密集估计（Ad）。 执行稀疏的任何程序来抑制来自数据库T的密集数据项，其产生第一稀疏任意估计（As1）。 然后通过抑制来自数据库R的密集数据项产生第二稀疏 - 任何估计（As2）。最终，通过将密集估计，第一稀疏任意估计和第二稀疏任意估计结合密集估计来产生查询大小估计 。

公开(公告)号：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.

摘要翻译： 用于生成具有真实源地址和目的地地址的电子邮件（“电子邮件”）消息的别名源地址的系统和方法以及诸如因特网的计算机网络，包括系统或方法 。 在一个实施例中，系统包括使用目的地地址来生成别名源地址的别名源地址生成器。 该系统还包括将别名源地址替换为实际源地址的别名源地址替换器。 这将从电子邮件消息中删除真实的源地址，从而使位于真实源地址的发件人匿名。 进一步描述了基于别名源地址转发回复电子邮件和过滤回复电子邮件的系统和方法。

公开(公告)号：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.

摘要翻译： 并行处理方法包括以下步骤：确定用于处理的任务的顺序排序，基于顺序排序中的最早然后稍后的顺序为可用任务分配优先级，选择大于总数的可用并行处理 来自具有最高优先级的所有可用任务的元素，将所选择的任务划分成等于可用数量的并行处理元素的多个组，以及在并行处理元素中执行组中的任务。 确定步骤建立具有独立于并行执行的特定预定顺序调度的排序，并且分配步骤基于独立于并行执行的顺序调度分配用于并行执行的优先级。

公开(公告)号：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.

摘要翻译： 一种方法维护与有限存储器的数据库中的项目相关联的信息，该信息用于生成诸如高偏置直方图的信息的表示。 在本发明方法的第一实施例中，保持与销售高于阈值的所有项目相关联的信息以及项目的近似计数。 阈值的适当选择限制了需要维护的信息量，从而以高概率生成信息的准确表示。 在本发明方法的第二实施例中，用于产生高偏差直方图的信息通过动态调整阈值而被保持在固定的存储器分配中，该阈值用于确定信息在数据库中被保留的概率。

公开(公告)号：US06301640B2

公开(公告)日：2001-10-09

申请号：US09110110

申请日：1998-07-02

申请人： Rakesh D. Barve ,  Phillip B. Gibbons ,  Bruce K. Hillyer ,  Yossi Matias ,  Elizabeth Shriver ,  Jeffrey S. Vitter

发明人： Rakesh D. Barve ,  Phillip B. Gibbons ,  Bruce K. Hillyer ,  Yossi Matias ,  Elizabeth Shriver ,  Jeffrey S. Vitter

IPC分类号： G06F1200

CPC分类号： G06F3/0613 ,  G06F3/0656 ,  G06F3/0689 ,  G06F12/0866

摘要： A method for scheduling access of data blocks located in a computer system having a plurality of disk drives, each disk drive has a disk cache with a specified fence parameter value coupled to a host computer via a common bus. The method according to one embodiment, comprises the steps of: (a) sequentially accessing each of the disk drives for a predetermined number of iterations to retrieve a predetermined number of data blocks; (b) for a specified number of the iterations, transferring data located in the disk cache to be transferred to the common bus and requesting data corresponding to the following iteration to be transferred to the disk cache; and (c) repeating steps (a) and (b) until the predetermined iterations are completed.

摘要翻译： 一种用于调度位于具有多个磁盘驱动器的计算机系统中的数据块的访问的方法，每个磁盘驱动器具有通过公共总线耦合到主计算机的指定围栏参数值的磁盘高速缓存。 根据一个实施例的方法包括以下步骤：（a）以预定次数的迭代顺序访问每个磁盘驱动器以检索预定数量的数据块; （b）对于指定数量的迭代，将位于磁盘高速缓存中的数据传送到公共总线并请求与以下迭代对应的数据传送到磁盘高速缓存; 和（c）重复步骤（a）和（b），直到预定的迭代完成。

公开(公告)号：US6009409A

公开(公告)日：1999-12-28

申请号：US832409

申请日：1997-04-02

申请人： Micah A. Adler ,  Phillip B. Gibbons ,  Yossi Matias

发明人： Micah A. Adler ,  Phillip B. Gibbons ,  Yossi Matias

IPC分类号： G06F3/048 ,  G06F13/00 ,  G06F17/30 ,  G06Q30/02 ,  G06F17/60

CPC分类号： G06Q30/02 ,  G06Q30/0264 ,  G06Q30/0277

摘要： A system and method for scheduling and controlling delivery of advertising in a communications network and a communications network and remote computer program employing the system or the method. The system includes: (1) a time allocation controller that allocates time available in a particular advertising region in a display device of a remote computer between at least two advertisements as a function of one of a desired user frequency, a desired time frequency, or a desired geometry, for each of the at least two advertisements and (2) data communication controller, coupled to the time allocation controller, that delivers the at least two advertisements to said remote computer for display in the advertising region according to the allocating of the time.

摘要翻译： 一种用于在通信网络和采用该系统或方法的通信网络和远程计算机程序中调度和控制广告传送的系统和方法。 该系统包括：（1）时间分配控制器，其根据期望的用户频率，期望的时间频率或期望的用户频率之一，在至少两个广告之间分配在远程计算机的显示设备中的特定广告区域中可用的时间 用于所述至少两个广告中的每一个的所需几何形状;以及（2）耦合到所述时间分配控制器的数据通信控制器，所述数据通信控制器将所述至少两个广告传送到所述远程计算机，以根据所述广告区域的分配来显示在所述广告区域中 时间。

公开(公告)号：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.

摘要翻译： 在关系更新的情况下维护数据库中关系的近似直方图的技术。 直方图包括多个子集或“桶”，每个子集表示该关系属性的至少一个可能的值。 每个子集具有与其相关联的计数，指示属性的相应值的出现频率。 在更新关系后，将与子集关联的计数与阈值进行比较。 如果与给定子集相关联的计数超过阈值，则给定子集在其中间被分离成两个单独的子集。 在分离操作之后，组合具有最低计数的两个子集，使得如果子集的总组合计数不超过阈值，则在直方图中维持恒定数量的子集。 如果没有两个子集具有不超过阈值的总组合计数，则从该关系的随机样本重新计算直方图。 本发明基本上减少了从随机样本重新计算直方图的次数，并且特别适用于近似等深度和压缩的直方图。

公开(公告)号：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.

摘要翻译： 在存在关系更新的情况下，在数据库中维护关系随机抽样的技术。 该关系的随机样本被称为“后备样本”，并且在存在涉及该关系的插入，修改和删除操作的情况下保持该样本。 当一个新元组被插入关系中时，如果背景样本的大小低于上限，则将给定元组的样本添加到背景样本中。 否则，如果必须将新元组的样本插入到背景样本中以保持随机性或其他特征，则将随机选择的背衬样本的元组替换为新的元组。 当关系中的元组是修改操作的主题时，如果修改操作不影响使用后备样本的应用程序感兴趣的属性，则后备样本将保持不变。 否则，将更新背景样本中的元组样本中的值字段。 当从该关系中删除元组时，将删除该背景样本中该元组的任何样本。 如果这种去除导致背衬样品的尺寸低于预先指定的下限，则可以计算新的背衬样品。 背衬样本的尺寸可以与关系相比可以忽略不计，并且只需要非常频繁地修改。 因此，其在计算时间和存储空间方面的开销是最小的。

公开(公告)号：US5768594A

公开(公告)日：1998-06-16

申请号：US502625

申请日：1995-07-14

申请人： Guy E. Blelloch ,  Phillip B. Gibbons ,  Yossi Matias

发明人： Guy E. Blelloch ,  Phillip B. Gibbons ,  Yossi Matias

IPC分类号： G06F15/16 ,  G06F9/46 ,  G06F9/48 ,  G06F9/50 ,  G06F15/177 ,  G06F9/00

CPC分类号： G06F9/5066 ,  G06F2209/5021

摘要： Parallel processing is performed by determining sequential ordering of tasks for processing, assigning priorities to the tasks available on the basis of 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 parallel processing elements.

摘要翻译： 通过确定用于处理的任务的顺序排序来执行并行处理，基于顺序排序为可用任务分配优先级，从具有最高优先级的所有可用任务中选择大于可用并行处理元素总数的任务数量 将所选择的任务划分成等于可用数量的并行处理单元的多个组，并且在并行处理单元中执行任务。

公开(公告)号：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.

摘要翻译： 本发明提供一种与使用索引的数据库相关联的高速缓冲存储器使用的预取系统。 在一个实施例中，预取系统包括被配置为预取包含与数据库相关联的树结构的节点的索引的高速缓存行的搜索子系统。 另外，预取系统还包括被配置为基于树结构的第一和第二叶节点之间的索引预取距离来预取高速缓存行的扫描子系统。