Document capture using client-based delta encoding with server

• US 10,318,592 B2
• Filed: 07/18/2016
• Issued: 06/11/2019
• Est. Priority Date: 07/16/2015
• Status: Active Grant

• Current Assignee: Quantum Metric, Inc.
• Original Assignee: Quantum Metric LLC
• Inventors: Ciabarra, Jr., Mario Luciano, Wang, Yiduo
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US15/212,569
• Publication Number:
  US 20170017650A1
• Time in Patent Office: 1,058 Days
• Field of Search: 707747
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 40/123 Storage facilities
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71

Abstract

When different client devices request the same document, most of content of the response from the server (i.e. the response document from a web server) will be the same. Embodiments allow the client devices to use fingerprints, i.e. hashes, sent by a capture system to pinpoint only the changing portions of the document instead of sending the entire document. In various embodiments, the client compares client-generated fingerprints for the document with capture system-generated fingerprints for most likely appearing portions of text of the document or related documents to fully represent and sends to the capture system the client document in a compact and efficient way.

Claims

1. A computer-implemented method, comprising:

accessing, by a client device, from a first computer system, a first electronic document identified by a uniform resource indicator (URI);

generating, by the client device, a first set of hashed data portions corresponding to the first electronic document, wherein each of the first set of hashed data portions corresponds to a different portion of data in the first electronic document;

sending, by the client device, to a second computer system, a request for one or more hashed data portions corresponding to the first electronic document, the request including information identifying the first electronic document;

receiving, by the client device, from the second computer system, a second set of hashed data portions responsive to the request, wherein each of the second set of hashed data portions is generated based on a different portion of data in a second electronic document, wherein each of the different data portions satisfies a threshold frequency for appearing in the second electronic document, and wherein the second set of hashed data portions are identified as responsive to the request based on determining that the second electronic document matches the first electronic document identified by the information in the request;

comparing the first set of hashed data portions to the second set of hashed data portions;

identifying, based on the comparing, one or more data portions of the first electronic document that are different from the second electronic document; and

sending, to the second computer system, the one or more identified data portions of the first electronic document as updates to the second electronic document, wherein the second computer system associates the one or more identified data portions as updates to the second electronic document to construct the first electronic document.

2. The computer-implemented method of claim 1, wherein the first set of hashed data portions includes a first hashed data portion generated using a weak hash function and includes a second hashed data portion generated using a strong hash function, wherein the first hashed data portion and the second hashed data portion are generated based on a same portion of the data in the first electronic document, wherein the weak hash function is defined by a first threshold measure of collisions and the strong hash function is defined by a second threshold measure of collisions, and wherein the first threshold measure of collisions is greater than the second threshold measure of collisions.

3. The computer-implemented method of claim 1, wherein the second set of hashed data portions includes a first hashed data portion generated using a weak hash function and includes a second hashed data portion generated using a strong hash function, wherein the first hashed data portion and the second hashed data portion are generated for a same portion of the data in the second electronic document, wherein the weak hash function is defined by a first threshold measure of collisions and the strong hash function is defined by a second threshold measure of collisions, and wherein the first threshold measure of collisions is greater than the second threshold measure of collisions.

4. The computer-implemented method of claim 1, wherein each of a subset of the first set of hashed data portions and each of a subset of the second set of hashed data portions are generated by a sliding window technique using a weak hash function.

5. The computer-implemented method of claim 1, wherein the first set of hashed data portions includes a weak hashed data portion and a strong hashed data portion for each of a plurality of data portions in the first electronic document, and wherein the second set of hashed data portions includes a weak hashed data portion and a strong hashed data portion for each of a plurality of data portions in the second electronic document.

6. The computer-implemented method of claim 5, wherein comparing the first set of hashed data portions to the second set of hashed data portions includes:

comparing the weak hashed data portion for each of the plurality of data portions in the first electronic document to the weak hashed data portion for each of the plurality of data portions in the second electronic document;

identifying, based on the comparing of the weak hashed data portion for each of the plurality of data portions in the first electronic document, a first set of data portions in the first electronic document, each of the first set of data portions for which the weak hashed data portion matches a different weak hashed data portion in the second set of hashed data portions for a second set of data portions in the second electronic document; and

comparing the strong hashed data portion corresponding to each of the first set of data portions to the strong hashed data portion of a data portion in the second set of data portions having the weak hashed data portion which matched the weak hashed data portion of the data portion in the first set of data portions.

7. The computer-implemented method of claim 6, wherein the identifying, based on the comparing, one or more data portions of the first electronic document that are different from the second electronic document includes:

based on determining that the weak hashed data portion of a first data portion in the plurality of data portions in the first electronic document does not match any weak hashed data portion in the second set of hashed data portions, identifying the first data portion for inclusion in the one or more data portions of the first electronic document that are different from the second electronic document; and

identifying a second data portion of the plurality of data portions in the first electronic document for inclusion in the one or more data portions of the first electronic document that are different from the second electronic document, wherein the second data portion is identified based on determining that the strong hashed data portion for the second data portion does not match the strong hashed data portion of the data portion in the second set of data portions.

8. The computer-implemented method of claim 1, further comprising:

identifying one or more hashed data portions of the first set of hashed data portions that match any of the second set of hashed data portions;

wherein the one or more identified data portions are sent to the second computer system along with the identified one or more hashed data portions.

9. The computer-implemented method of claim 8, wherein the one or more identified data portions are sent to the second computer system along with information indicating a process to generate the first electronic document using the one or more identified data portions and the one or more identified hashed data portions.

10. The computer-implemented method of claim 1, further comprising:

parsing the first electronic document to identify a plurality of data portions of the data in the first electronic document; and

generating, a set of hash values for the plurality of data portions, wherein the set of hash values is generated based on applying one or more hashing algorithms to the plurality of data portions;

wherein the information identifying the first electronic document includes the generated set of hash values.

11. The computer-implemented method of claim 10, wherein the first set of hashed data portions are generated based on the plurality of data portions, and wherein each of the first set of hashed data portions corresponds to a different one of the plurality of data portions.

12. The computer-implemented method of claim 10, wherein determining that the second electronic document matches the first electronic document includes determining that the generated set of hash values matches a threshold number of hash values in a set of hash values generated for the second electronic document, and wherein each of the set of hash values is generated for a different one of a set of data portions of the data in the second electronic document.

13. The computer-implemented method of claim 10, wherein the plurality of data portions are identified in the first electronic document by parsing the first electronic document based on a size of the first electronic document.

14. The computer-implemented method of claim 1, wherein the second set of hashed data portions is generated for a set of data portions in the second electronic document, and wherein each of the set of data portions satisfies a threshold frequency for appearing in electronic documents related to the first electronic document identified by the URI.

15. The computer-implemented method of claim 1, wherein accessing the first electronic document from the first computer system includes:

sending, to the first computer system, a hypertext transfer protocol (HTTP) request for the first electronic document, wherein the HTTP request includes the URI; and

receiving an HTTP response, wherein the HTTP response includes the first electronic document identified by the URI, wherein the HTTP response includes one of a hypertext markup language (HTML) document or a document including JavaScript.

16. A system, comprising:

one or more processors;

a memory accessible to the one or more processors, the memory comprising instructions that, when executed by the one or more processors, causes the one or more processors to;

access, from a first computer system, a first electronic document identified by a uniform resource indicator (URI);

generate a first set of hashed data portions corresponding to the first electronic document, wherein each of the first set of hashed data portions corresponds to a different portion of data in the first electronic document;

send, to a second computer system, a request for one or more hashed data portions corresponding to the first electronic document, the request including information identifying the first electronic document;

receive, from the second computer system, a second set of hashed data portions responsive to the request, wherein each of the second set of hashed data portions is generated based on a different portion of data in a second electronic document, wherein each of the different data portions satisfies a threshold frequency for appearing in the second electronic document, and wherein the second set of hashed data portions are identified as responsive to the request based on determining that the second electronic document matches the first electronic document identified by the information in the request;

compare the first set of hashed data portions to the second set of hashed data portions;

identify, based on the comparing, one or more data portions of the first electronic document that are different from the second electronic document; and

send, to the second computer system, the one or more identified data portions of the first electronic document as updates to the second electronic document, wherein the second computer system associates the one or more identified data portions as updates to the second electronic document to construct the first electronic document.

17. The system of claim 16, wherein the one or more processors and the memory are included in a mobile communication device, and wherein the first computer system is a web server computer and is different from the second computer system.

18. A computer-implemented method, comprising:

determining, by a computer system, identification data for a first electronic document stored in association with a uniform resource indicator (URI);

identifying, by the computer system, a set of data portions in the first electronic document, wherein each of the set of data portions satisfies a threshold frequency for appearing in the first electronic document;

generating, by the computer system, a set of hashed data portions for the identified set of data portions in the first electronic document, wherein each of the set of hashed data portions are generated based on a different portion of the identified set of data portions;

receiving, by the computer system, from a client device, a request for one or more hashed data portions corresponding to a second electronic document, the request including information identifying the second electronic document;

determining that the second electronic document matches the first electronic document based on the information identifying the second electronic document matching the identification data for the first electronic document;

responsive to determining that the second electronic document matches the first electronic document, sending the set of hashed data portions to the client device;

receiving, by the computer system, from the client device, one or more data portions of the second electronic document that are different from the first electronic document, wherein the one or more data portions are identified using the set of hashed data portions sent to the client device; and

constructing, by the computer system, a third electronic document based on the one or more data portions of the second electronic document and the identified set of data portions, wherein the third electronic document is constructed as an update to the first electronic document having as at least a portion of the first electronic document and the one or more data portions of the second electronic document that are received from the client device.

19. The computer-implemented method of claim 18, wherein the third electronic document is the second electronic document.