Cisco Technology, Inc.

Microsoft Technology Licensing, LLC

Massachusetts Institute of Technology

Other

Cisco Technology, Inc., C/o Robert Barr

Rina Panigrahy

Samar Sharma

Abhijit Patra

Sreenivas Gollapudi

Sriram Krishnan

Marc Alexander Najork

Mikhail Kapralov

Nagaraj Bagepalli

F Thomson Leighton

Daniel M Lewin

Matthew S Levine

David R Karger

Kunal Talwar

Rajesh Shenoy

Eric Lehman

Sanjay Jain

Ehud Wieder

Daniel Yu-Kwong Ng

Lincoln K Uyeda

Punit Bhargava

Jackie Liu

Atish Das Sarma

John Joseph Williams, Jr

Yinglian Xie

Ashwath Nagaraj

Chad E Verbowski

Suran Saminda De Silva

Awais Bin Nemat

Timothy Lewis Harrington

Ketan Arun Padwekar

Yoichi Hariguchi

Anh Tien Nguyen

Sunil Parthasarathy

William Nelson

Ding Yuan

Junfeng Yang

Timothy Harrington

A sparsifier is generated from a union of multiple spanners of a graph. The edges of the sparsifier are weighted based on a measure of connectivity called robust connectivity. The robust connectivity of a node pair is the highest edge sampling probability at which a distance between the pair is likely to drop below a specified length. Each spanner is generated from a subgraph of the graph that is generated using a decreasing sampling probability. For the weight of each edge, a spanner is determined where an estimated distance between the nodes associated with the edge is greater than a threshold distance. The sampling probability of the subgraph used to generate the spanner is an estimate of the robust connectivity of the edge. The weight of the edge is set to the inverse of the estimated robust connectivity.

Generating a sparsifier using graph spanners

A method for packing virtual machines onto host devices may calculate scarcity values for several different parameters. A host's scarcity for a parameter may be determined by multiplying the host's capacity for a parameter with the overall scarcity of that parameter. The sum of a host's scarcity for all the parameters determines the host's overall scarcity. Hosts having the highest scarcity are attempted to be populated with a group of virtual machines selected for compatibility with the host. In many cases, several different scenarios may be evaluated and an optimal scenario implemented. The method gives a high priority to those virtual machines that consume scarce resources, with the scarcity being a function of the available hardware and the virtual machines that may be placed on them.

Virtual machine packing method using scarcity

Architecture that provides a data structure to facilitate personalized ranking over recommended content (e.g., documents). The data structure approximates the social distance of the searching user to the content at query time. A graph is created of content recommended by members of the social network, where the nodes of the graph include content nodes (for the content) and recommending member nodes (for members of the social network who recommended the content). If a member recommends content, an edge is created between the member node and the content node. If a member is a 'friend' (tagged as related in some way) of another member, an edge is created between the two member nodes. Each node is converted to a lower dimensional feature set. Feature sets of the content are indexed and the feature set of the searching user is utilized to match and rank the search results at query time.

Social network recommended content and recommending members for personalized search results

Multiple data prediction strategies are received. Each data prediction strategy may predict a next data value in a sequence of data values with a corresponding confidence value. Rather than rely on a single prediction strategy, the predictions of each of the data prediction strategies are linearly combined to generate a single prediction that is more accurate and has a lower overall loss than any of the individual prediction strategies. Further, a deviation is calculated based on the values in the sequence of values that have been observed so far using a weighted sum that favors more recent values in the sequence over less recent values in the sequence. A prediction of the next value in the sequence is generated based on the combined strategies and the calculated deviation.

Predicting values in sequence

User accounts in a social networking application are divided into highly-connected accounts and regular accounts. A mapping of the highly-connected accounts to their friends, and a mapping of accounts to documents endorsed by the users associated with the accounts are stored on index servers of a search engine. When a query is received by a front-end server of the search engine, the front-end server determines if an account associated with the query is a highly-connected account. If it is, only an identifier of the account is sent to the index servers with the query. If it is not, however, then identifiers of all of the accounts that are friends with the account are sent with the query. The index servers then determine the documents that are endorsed by the friends of the account, and consider the determined documents when selecting documents that are responsive to the query.

Considering document endorsements when processing queries

To facilitate the estimation of relatedness between nodes of a graph, implementations estimate relatedness between nodes in a graph by pre-computing for a subset of sample nodes (e.g., center nodes) a plurality of transition probabilities between each sample node and each of the other nodes in the graph, and then later when queried the implementations calculate in real-time the resultant estimated transition probability between the first node and the second node through the at least one sample node based on the pre-computed transition probabilities.

Estimating relatedness in social network

Sketches are generated for each node in a graph. For undirected graphs, each sketch for a node may include an indicator of a node from a seed set of nodes and the shortest distance between the node and the indicated node. When a request is received for the shortest distance between two nodes of the graph, the sketches for each of the two nodes are retrieved, and nodes that are indicated in both of the sketches are determined. The distances between each of the two nodes and a determined node as indicated in the sketches is summed for each of the determined nodes, and the sum having the least distance is selected as the estimated shortest distance between the two nodes.

Estimating shortest distances in graphs using sketches

Relevant search results for a given query may be determined using click data for the query and the number of times the query is issued to a search engine. The number of clicks that a result receives for the given query may provide a feedback mechanism to the search engine on how relevant the result is for the given query. The frequency of a query along with the associated clicks provides the search engine with the effectiveness of the query in producing relevant results. Edges in a graph of queries versus results may be weighted in accordance with the click data and the efficiency to rank the search results provided to a user.

Semi-supervised part-of-speech tagging

The rank of nodes in a graph may be inferred from a calculated probability that each node in the graph appears in a single random walk of the graph. Short random walks may be generated for each node in the graph. The generated random walks may be combined to form a longer single random walk. Multiple single random walks may be generated in this fashion. The probability of each node appearing in a single random may be calculated from the generated single random walks. The rank of each node may then be inferred from the calculated probabilities.

Estimating rank on graph streams

A technique for automatically detecting and correcting configuration errors in a computing system. In a learning process, recurring event sequences, including e.g., registry access events, are identified from event logs, and corresponding rules are developed. In a detecting phase, the rules are applied to detected event sequences to identify violations and to recover from failures. Event sequences across multiple hosts can be analyzed. The recurring event sequences are identified efficiently by flattening a hierarchical sequence of the events such as is obtained from the Sequitur algorithm. A trie is generated from the recurring event sequences and edges of nodes of the trie are marked as rule edges or non-rule edges. A rule is formed from a set of nodes connected by rule edges. The rules can be updated as additional event sequences are analyzed. False positive suppression policies include a violation-consistency policy and an expected event disappearance policy.

Fingerprinting event logs for system management troubleshooting

The present invention provides a packet processing device and method. A parsing processor provides instruction-driven content inspection of network packets at 10-Gbps and above with a parsing engine that executes parsing instructions. A flow state unit maintains statefulness of packet flows to allow content inspection across several related network packets. A state-graph unit traces state-graph nodes to keyword indications and/or parsing instructions. The parsing instructions can be derived from a high-level application to emulate user-friendly parsing logic. The parsing processor sends parsed packets to a network processor unit for further processing.

Stateful flow of network packets within a packet parsing processor

Entries are arranged in hash tables with storage for multiple entries per bucket with entries being shifted among hash tables to make room for entries being added. A path is determined through a search of the hash tables to identify where to move entries during insert operations among the hash tables to make room for a data item being added. Entries are moved and a data item added according to the identified path. Many different types of searches may be used, such as breadth-first, depth-first, random walk, etc. Also, a free position at the end of the path may be identified by being a bucket having a lowest occupancy level in a first predetermined number of levels of the search, a first bucket encountered having space available or an occupancy level less than a predetermined threshold level, with the predetermined threshold level typically being less than that of a full bucket, etc.

Searching for a path to identify where to move entries among hash tables with storage for multiple entries per bucket during insert operations

A method is disclosed for identifying queries stored in a log which are semantically related to an input query that may include a large number of terms. A set of one or more subsequences are generated for each query stored in the log, and these sets of subsequences are stored in a lookup table. A set of one or more subsequences are also generated for the input query. The subsequences in the lookup table and of the input query are generated by hashing of the respective query terms to a value between 0 and 1 using a known technique of min-hashing. The present system then constructs the subsequences of the query using the k-min hashes of the query, where k is an integer based on the number of terms in the query.

Method of finding candidate sub-queries from longer queries

A method, computer program product, system and apparatus are presented for reducing wasted bandwidth due to supercasting multicast cells through a router switch fabric. In one embodiment of the present invention, signatures of a switch fabric destination address are generated and compared. A signature is an information-rich representation of the fabric destination address that is generated using the fabric destination address. Therefore, supercasting can be minimized by combining fabric destination addresses with like signatures. Aspects of the present invention include generating the signatures using random permutation maps of the set of switch fabric ports or determining intersections of a fabric destination address with a selection of subsets of the switch fabric ports. Signature-based solutions for supercast minimization can be performed in a time-efficient manner and be implemented online, while solutions that can generate a more optimal solution but may take a longer time to perform, such as row-clustering, can be implemented off-line. A further aspect of the invention, incorporates an off-line row-clustering supercast minimization method with an on-line signature-based supercast minimization method.

Constant time signature methods for scalable and bandwidth-efficient multicast

Growing community of inventors

Sunnyvale, CA, United States of America

Rina Panigrahy