公开(公告)号：US08775371B2

公开(公告)日：2014-07-08

申请号：US12616679

申请日：2009-11-11

Applicant: Ronald J. Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce G. Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita

Inventor： Ronald J. Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce G. Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita

IPC: G06F17/30

CPC classification number: G06F17/30578 ,  G06F17/30545

Abstract: Techniques are disclosed for synchronizing a primary data system with an auxiliary data system that processes data for the primary data system. In one embodiment, how current the primary data system and the auxiliary data system are is determined. Requests sent from the primary data system that were not processed by the auxiliary data system are determined. The requests are resent to the auxiliary data system for processing.

Abstract translation: 公开了用于使主数据系统与处理主数据系统的数据的辅助数据系统同步的技术。 在一个实施例中，确定主数据系统和辅助数据系统的当前时间。 确定从主数据系统发送的未被辅助数据系统处理的请求。 请求重新发送到辅助数据系统进行处理。

公开(公告)号：US08738673B2

公开(公告)日：2014-05-27

申请号：US12875615

申请日：2010-09-03

Applicant: Ronald Jason Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita ,  Paul Sherwood Taylor

Inventor： Ronald Jason Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita ,  Paul Sherwood Taylor

IPC: G06F17/30

CPC classification number: G06F17/30233 ,  G06F17/30584 ,  G06F17/30631

Abstract: Provided are techniques for partitioning a physical index into one or more physical partitions; assigning each of the one or more physical partitions to a node in a cluster of nodes; for each received document, assigning an assigned-doc-ID comprising an integer document identifier; and, in response to assigning the assigned-doc-ID to a document, determining a cut-off of assignment of new documents to a current virtual-index-epoch comprising a first set of physical partitions and placing the new documents into a new virtual-index-epoch comprising a second set of physical partitions by inserting each new document to a specific one of the physical partitions in the second set using one or more functions that direct the placement based on one of the assigned-doc-id, a field value derived from a set of fields obtained from the document, and a combination of the assigned-doc-id and the field value.

Abstract translation: 提供了用于将物理索引分割成一个或多个物理分区的技术; 将一个或多个物理分区中的每一个分配给节点簇中的节点; 对于每个接收到的文档，分配包括整数文档标识符的分配文档ID; 并且响应于将分配的文档ID分配给文档，确定新文档的分配到当前虚拟索引时期的截断，该当前虚拟索引时期包括第一组物理分区，并将新文档放入新的虚拟 - 指数 - 历元包括第二组物理分区，通过使用一个或多个基于所分配的文档ID中的一个来指导所述布局的功能，将每个新文档插入第二组中的特定一个物理分区 从文档获得的一组字段中导出的值以及分配的doc-id和字段值的组合。

公开(公告)号：US08209368B2

公开(公告)日：2012-06-26

申请号：US12134148

申请日：2008-06-05

Applicant: Kevin Scott Beyer ,  Sridhar Rajagopalan ,  Adriana Zubiri

Inventor： Kevin Scott Beyer ,  Sridhar Rajagopalan ,  Adriana Zubiri

IPC: G06F17/10

CPC classification number: G06F12/0864

Abstract: A dynamic Bloom filter comprises a cascaded set of Bloom filters. The system estimates or guesses a cardinality of input items, selects a number of hash functions based on the desired false positive rate, and allocates memory for an initial Bloom filter based on the estimated cardinality and desired false positive rate. The system inserts items into the initial Bloom filter and counts the bits set as they are inserted. If the number of bits set in the current Bloom filter reaches a predetermined target, the system declares the current Bloom filter full. The system recursively generates additional Bloom filters as needed for items remaining after the initial Bloom filter is filled; items are checked to eliminate duplicates. Each of the set of Bloom filters is individually queried to identify a positive or negative in response to a query. When the system is configured such that the false positive rate of each successive Bloom filter is decreased by one half, the system guarantees a false positive rate of at most twice the desired false positive rate.

Abstract translation: 一个动态的Bloom过滤器包括一个级联的Bloom过滤器。 系统估计或猜测输入项的基数，基于所需的假阳性率选择多个散列函数，并且基于估计的基数和期望的假阳性率为初始布隆过滤器分配存储器。 系统将项目插入到初始布隆过滤器中，并对插入的位进行计数。 如果当前布隆过滤器中设置的位数达到预定目标，则系统将声明当前布隆过滤器已满。 系统会根据需要在初始布隆过滤器填充后剩余的项目递归地生成其他布隆过滤器; 检查项目以消除重复。 每一组Bloom过滤器都被单独查询以识别响应于查询的正或负。 当系统被配置为使得每个连续的Bloom过滤器的假阳性率减少一半时，系统保证假阳性率为期望假阳性率的两倍。

公开(公告)号：US20120059823A1

公开(公告)日：2012-03-08

申请号：US12875615

申请日：2010-09-03

Applicant: Ronald J. Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce G. Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita ,  Paul S. Taylor

Inventor： Ronald J. Barber ,  Harish Deshmukh ,  Ning Li ,  Bruce G. Lindsay ,  Sridhar Rajagopalan ,  Roger C. Raphael ,  Eugene J. Shekita ,  Paul S. Taylor

IPC: G06F17/30

CPC classification number: G06F17/30233 ,  G06F17/30584 ,  G06F17/30631

Abstract: Provided are techniques for partitioning a physical index into one or more physical partitions; assigning each of the one or more physical partitions to a node in a cluster of nodes; for each received document, assigning an assigned-doc-ID comprising an integer document identifier; and, in response to assigning the assigned-doc-ID to a document, determining a cut-off of assignment of new documents to a current virtual-index-epoch comprising a first set of physical partitions and placing the new documents into a new virtual-index-epoch comprising a second set of physical partitions by inserting each new document to a specific one of the physical partitions in the second set using one or more functions that direct the placement based on one of the assigned-doc-id, a field value derived from a set of fields obtained from the document, and a combination of the assigned-doc-id and the field value.

Abstract translation: 提供了用于将物理索引分割成一个或多个物理分区的技术; 将一个或多个物理分区中的每一个分配给节点簇中的节点; 对于每个接收到的文档，分配包括整数文档标识符的分配文档ID; 并且响应于将分配的文档ID分配给文档，确定新文档的分配到当前虚拟索引时期的截断，该当前虚拟索引时期包括第一组物理分区，并将新文档放入新的虚拟 - 指数 - 历元包括第二组物理分区，通过使用一个或多个基于所分配的文档ID中的一个来指导所述布局的功能，将每个新文档插入第二组中的特定一个物理分区 从文档获得的一组字段中导出的值以及分配的doc-id和字段值的组合。

公开(公告)号：US20120042030A1

公开(公告)日：2012-02-16

申请号：US12855241

申请日：2010-08-12

Applicant: HARISH DESHMUKH ,  SRIDHAR RAJAGOPALAN ,  ROGER C. RAPHAEL ,  CHITRANG SHAH ,  PAUL S. TAYLOR

Inventor： HARISH DESHMUKH ,  SRIDHAR RAJAGOPALAN ,  ROGER C. RAPHAEL ,  CHITRANG SHAH ,  PAUL S. TAYLOR

IPC: G06F15/16

CPC classification number: H04L43/0817 ,  G06F11/0709 ,  G06F11/076 ,  H04L43/10 ,  H04L43/16

Abstract: Systems, methods and computer program products are disclosed for managing availability of a slave components executing in a distributed system. A master server and a heartbeat protocol may be provided. The heartbeat protocol may define state machines for the master server and/or the slave components. The master server and/or the slave components may act in accordance with the state machines to manage availability of the slave components in the distributed system.

Abstract translation: 公开了用于管理在分布式系统中执行的从属组件的可用性的系统，方法和计算机程序产品。 可以提供主服务器和心跳协议。 心跳协议可以定义主服务器和/或从组件的状态机。 主服务器和/或从属组件可以根据状态机来起作用以管理分布式系统中从属组件的可用性。

公开(公告)号：US08032732B2

公开(公告)日：2011-10-04

申请号：US12134125

申请日：2008-06-05

Applicant: Kevin Scott Beyer ,  Sridhar Rajagopalan

Inventor： Kevin Scott Beyer ,  Sridhar Rajagopalan

IPC: G06F12/00

CPC classification number: G06F17/10

Abstract: A cache-aware Bloom filter system segments a bit vector of a cache-aware Bloom filter into fixed-size blocks. The system hashes an item to be inserted into the cache-aware Bloom filter to identify one of the fixed-size blocks as a selected block for receiving the item and hashes the item k times to generate k hashed values for encoding the item for insertion in the in the selected block. The system sets bits within the selected block with addresses corresponding to the k hashed values such that accessing the item in the cache-aware Bloom filter requires accessing only the selected block to check the k hashed values. The size of the fixed-size block corresponds to a cache-line size of an associated computer architecture on which the cache-aware Bloom filter is installed.

Abstract translation: 一个缓存感知的Bloom过滤器系统将缓存感知的Bloom过滤器的位向量分成固定大小的块。 系统将要插入到缓存感知的布隆过滤器中的项目进行散列，以将固定大小块之一识别为用于接收项目的选定块，并将项目k次哈希，以产生用于编码项目以插入的k个哈希值 在所选的块中。 系统在所选择的块内设置与k个哈希值相对应的地址的位，使得访问缓存感知的Bloom过滤器中的项目只需要访问所选择的块来检查k个哈希值。 固定大小块的大小对应于其上安装有缓存感知布隆过滤器的关联计算机体系结构的高速缓存行大小。

公开(公告)号：US20080155229A1

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

申请号：US11614790

申请日：2006-12-21

Applicant: Kevin Scott Beyer ,  Sridhar Rajagopalan

Inventor： Kevin Scott Beyer ,  Sridhar Rajagopalan

IPC: G06F9/34

CPC classification number: G06F17/10

Abstract: A cache-aware Bloom filter system segments a bit vector of a cache-aware Bloom filter into fixed-size blocks. The system hashes an item to be inserted into the cache-aware Bloom filter to identify one of the fixed-size blocks as a selected block for receiving the item and hashes the item k times to generate k hashed values for encoding the item for insertion in the in the selected block. The system sets bits within the selected block with addresses corresponding to the k hashed values such that accessing the item in the cache-aware Bloom filter requires accessing only the selected block to check the k hashed values. The size of the fixed-size block corresponds to a cache-line size of an associated computer architecture on which the cache-aware Bloom filter is installed.

Abstract translation: 一个缓存感知的Bloom过滤器系统将缓存感知的Bloom过滤器的位向量分成固定大小的块。 系统将要插入到缓存感知的布隆过滤器中的项目进行散列，以将固定大小块之一识别为用于接收项目的选定块，并将项目k次哈希，以产生用于编码项目以插入的k个哈希值 在所选的块中。 系统在所选择的块内设置与k个哈希值相对应的地址的位，使得访问缓存感知的Bloom过滤器中的项目只需要访问所选择的块来检查k个哈希值。 固定大小块的大小对应于其上安装有缓存感知布隆过滤器的关联计算机体系结构的高速缓存行大小。

公开(公告)号：US07010526B2

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

申请号：US10141686

申请日：2002-05-08

Applicant: Matthew Denesuk ,  Daniel Frederick Gruhl ,  Kevin Snow McCurley ,  Sridhar Rajagopalan ,  Andrew S. Tomkins

Inventor： Matthew Denesuk ,  Daniel Frederick Gruhl ,  Kevin Snow McCurley ,  Sridhar Rajagopalan ,  Andrew S. Tomkins

IPC: G06F17/30

CPC classification number: G06F17/30864 ,  Y10S707/99936 ,  Y10S707/99942

Abstract: In a data mining system, data is gathered into a data store using, e.g., a Web crawler. The data is classified into entities. Data miners use rules to process the entities and append respective keys to the entities representing characteristics of the entities as derived from expert rules embodied in the miners. With these keys, characteristics of entities as defined by disparate expert authors of the data miners are identified for use in responding to complex data requests from customers.

公开(公告)号：US06343288B1

公开(公告)日：2002-01-29

申请号：US09268089

申请日：1999-03-12

Applicant: Bruce Gilbert Lindsay ,  Gurmeet Singh Manku ,  Sridhar Rajagopalan

Inventor： Bruce Gilbert Lindsay ,  Gurmeet Singh Manku ,  Sridhar Rajagopalan

IPC: G06F1730

CPC classification number: G06F17/30539 ,  G06F2216/03 ,  Y10S707/99932 ,  Y10S707/99936 ,  Y10S707/99937 ,  Y10S707/99942

Abstract: A space-efficient system and method for generating an approximate &phgr;-quantile data element of a data set in a single pass over the data set, without a priori knowledge of the size of the data set. The approximate &phgr;-quantile is guaranteed to lie within a user-specified approximation error &egr; of the true quantile being sought with a probability of at least 1−&dgr;, with &dgr; being a user-defined probability of failure. B buffers, each having a capacity of k elements, initially are filled with elements from the data set, with the values of b and k depending on approximation error e and the probability &dgr;. The buffers are then collapsed into an output buffer, with the remaining buffers then being refilled with elements, collapsed (along with the previous output buffer), and so on until the entire data set has been processed and a single output remains. The element of the output corresponding to the approximate quantile is then output as the approximate quantile. In later iterations (when the height of the tree is at least equal to a predetermined height that depends on &dgr; and &egr;), the data is sampled non-uniformly to populate the buffers to render the desired performance. Parallel processors can be used, with the final output buffers of the processors being sent to a collecting processor P0 as input buffers to the collecting processor P0.

Abstract translation: 一种空间有效的系统和方法，用于在数据集中的单次传递中生成数据集的近似分位数据元素，而无需对数据集的大小的先验知识。 大致的分位数被保证位于用至少1-delta的概率寻求的真实分位数的用户指定的近似误差εi中，其中Δ是用户定义的故障概率。 每个具有k个元素的容量的B缓冲器最初由数据集中的元素填充，其中b和k的值取决于近似误差e和概率delta。 缓冲区然后被折叠成输出缓冲区，剩余的缓冲区然后被元素重新填充（与先前的输出缓冲区一起），等等，直到整个数据集被处理并且保持单个输出。 然后输出对应于近似分位数的输出元素作为近似分位数。 在后面的迭代中（当树的高度至少等于取决于delta和epsi的预定高度时），数据被不均匀地采样以填充缓冲器以呈现期望的性能。 可以使用并行处理器，处理器的最终输出缓冲器被发送到收集处理器P0作为到采集处理器P0的输入缓冲器。

公开(公告)号：US20120259890A1

公开(公告)日：2012-10-11

申请号：US13526424

申请日：2012-06-18

Applicant: Matthew Denesuk ,  Daniel Frederick Gruhl ,  Sridhar Rajagopalan ,  Andrew S. Tomkins

Inventor： Matthew Denesuk ,  Daniel Frederick Gruhl ,  Sridhar Rajagopalan ,  Andrew S. Tomkins

IPC: G06F17/30

CPC classification number: G06F16/951 ,  G06F2216/03

Abstract: In a data mining system, data is gathered into a data store using, e.g., a Web crawler. The data is classified into entities. Data miners use rules to process the entities and append respective keys to the entities representing characteristics of the entities as derived from rules embodied in the miners. With these keys, characteristics of entities as defined by disparate expert authors of the data miners are identified for use in responding to complex data requests from customers.

Abstract translation: 在数据挖掘系统中，使用例如Web爬行器将数据收集到数据存储中。 数据分为实体。 数据挖掘者使用规则来处理实体，并将相应的密钥附加到代表矿工特征的实体的实体。 利用这些密钥，确定数据挖掘者的不同专家作者定义的实体的特征用于响应客户的复杂数据请求。