Lock-free indexing of documents

• US 9,158,767 B2
• Filed: 04/08/2011
• Issued: 10/13/2015
• Est. Priority Date: 04/08/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sharman, Neil, Sharma, Vibhaakar
• Primary Examiner(s): GEBRESENBET, DINKU W
• Application Number:
  US13/082,997
• Publication Number:
  US 20120259860A1
• Time in Patent Office: 1,649 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Methods and systems for serving documents are provided. Documents may be served to users, for example, in response to search query inputs. Documents may be individually received for serving to users. In order to serve documents, documents are typically indexed. To serve documents in a real-time environment, a data structure is configured to index documents that are received while simultaneously being queried for documents to serve to a user. Documents that have not yet completed the indexing process are not available for serving and, thus, are not queried. Additionally, the data structure includes a memory optimizer such that indexing does not waste memory of the data structure.

Claims

1. One or more computer storage hardware devices having one or more computer-useable instructions embodied thereon that, when executed perform a method, the method comprising:

receiving a first document at a data structure, wherein the data structure includes an index of one or more documents;

receiving a search query at the data structure while the data structure is receiving the first document;

determining, at the one or more computer storage devices, whether the first document is available for serving by identifying a cut-off point that indicates completion of individually indexing the first document, wherein if the first document has been completely indexed, the first document is available for serving, and if the first document has not been completely indexed, the first document is not available for serving, wherein the cut-off point is an indication that a mapping of content of the first document is complete; and

upon determining the first document is available for serving, having identified completion of individually indexing of the first document, individually serving the first document while simultaneously indexing a second document prior to completion of a batching process that includes the first document and the second document.

2. The one or more computer storage hardware devices of claim 1, wherein documents include websites and web pages.

3. The one or more computer storage hardware devices of claim 1, further comprising identifying a plurality of documents associated with a search query input.

4. The one or more computer storage hardware devices of claim 3, wherein the plurality of documents includes the first document.

5. The one or more computer storage hardware devices of claim 1, wherein the first document is served in response to a search query input.

6. The one or more computer storage hardware devices of claim 1, wherein the index includes an identification of one or more terms included within a received document.

7. The one or more computer storage hardware devices of claim 6, wherein the index further includes an identification of a position of each of the one or more terms included within the received document.

8. The one or more computer storage hardware devices of claim 1, further comprising

receiving a search query input;

and

identifying that the second document is not completely indexed such that it is not available to serve to a user.

9. A method for quickly serving documents, the method comprising:

receiving, at a data structure, a first document that is available from a document provider, wherein the first document is any new web document;

identifying, by a computing device having a processor and a memory, a first term associated with the first document and a position associated therewith;

assigning a memory allocation to the first term;

identifying the first term as a common term, wherein a common term is a term that is identified a predetermined number of times;

receiving the first term at a later time;

upon receiving the first term at a later time, adjusting the memory allocation assigned to the first term; and

individually serving a second document that has been indexed, while completing indexing of the first document, prior to completion of a batching process that groups the first document and the second document, such that the data structure is being built while serving the individual second document.

10. The method of claim 9, wherein adjusting the memory allocation assigned to the first term includes increasing the memory allocation assigned to the first term.

11. The method of claim 9, further comprising:

identifying a second term; and

assigning a second memory allocation to the second term.

12. The method of claim 11, further comprising identifying a second term as a rare term, wherein a rare term is a term that is identified a number of times that is less than a predetermined threshold.

13. The method of claim 12, further comprising adjusting the second memory allocation assigned to the second term, wherein adjusting the second memory allocation assigned to the second term includes reducing the second memory allocation.

14. A system for quickly serving documents, comprising:

one or more hardware computer-storage devices configured to embody a data structure, wherein the data structure includes an index of one or more documents, the data structure configured to

A) receive a first document, and

B) receive a search query while the first document is received by the data structure; and

one or more processors configured to

A) determine whether the first document is available for serving by identification of a cut-off point that indicates completion of an individual indexing of the first document, wherein if the first document has been completely indexed, the first document is available for serving, and if the first document has not been completely indexed, the first document is not available for serving, wherein the cut-off point is an indication that a mapping of content of the first document is complete,

B) upon a determination that the first document is available for serving, having identified completion of the individual indexing of the first document, individually serve the first document and simultaneously index a second document prior to completion of a batching process that includes the first document and the second document.

15. The system of claim 14, wherein documents include websites and web pages.

16. The system of claim 14, the one or more processors further configured to identify a plurality of documents associated with a search query input.

17. The system of claim 16, wherein the plurality of documents includes the first document.

18. The system of claim 14, wherein the first document is served in response to a search query input.

19. The system of claim 14, wherein the index includes an identification of one or more terms included within a received document.

20. The system of claim 19, wherein the index further includes an identification of a position of each of the one or more terms included within the received document.