公开(公告)号：US20070027837A1

公开(公告)日：2007-02-01

申请号：US11190947

申请日：2005-07-28

申请人： Marcel Kutsch ,  Volker Markl ,  Nimrod Megiddo ,  Tam Minh Tran

发明人： Marcel Kutsch ,  Volker Markl ,  Nimrod Megiddo ,  Tam Minh Tran

IPC分类号： G06F17/30

CPC分类号： G06F17/30469 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A method for consistent selectivity estimation based on the principle of maximum entropy (ME) is provided. The method efficiently exploits all available information and avoids the bias problem. In the absence of detailed knowledge, the ME approach reduces to standard uniformity and independence assumptions. The disclosed method, based on the principle of ME, is used to improve the optimizer's cardinality estimates by orders of magnitude, resulting in better plan quality and significantly reduced query execution times.

摘要翻译： 提供了一种基于最大熵原理（ME）的一致选择性估计方法。 该方法有效地利用了所有可用信息，避免了偏差问题。 在没有详细知识的情况下，ME方法减少到标准统一性和独立性假设。 所公开的方法，基于ME的原理，用于提高优化器的基数估计数量级，导致更好的计划质量和显着减少的查询执行时间。

公开(公告)号：US07167953B2

公开(公告)日：2007-01-23

申请号：US11151363

申请日：2005-06-13

申请人： Nimrod Megiddo ,  Dharmendra Shantilal Modha

发明人： Nimrod Megiddo ,  Dharmendra Shantilal Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/123 ,  G06F12/122 ,  G06F12/127 ,  G06F2212/502

摘要： An adaptive replacement cache policy dynamically maintains two lists of pages, a recency list and a frequency list, in addition to a cache directory. The policy keeps these two lists to roughly the same size, the cache size c. Together, the two lists remember twice the number of pages that would fit in the cache. At any time, the policy selects a variable number of the most recent pages to exclude from the two lists. The policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time. It achieves such online, on-the-fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively.

摘要翻译： 自适应替换高速缓存策略除了缓存目录之外，还动态维护两个页面列表，新近度列表和频率列表。 该策略将这两个列表大致相同的大小，缓存大小c。 一起，两个列表记住了适合缓存的页面数量的两倍。 在任何时候，策略都会选择要从两个列表中排除的最新页面的可变数量。 该策略自适应地决定响应于不断变化的工作负载，在任何给定时间，来自每个列表的顶页数量将保持在高速缓存中。 它通过使用允许策略来快速有效地跟踪工作负载的学习规则来实现在线，即时的适应。

公开(公告)号：US06996676B2

公开(公告)日：2006-02-07

申请号：US10295507

申请日：2002-11-14

申请人： Nimrod Megiddo ,  Dharmendra Shantilal Modha

发明人： Nimrod Megiddo ,  Dharmendra Shantilal Modha

IPC分类号： G06F12/00

CPC分类号： G06F12/123 ,  G06F12/122 ,  G06F12/127 ,  G06F2212/502

摘要： An adaptive replacement cache policy dynamically maintains two lists of pages, a recency list and a frequency list, in addition to a cache directory. The policy keeps these two lists to roughly the same size, the cache size c. Together, the two lists remember twice the number of pages that would fit in the cache. At any time, the policy selects a variable number of the most recent pages to exclude from the two lists. The policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time. It achieves such online, on-the-fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively. This allows the policy to balance between recency and frequency in an online and self-tuning fashion, in response to evolving and possibly changing access patterns. The policy is also scan-resistant. It allows one-time-only sequential read requests to pass through the cache without flushing pages that have temporal locality. The policy is extremely simple to implement and requires only constant-time overhead per request. The policy has negligible space overhead.

摘要翻译： 自适应替换高速缓存策略除了缓存目录之外，还动态维护两个页面列表，新近度列表和频率列表。 该策略将这两个列表大致相同的大小，缓存大小c。 一起，两个列表记住了适合缓存的页面数量的两倍。 在任何时候，策略都会选择要从两个列表中排除的最新页面的可变数量。 该策略自适应地决定响应于不断变化的工作负载，在任何给定时间，来自每个列表的顶页数量将保持在高速缓存中。 它通过使用允许策略来快速有效地跟踪工作负载的学习规则来实现在线，即时的适应。 这允许该策略以在线和自调节方式平衡新近度和频率，以响应不断变化和可能改变的访问模式。 该政策也是防扫描的。 它允许一次性顺序读取请求通过缓存，而不刷新具有时间局部性的页面。 该策略实现起来非常简单，只需要每个请求定时开销。 该政策的空间开销微乎其微。

公开(公告)号：US06957224B1

公开(公告)日：2005-10-18

申请号：US09659261

申请日：2000-09-11

申请人： Nimrod Megiddo ,  Kevin S. McCurley

发明人： Nimrod Megiddo ,  Kevin S. McCurley

IPC分类号： G06F17/30

CPC分类号： G06F17/30876 ,  G06F17/30902 ,  H04L67/02 ,  H04L67/2814 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99945

摘要： A system, method and computer program product for providing links to remotely located information in a network of remotely connected computers. The system may or may not include a server providing an interface between shorthand codes and corresponding original files. If the server is included, a uniform resource locator (URL) is registered with a server. A shorthand link is associate with the registered URL. The associated shorthand link and URL are logged in a registry database. When a request is received for a shorthand link, the registry database is searched for an associated URL. If the shorthand link is found to be associated with an URL, the URL is fetched, otherwise an error message is returned. If the server is not included, all URLs located at a root page may be listed and associated with shorthand keys or links. Associated files and keys are indexed in an index file. The shorthand codes or keys are combined with the root page to form shorthand URLs. Requests are made for the shorthand URLs and the index file is searched for the requested shorthand URL. If the requested shorthand URL is encountered, the corresponding file is returned; otherwise, an error message is returned.

摘要翻译： 一种系统，方法和计算机程序产品，用于向远程连接的计算机的网络中的远程定位的信息提供链接。 系统可以包括也可以不包括提供速写代码和对应的原始文件之间的接口的服务器。 如果包含服务器，则会向服务器注册统一的资源定位符（URL）。 速记链接与注册的URL相关联。 关联的速记链接和URL记录在注册表数据库中。 当收到快速链接的请求时，会搜索注册表数据库中的相关联的URL。 如果发现速记链接与URL相关联，则会获取该URL，否则返回错误消息。 如果不包括服务器，则可以列出位于根页面的所有URL，并与速记键或链接相关联。 关联的文件和密钥在索引文件中进行索引。 速写代码或键与根页面组合以形成简写URL。 针对速记URL提供请求，并搜索索引文件以获取请求的简写URL。 如果遇到请求的速记URL，则返回相应的文件; 否则返回错误信息。

公开(公告)号：US06892181B1

公开(公告)日：2005-05-10

申请号：US09658632

申请日：2000-09-08

申请人： Nimrod Megiddo ,  Xiaoming Zhu

发明人： Nimrod Megiddo ,  Xiaoming Zhu

IPC分类号： G06Q30/02 ,  G06F17/60

CPC分类号： G06Q30/02 ,  G06Q30/0242 ,  G06Q30/0272 ,  G06Q30/0277

摘要： A system and method for improving the effectiveness of web advertising by allowing a user to return and request a previously displayed ad that appeals to the user. Generally, the system employs an intelligent browser cache maintained within a user's terminal to keep web pages in cache and maintain information about hyperlinks contained therein. Furthermore, the system allows for the storing of ads in a bookmark memory without clicking on the ads. The bookmark memory is either permanently maintained or temporarily stored for a predetermined time period at the user's terminal to allow the user view all the stored ads at a later time. The system further includes an algorithm for computing the differences between previously visited pages stored in the intelligent browser cache and a new page in terms of their hyperlinks. Presented to the user in separate windows are all the ads from both the old and new pages to aid the user in deciding whether to click and visit a different page or to save the displayed page for later use. Finally, the system permits the user to request for ads previously displayed at a particular position by pointing his mouse to the current ad at such a location.

摘要翻译： 一种用于通过允许用户返回并请求先前显示的吸引用户的广告来提高网络广告的有效性的系统和方法。 通常，系统采用在用户终端内维护的智能浏览器缓存来将网页保持在高速缓存中并且保持关于其中包含的超链接的信息。 此外，该系统允许在书签存储器中存储广告而不点击广告。 书签存储器在用户终端处永久维护或暂时存储预定时间段，以允许用户在稍后的时间查看所有存储的广告。 该系统还包括用于计算存储在智能浏览器高速缓存中的先前访问页面与其超链接之间的新页面之间的差异的算法。 在单独的窗口中向用户呈现来自旧页面和新页面的所有广告，以帮助用户决定是否点击并访问其他页面，或者保存显示的页面供以后使用。 最后，该系统允许用户通过将鼠标指向在该位置处的当前广告来请求先前在特定位置显示的广告。

公开(公告)号：US06745231B1

公开(公告)日：2004-06-01

申请号：US09634547

申请日：2000-08-08

申请人： Nimrod Megiddo

发明人： Nimrod Megiddo

IPC分类号： G06F1516

CPC分类号： H04L63/18 ,  H04L51/00

摘要： Encrypted e-mails that reside in e-mail service providers servers or a gateway machines can be compromised and deciphered with advances in technology for breaking encryption codes. Significant security can be achieved by encrypting the message, splitting message, and transmitting the individual fragments via a set of unique e-mail servers. At the receivers end, the message can be reconstructed from the individual pieces and then decrypted and displayed to the recipient.

摘要翻译： 驻留在电子邮件服务提供商服务器或网关机器中的加密电子邮件可能会受到破坏和解密，从而破坏加密代码的技术进步。 可以通过加密消息，分割消息以及通过一组独特的电子邮件服务器传送各个片段来实现重要的安全性。 在接收者端，消息可以从各个部分重建，然后被解密并显示给收件人。

公开(公告)号：US06574676B1

公开(公告)日：2003-06-03

申请号：US09481255

申请日：2000-01-11

申请人： Nimrod Megiddo

发明人： Nimrod Megiddo

IPC分类号： G06F1314

CPC分类号： G06F3/0601 ,  G06F2003/0697

摘要： A system and method that utilize a scheduling algorithm to reorder queued I/O commands in rotating disk drives. The reordering is implemented by selecting commands based on a probabilistic approach that minimizes the expected next command access time. Thus, the scheduling algorithm allows data to be accessed in the shortest possible expected time, and maximizes the throughput of the drive. The scheduling algorithm improves the I/O average access time by estimating the expected access time (EAT) for the queued commands, and by reordering these commands so that the command with the least expected access time (LEAT) is executed first. The scheduling algorithm weights the possible access times of commands stored in the scheduling queue, and accounts for the probability of executing a command during a first possible revolution or cycle, as well as the probability of executing the command in the second possible revolution. Both of these probabilities are taken into consideration in reaching a final determination as to the queue order of the commands. This allows for taking calculated risks in scheduling commands so as to minimize long-term average latency.

摘要翻译： 利用调度算法重新排列旋转磁盘驱动器中排队的I / O命令的系统和方法。 通过基于最小化预期的下一个命令访问时间的概率方法来选择命令来实现重新排序。 因此，调度算法允许以尽可能短的预期时间访问数据，并且使驱动器的吞吐量最大化。 调度算法通过估计排队命令的预期访问时间（EAT）和重新排序这些命令来改善I / O平均访问时间，以便首先执行具有最少预期访问时间（LEAT）的命令。 调度算法对存储在调度队列中的命令的可能访问时间进行加权，并且考虑在第一可能的转动或周期期间执行命令的概率以及在第二次可能的转动中执行命令的概率。 在对命令的队列顺序进行最终确定时，考虑到这两个概率。 这允许在调度命令中获取计算的风险，以便最小化长期平均延迟。

公开(公告)号：US06559863B1

公开(公告)日：2003-05-06

申请号：US09503044

申请日：2000-02-11

申请人： Nimrod Megiddo

发明人： Nimrod Megiddo

IPC分类号： G09G500

CPC分类号： H04L12/1827 ,  H04M3/568 ,  H04N7/15 ,  H04N7/157

摘要： A system and method is provided that allows participants in an electronic conference room to move to any spatial location in the electronic conference room by simply clicking and dragging, using a computer mouse, a graphical image representing the participant to any location in the electronic conference room. This allows participants to form small groups for communicating similar to a cocktail party situation. A communication media allows participants to communicate with one another within their particular groups. The participants can communicate though the graphical images either visually, audibly or both visually and audibly. Each user is provided visually with captions of other groups, which is reduced in size depending on the distance that particular group is from the user's location within the electronic conference room. In addition, each main user is provided with audible signals from other groups, which is attenuated based on the distance that particular group is from the user's location within the electronic conference room.

摘要翻译： 提供了一种系统和方法，其允许电子会议室中的参与者移动到电子会议室中的任何空间位置，只需使用计算机鼠标将代表参与者的图形图像点击并拖动到电子会议室中的任何位置 。 这样就可以让参与者组织小组来进行类似鸡尾酒会的情况的沟通。 通信媒体允许参与者在其特定组内彼此通信。 参与者可以通过视觉，听觉或视觉和听觉两者在图形图像之间进行通信。 每个用户被视觉地提供其他组的标题，根据特定组距离用户在电子会议室内的位置的距离而减小其他组的大小。 此外，每个主要用户被提供有来自其他组的可听信号，其基于特定组距离电子会议室内的用户位置的距离被衰减。

公开(公告)号：US6148295A

公开(公告)日：2000-11-14

申请号：US560

申请日：1997-12-30

申请人： Nimrod Megiddo ,  Uri Shaft

发明人： Nimrod Megiddo ,  Uri Shaft

IPC分类号： G06F17/30 ,  G06K9/62

CPC分类号： G06F17/30598 ,  G06F17/30256 ,  G06F17/30327 ,  G06F17/30483 ,  G06K9/6276 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A method for determining k nearest-neighbors to a query point in a database in which an ordering is defined for a data set P of a database, the ordering being based on l one-dimensional codes C.sub.1, . . . , C.sub.1. A single relation R is created in which R has the attributes of index-id, point-id and value. An entry (j,i,C.sub..epsilon.j (p.sub.i)) is included in relation R for each data point p.sub.i .EPSILON.P, where index-id equals j, point-id equals i, and value equals C.sub..epsilon.j (p.sub.i). A B-tree index is created based on a combination of the index-id attribute and the value attribute. A query point is received and a relation Q is created for the query point having the attributes of index-id and value. One tuple is generated in the relation Q for each j, j=1, . . . , l, where index-id equals j and value equals C.sub..epsilon.j (q). A distance d is selected. The index-id attribute for the relation R of each data point p.sub.i is compared to the index-id attribute for the relation Q of the query point. A candidate data point p.sub.i is selected when the comparison of the relation R of a data point p.sub.i to the index-id attribute for the relation Q of the query point is less than the distance d. Lower bounds are calculated for each cube of the plurality of cubes that represent a minimum distance between any point in a cube and the query point. Lastly, k candidate data points p.sub.i are selected as k nearest-neighbors to the query point.

摘要翻译： 一种用于确定数据库中的查询点的k个最近邻的方法，其中为数据库的数据集P定义排序，排序基于l个一维码C1。 。 。 ，C1。 创建单个关系R，其中R具有index-id，point-id和value的属性。 对于每个数据点pi EPSILON P，其中index-id等于j，point-id等于i，并且值等于C epsilon（pi），则在关系R中包括条目（j，i，C epsilon j（pi））。 基于index-id属性和value属性的组合创建B树索引。 接收到一个查询点，并为具有index-id和value属性的查询点创建一个关系Q。 在每个j，j = 1的关系Q中产生一个元组。 。 。 ，l，其中index-id等于j，值等于C epsilon（q）。 选择距离d。 将每个数据点pi的关系R的index-id属性与查询点的关系Q的index-id属性进行比较。 当数据点pi的关系R与查询点的关系Q的index-id属性的比较小于距离d时，选择候选数据点pi。 对于表示多维数据集中的任何点与查询点之间的最小距离的多个立方体中的每个立方体计算下限。 最后，将k个候选数据点pi选为查询点的k个最近邻。

公开(公告)号：US6058266A

公开(公告)日：2000-05-02

申请号：US881883

申请日：1997-06-24

申请人： Nimrod Megiddo ,  Vivek Sarkar

发明人： Nimrod Megiddo ,  Vivek Sarkar

IPC分类号： G06F9/45

CPC分类号： G06F8/452 ,  G06F8/443

摘要： An integer programming formulation for weighted loop fusion is presented. Loop fusion is a well-known program transformation that has shown to be effective in reducing loop overhead and improving register and cache locality. Weighted loop fusion is the problem of finding a legal partition of loop nests into fusible clusters so as to minimize the total inter-cluster edge weights. Past work has shown that the weighted loop fusion problem is NP-hard. Despite the NP-hardness property, the present invention provides optimal solutions that may be found efficiently, in the context of an optimizing compiler, for weighted loop fusion problem sizes that occur in practice. An integer programming formulation for weighted loop fusion with a problem size (number of variables and constraints) that is linearly proportional to the size of the input weighted loop fusion problem is also presented. The integer programming formulation may be solved efficiently using a general integer programming package. Alternatively, a custom branch-and-bound procedure for the integer programming formulation is presented that is more efficient than the procedures used in general integer programming.

摘要翻译： 提出了一种用于加权环融合的整数规划公式。 循环融合是一种众所周知的程序转换，已经显示出有效减少循环开销和改进寄存器和缓存位置。 加权环融合是将环巢的合法分区发现到易熔簇中的问题，以便使簇间边缘权重的总体最小化。 过去的工作表明，加权回路融合问题是NP-hard。 尽管具有NP硬度特性，本发明提供了在优化编译器的上下文中有效发现用于在实践中出现的加权环融合问题尺寸的最佳解决方案。 还提出了具有与输入加权环融合问题的大小成线性比例的问题大小（变量和约束的数量）的加权环融合的整数规划公式。 可以使用通用整数规划包有效地解决整数规划公式。 或者，提出了整数规划公式的自定义分支和绑定过程，其比在一般整数规划中使用的过程更有效。