Systems and methods for indexing content for fast and scalable retrieval

Abstract

Systems and methods for generating a document identifier, for a document received at a content store, to be used to generate at least one posting list in connection with querying a content store is described.

1 . A computer-implemented method for generating a document identifier, for a document received at a content store, to be used to generate at least one posting list in connection with querying a content store, comprising:
 upon receiving a new document at the content store, reading a current timestamp value from a system clock;   determining that the current timestamp value has already been assigned to a particular document that has been already stored in a content store;   resolving a timestamp conflict by generating a new timestamp value that is distinguishable from timestamp values associated with documents that have been already stored in the content store; and   assigning the new timestamp value as a new document identifier to the new document;   wherein the steps are performed by one or more computing devices.   
   
   
       2 . The method of  claim 1 , wherein the step of resolving a timestamp conflict comprises:
 preserving a timestamp total order, according to which, each stored document has assigned a unique corresponding document identifier.   
   
   
       3 . The method of  claim 1 , wherein the step of generating a new timestamp value comprises:
 advancing the current timestamp value by a pre-specified amount of time; and   assigning the advanced current timestamp value to the new timestamp value.   
   
   
       4 . The method of  claim 1 , wherein the step of generating a new timestamp value comprises:
 generating a secondary sort key based on information specific to the new document; and   generating the new timestamp value by concatenating the current timestamp value with the secondary sort key.   
   
   
       5 . The method of  claim 4 , wherein the secondary sort key comprises one or more characters extracted from a name of the new document; 
   
   
       6 . The method of  claim 4 , wherein the secondary sort key identifies a creator of the new document. 
   
   
       7 . The method of  claim 1 , wherein the step of generating a new timestamp value comprises:
 increasing a resolution in which timestamp values associated with the documents stored in the content store are represented;   advancing the current timestamp value that is represented with the increased resolution; and   associating the advanced current timestamp value with the new timestamp value.   
   
   
       8 . The method of  claim 1 , wherein the step of generating a new timestamp value comprises:
 determining, based on the current timestamp value, a particular time bucket of a plurality of time buckets, to which the new document belongs;   assigning a unique sequence number to each of the documents identified in the particular time bucket, and assigning a particular unique sequence number concatenated with the current timestamp value to a particular document identified in the particular time bucket; and   advancing the unique sequence number and assign the advanced unique sequence number concatenated with the current timestamp value as the new document identifier for the new document.   
   
   
       9 . The method of  claim 1 , further comprising:
 retesting uniqueness of the new timestamp value before storing, in the content store, the new document and the new timestamp value associated with the new document.   
   
   
       10 . The method of  claim 1 , further comprising:
 applying a Bloom filter to a plurality of timestamps already assigned to documents in the content store.   
   
   
       11 . The method of  claim 1 , wherein the documents stored in the content stored are sorted according to a reverse-chronological order based on document identifiers associated with the documents stored in the content store. 
   
   
       12 . A computing device, including one or more processors, for generating a document identifier, for a document received at a content store, to be used to generate at least one posting list in connection with querying a content store, the computing device configured to perform the steps of:
 upon receiving a new document at the content store, reading a current timestamp value from a system clock;   determining that the current timestamp value has already been assigned to a particular document that has been already stored in a content store;   resolving a timestamp conflict by generating a new timestamp value that is distinguishable from timestamp values associated with documents that have been already stored in the content store;   assigning the new timestamp value as a new document identifier to the new document.   
   
   
       13 . The computing device of  claim 12 , wherein the step of resolving a timestamp conflict comprises:
 preserving a timestamp total order, according to which, each stored document has assigned a unique corresponding document identifier.   
   
   
       14 . The computing device of  claim 12 , wherein the step of generating a new timestamp value comprises:
 advancing the current timestamp value by a pre-specified amount of time; and   assigning the advanced current timestamp value to the new timestamp value.   
   
   
       15 . The computing device of  claim 12 , wherein the step of generating a new timestamp value comprises:
 generating a secondary sort key based on information specific to the new document; and   generating the new timestamp value by concatenating the current timestamp value with the secondary sort key.   
   
   
       16 . The computing device of  claim 15 , wherein the secondary sort key comprises one or more characters extracted from a name of the new document; 
   
   
       17 . The computing device of  claim 15 , wherein the secondary sort key identifies a creator of the new document. 
   
   
       18 . The computing device of  claim 12 , wherein the step of generating a new timestamp value comprises:
 increasing a resolution in which timestamp values associated with the documents stored in the content store are represented;   advancing the current timestamp value that is represented with the increased resolution; and   associating the advanced current timestamp value with the new timestamp value.   
   
   
       19 . The computing device of  claim 12 , wherein the step of generating a new timestamp value comprises:
 determining, based on the current timestamp value, a particular time bucket of a plurality of time buckets, to which the new document belongs;   assigning a unique sequence number to each of the documents identified in the particular time bucket, and assigning a particular unique sequence number concatenated with the current timestamp value to a particular document identified in the particular time bucket;   advancing the unique sequence number and assign the advanced unique sequence number concatenated with the current timestamp value as the new document identifier for the new document.   
   
   
       20 . The computing device of  claim 12 , further configured to perform the step of:
 retesting uniqueness of the new timestamp value before storing, in the content store, the new document and the new timestamp value associated with the new document.   
   
   
       21 . The computing device of  claim 12 , further configured to perform the step of:
 applying a Bloom filter to a plurality of timestamps already assigned to documents in the content store.   
   
   
       22 . The computing device of  claim 12 , wherein the documents stored in the content stored are sorted according to a reverse-chronological order based on document identifiers associated with the documents stored in the content store.