Microsoft Technology Licensing, LLC

Anton Mityagin

Kumar Hemachandra Chellapilla

Kristin E Lauter

Denis X Charles

David Maxwell Chickering

Xuanhui Wang

Brian LaMacchia

Edith Law

Christopher A Meek

Timothy S Paek

Paul Nathan Bennett

Asela J Gunawardana

Ewa Dominowska

David Max Chickering

Aparna Lakshmiratan

Reid Andersen

Ilya Mironov

Yaacov Nissim Kobliner

Matt Jacobsen

Systems, methods, and computer storage media having computer-executable instructions embodied thereon that facilitate evaluation of digital content preferences are provided. A user is presented with items of digital content and permitted to manipulate the arrangement of the digital content items in the context of a layout area. Based on the user's manipulation of the digital content items, a user preference regarding an arrangement of digital content, such as a location preference, a position preference, and/or a usage preference, is identified. In embodiments, such a user preference can be utilized to later display digital content to a user in accordance therewith.

Evaluating preferences of content on a webpage

Systems and methods allow an on-line game to extract information relevant to a specific need of a game platform or service platform. The specific need relates to management and use of digital content, and is addressed by designing and playing an on-line collaborative game. The rules of the game intend to solve a specific task dictated by the specific need. Players' responses to the game generate a wealth of information related to a specific task objective, such as ranking, sorting, and evaluating a set of digital content items. To compel participation in a game, players can be rewarded with monetary value rewards. As a game illustration, an image selection game (ISG) that exploits human contextual inference is described in detail. The information extracted from ISG is a list of key-image associations, relevant for the task of image sorting and ranking.

Information collection during game play

A game description language is provided for human computation games, as well as a game platform or generator component that can generate the code base for the game. The game description language and schema framework can be used to represent the game logic and synchronization patterns of a human computation game. The automated code generation tool takes a file, e.g., a file made from the above game description language, or the like, as an input and generates a code base for the corresponding human computation game. These tools allow a prototype of a human computation game to be generated within minutes.

Arrangement for building and operating human-computation and other games

A human or hand-labeled ranking of URL results for a search query is compared against actual click data for the respective query/URL pairs (e.g., which URLs were actually clicked on by users when the URLs were presented to users when the search query was run in the real world). The human ranking or ordering of the URL results (e.g., pre-existing relevance ranking) for the query can then be adjusted, if necessary, based upon the real world click data (e.g., click relevance ranking). The modified pre-existing relevance ranking can be used in providing future search results.

Web searching

Technologies are described herein for constructing a minimal perfect hash function. According to embodiments, a hash table is constructed by double hashing each of the strings in a set of strings. A computed double hash value is utilized to identify an empty location in the hash table for each string. A signature for each string is stored in the empty location of the hash table identified for the string. In order to obtain a minimal perfect hash value for an input string, the input string is iteratively double hashed until a location is identified in the hash table that contains a signature corresponding to the input string. The minimal perfect hash value is an integer value identifying the location in the hash table that contains the signature corresponding to the input string.

Minimal perfect hash functions using double hashing

An exemplary method includes receiving a request to register a peer in a peer-to-peer system; generating or selecting a transaction key for the peer; storing the transaction key in association with registration information for the peer; transmitting the transaction key to the peer and, in response to a request to perform a desired peer-to-peer transaction by another peer, generating a token, based at least in part on the transaction key. Such a token allows for secure transactions in a peer-to-peer system including remote storage of data and retrieval of remotely stored data. Other exemplary techniques are also disclosed including exemplary modules for a peer-to-peer server and peers in a peer-to-peer system.

Security architecture for peer-to-peer storage system

AKE with derived ephemeral keys is described. In one aspect, a first party computes a derived ephemeral public-key based on a derived ephemeral secret key and a mathematical group. The derived ephemeral secret key is based on an ephemeral secret key and a long-term secret key. The first party generates a session key for secure exchange of information with a second party. The session key is generated using the derived ephemeral secret key and a second party derived ephemeral public-key key to demonstrate to the second party that the first party possesses the long-term secret key.

Authenticated key exchange with derived ephemeral keys

Systems and methods are described for trapdoor pairing. In one implementation, a trapdoor pairing is a cryptographic primitive generated by determining a bilinear pairing between an elliptic curve group and another group and selecting a parameter of the bilinear pairing, such as a group order or an isogeny between curves, to be a key for generating and evaluating the bilinear pairing. Trapdoor pairing allows construction of a group in which the Decisional Diffie-Hellman (DDH) problem is computationally infeasible given only the description of the group, but is easy given the secret key. Exemplary trapdoor pairing constructions have general applicability to cryptography and also lend themselves more specifically to certain special practical implementations, such as public key cryptography and certificate authority infrastructures.

Trapdoor pairings

A processing device and method may be provided for determining whether a zero search result may be produced with respect to a search for a document including all words of a word group. An index, with respect to words included in a group of documents, may be searched for documents including all words of the word group when a zero search result is determined not likely to occur with respect to the search for the document including all of the words of the word group. A method for creating multiple types of data structures corresponding to word grouping collections may further be provided to store occurrence information indicating a likelihood of a presence of a document including all words of a word group.

Detecting zero-result search queries

Key confirmed (KC) authenticated key exchange (AKE) with derived ephemeral keys protocol using a mathematical group is described. In one aspect, a first party, using the mathematical group, determines whether a second party has received information to compute an agreed session key value for exchanging information securely with the first party. At least a subset of the received information is computed using derived ephemeral keys of the first and second parties. The first party generates the agreed session key value only when the second party has demonstrated receipt of the information.

Key confirmed authenticated key exchange with derived ephemeral keys

Mislabeled URLs are identified and corrected based upon a click relevance ranking computed from user data comprising user click information. The click relevance ranking is formed by applying a set of relevance ordering rules to user log data aggregated by query and URL and by mapping the results of the relevance ordering rules into a linear ordering. For a given query, the aggregated user log data comprises a relative total number of impression, a relative total number of clicks received and a rank associated with the query/URL pair at the time of the total number of impressions and total number of clicks received. The click relevance ranking is used to identify and correct mislabeled query/URL pairs of other rankings according to a number of disclosed methods.

A minimal perfect hash function can be created for input data by dividing the input data into multiple collections, with each collection comprising fewer elements that the input data as a whole. Subsequently, minimal perfect hash functions can be created for each of the collections and the resulting hash values can be offset by a value equivalent to the number of input data in preceding collections. The minimal perfect hash function can, thereby, be derived in parallel and can consume substantially less storage space. To further save storage space, the internal state of each individual minimal perfect hash function can be further compressed using algorithms exploiting a skewed distribution of values in a lookup table comprising the internal state.

Scalable minimal perfect hashing

Multiple Bloom filters are generated to partition data between first and second disjoint data sets of elements. Each element in the first data set is assigned to a bucket of a first set of buckets, and each element in the second data set is assigned to a bucket of a second set of buckets. A Bloom filter is generated for each bucket of the first set of buckets. The Bloom filter generated for a bucket indicates that each element assigned to that bucket is part of the first data set, and that each element assigned to a corresponding bucket of the second set of buckets is not part of the first data set. Additionally, a Bloom filter corresponding to a subsequently received element can be determined and used to identify whether that subsequently received element is part of the first data set or the second data set.

Growing community of inventors

Woodinville, WA, United States of America

Anton Mityagin