Microsoft Technology Licensing, LLC

Shriraghav Kaushik

Arvind Arasu

Venkatesh Ganti

Surajit J Chaudhuri

Ravishankar Ramamurthy

Ramarathnam R Venkatesan

Donald Kossmann

Kenneth Hiroshi Eguro

Manas Rajendra Joglekar

Spyridon Blanas

Prasang Upadhyaya

Vivek Ravindranath Narasayya

Zhimin Chen

Gunjan Jha

Anish Das Sarma

Michaela Götz

Bee Chung Chen

Methods, systems, and computer-readable media are directed towards receiving, at an untrusted component, a query for a data store. The query includes a plurality of data operations. The data store is accessible by the untrusted component. A first proper subset of data operations is determined from the plurality of data operations that do not access sensitive data within the data store. A second proper subset of data operations is determined from the plurality of data operations that access sensitive data within the data store. The first proper subset of data operations is executed, at the untrusted component, to create first results. The second proper subset of data operations is sent to a trusted component for execution. Second results based on the sending the second proper subset of data operations are received from the trusted component. Results to the query are returned based on the first results and the second results.

Secure data processing on sensitive data using trusted hardware

The subject disclosure is directed towards secure query processing over encrypted database records without disclosing information to an adversary except for permitted information. In order to adapting semantic security to a database encryption scheme, a security model for all query processing is specified by a client and used to determine which information is permitted to be disclosed and which information is not permitted. Based upon the security model, a trusted, secure query processor transforms each query and an encrypted database into secure query results. Even though the adversary can view the secure query results during communication to the client, the adversary cannot determine any reliable information regarding the secure query results or the encrypted database.

Secure query processing over encrypted data

An active learning record matching system and method for producing a record matching package that is used to identify pairs of duplicate records. Embodiments of the system and method allow a precision threshold to be specified and then generate a learned record matching package having precision greater than this threshold and a recall close to the best possible recall. Embodiments of the system and method use a blocking technique to restrict the space of record matching packages considered and scale to large inputs. The learning method considers several record matching packages, estimates the precision and recall of the packages, and identifies the package with maximum recall having precision greater than equal to the given precision threshold. A human domain expert labels a sample of record pairs in the output of the package as matches or non-matches and this labeling is used to estimate the precision of the package.

Active learning of record matching packages

Techniques are described to leverage a set of sample or example matched pairs of strings to learn string transformation rules, which may be used to match data records that are semantically equivalent. In one embodiment, matched pairs of input strings are accessed. For a set of matched pairs, a set of one or more string transformation rules are learned. A transformation rule may include two strings determined to be semantically equivalent. The transformation rules are used to determine whether a first and second string match each other.

Learning string transformations from examples

A deduplication algorithm that provides improved accuracy in data deduplication by using aggregate and/or groupwise constraints. Deduplication is accomplished using only as many of these constraints that are satisfied rather than be imposed inflexibly as hard constraints. Additionally, textual similarity between tuples is leveraged to restrict the search space. The algorithm begins with a coarse initial partition of data records and continues by raising the similarity threshold until the threshold splits a given partition. This sequence of splits defines a rich space of alternatives. Over this space, an algorithm finds a partition of the input that maximizes constraint satisfaction. In the context of groupwise aggregation constraints for deduplication all SQL (structured query language) aggregates are allowed, including summation.

Leveraging constraints for deduplication

Example-driven creation of record matching queries. The disclosed architecture employs techniques that exploit the availability of positive (or matching) and negative (non-matching) examples to search through this space and suggest an initial record matching query. The record matching task is modeled as that of designing an operator tree obtained by composing a few primitive operators. This ensures that record matching programs be executable efficiently and scalably over large input relations. The architecture joins records across multiple (e.g., two) relations (e.g., R and S). The architecture exploits the monotonicity property of similarity functions for record matching in the relations, in that, any pair of matching records have a higher similarity value than non-matching record pairs on at least one similarity function.

Example-driven design of efficient record matching queries

Architecture that provides a data profile computation technique which employs key profile computation and data pattern profile computation. Key profile computation in a data table includes both exact keys as well as approximate keys, and is based on key strengths. A key strength of 100% is an exact key, and any other percentage in an approximate key. The key strength is estimated based on the number of table rows that have duplicated attribute values. Only column sets that exceed a threshold value are returned. Pattern profiling identifies a small set of regular expression patterns which best describe the patterns within a given set of attribute values. Pattern profiling includes three phases: a first phases for determining token regular expressions, a second phase for determining candidate regular expressions, and a third phase for identifying the best regular expressions of the candidates that match the attribute values.

Key profile computation and data pattern profile computation

Input set indexing for set-similarity lookups. The architecture provides input to an indexing process that enables more efficient lookups for large data sets (e.g., disk-based) without requiring a full scan of the input. A new index structure is provided, the output of which is exact, rather than approximate. The similarity of two sets is specified using a similarity function that maps two sets to a numeric value that represents similarity of the two sets. Threshold-based lookups are addressed where two sets are considered similar if the numeric similarity score is above a threshold. The structure efficiently identifies all input sets within a distance k (e.g., a hamming distance) of the query set. Additional information in the form of frequency of elements (the number of input sets in which an element occurs) is used to improve index performance.

Growing community of inventors

Bellevue, WA, United States of America

Shriraghav Kaushik