Efficient storage of related sparse data in a search index

• US 9,720,946 B2
• Filed: 10/24/2014
• Issued: 08/01/2017
• Est. Priority Date: 06/19/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Torbjrnsen, ystein, Heino, Jr., Christopher, Srinivasan, Sowmy, Wilhelm, Ryan
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US14/523,241
• Publication Number:
  US 20150370840A1
• Time in Patent Office: 1,012 Days
• Field of Search: 707744
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

Sparse data may be stored in a search index such that one or more data points related to a number of entities may be queriable. Upon detection of a data point related to an entity, an integer array may be created for the data point to store within a single column of the search index, the integer array including an identifier of the entity and a value associated with the data point. In response to receiving a request from a user to perform a query on the search index that includes the data point, the query may be transformed to a corresponding range based on the identifier of the entity. Upon execution of the query, the identifier may be removed and query results may be provided to the user as another array with a user-compatible identifier for the entity such that the results may be understood by the user.

Claims

1. A computer-implemented method to store related sparse data within a search index, the method comprising:

detecting sparse data within content to be indexed, the sparse data comprising a data point related to an entity by determining if the content matches one or more classification rules;

determining a number of matches and a confidence of the matches for the one or more classification rules;

in response to a determination that there is at least one match, creating an integer array for the data point such that a value associated with the data point is one or more of a count value and a confidence value based on the determined number and confidence of the matches;

in response to receiving a request from a user to perform a query on the search index that includes the data point, transforming the query to a corresponding range based on an identifier of the entity; and

upon execution of the query, providing query results to the user.

2. The method of claim 1, further comprising:

removing the identifier of the entity prior to providing the query results to the user.

3. The method of claim 1, wherein providing the query results to the user further comprises:

providing the query results as another array with a user compatible identifier for the entity.

4. The method of claim 3, wherein the other array has a same index as the integer array.

5. The method of claim 1, wherein the identifier corresponds to a highest n-bits of the integer array.

6. The method of claim 1, wherein the value corresponds to a lowest m-bits of the integer array.

7. The method of claim 1, further comprising:

storing the integer array within a single column of the search index.

8. A system configured to store related sparse data within a search index, the system comprising:

a communication module configured to transmit data between one or more servers of the system and one or more client devices associated with the system; and

at least one server comprising;

a memory; and

a processor coupled to the memory and the communication interface, the processor configured to execute a search application, wherein the search application is configured to execute a classification engine and a query engine, wherein the classification engine is configured to;

determine if content to be indexed matches one or more classification rules to detect sparse data within the content, the sparse data comprising a data point related to an entity

determine a number of matches and a confidence of the matches for the one or more classification rules; and

in response to a determination that there is at least one match, creating an inter array for the data point such that a value associated with the data point is one or more of a count value and a confidence value based on the determined number and confidence of the matches; and

the query engine is configured to;

transform a query to a corresponding range based on an identifier of the entity in response to a receipt of a request from a user to perform a query on the search index that includes the data point; and

upon execution of the query, provide query results to the user.

9. The system of claim 8, wherein the one or more classification rules are one of default rules of the classification engine and user-defined.

10. The system of claim 8, wherein the user is enabled to refine the query using the number of the matches and the confidence of the matches determined for the one or more classification rules.

11. The system of claim 8, wherein the request to perform the query includes the entity and the data point.

12. The system of claim 8, wherein the sparse data is sensitive data.

13. A hardware computer-readable memory device with instructions stored thereon to store related sparse data within a search index, the instructions comprising:

detecting sensitive data within content to be indexed, the sensitive data comprising a data point related to an entity by determining if the content matches one or more classification rules;

determining a number of matches and a confidence of the matches for the one or more classification rules;

in response to a determination that there is at least one match, creating an integer array for the data point such that a value associated with the data point is one or more of a count value and a confidence value based on the determined number and confidence of the matches;

in response to receiving a request from a user to perform a query on the search index that includes the data point, transforming the query to a corresponding range based on an identifier of the entity; and

upon execution of the query;

removing the identifier of the entity from the integer array; and

providing query results to the user as another array with a user compatible identifier for the entity.

14. The hardware computer-readable memory device of claim 13, wherein the entity includes one of a credit card number, a social security number, a passport number, an identification number, and account number.

15. The hardware computer-readable memory device of claim 13, wherein the data point includes an integer type that supports standard integer operations.