Systems and methods for indexing content for fast and scalable retrieval

Claim 2

A computer-implemented method for deriving a posting list that contains posting records that identify documents that satisfy a logical combination of a plurality of terms of a query, comprising: for each term of the plurality of terms of the query being executed against a content store, generating a temporally ordered posting list having posting records that identify documents in the content store that satisfy the each term of the query, wherein: each posting record uniquely identifies a document by using a timestamp that is a document identifier; and within each temporally ordered posting list, posting records are listed in a pre-defined temporal order based on the timestamps that are used as document identifiers by the posting records; combining a first posting list and a second posting list of the temporally ordered posting lists by: selecting, based on the pre-defined temporal order of a first posting list having posting records that identify documents in the content store that satisfy a first term of the plurality of terms of the query, a posting record from the first posting list; selecting, based on the pre-defined temporal order of a second posting list having posting records that identify documents in the content store that satisfy a second term of the plurality of terms of the query, a posting record from the second posting list; performing a compare operation between the posting record from the first posting list and the posting record from the second posting list by comparing a first timestamp of the posting record from the first posting list with a second timestamp of the posting record from the second posting list; determining, based on the compare operation, whether there is a match between the posting record from the first posting list and the posting record from the second posting list; and in response to determining that there is a match, determining that the posting record from the first posting list or the posting record from the second posting list identifies a document that satisfies the query.

Claim 3

A method according to claim 1 , wherein said generating a temporally ordered posting list includes making the temporally ordered posting list a total order.

Claim 4

A method according to claim 2 , wherein said making the temporally ordered posting list a total order includes: assigning, to documents in the content store, unique timestamps as document identifiers; wherein each posting record identifies a document in the content store by using the unique timestamp assigned to the document as a document identifier.

Claim 5

A method according to claim 3 , wherein said making the temporally ordered posting list a total order includes applying a Bloom filter to a plurality of existing timestamps assigned to documents in the content store as document identifiers.

Claim 6

A method according to claim 3 , wherein assigning includes enforcing the uniqueness of a timestamp when it is generated by resolving the conflict with another pre- existing time stamp.

Claim 7

A method according to claim 5 , wherein said enforcing includes modifying at least one bit of the timestamp.

Claim 8

A method according to claim 5 , wherein said enforcing includes modifying the timestamp by a pre-specified amount of time.

Claim 9

A method according to claim 5 , wherein said enforcing includes at least one of (A) adding at least one random bit to the timestamp, (B) supplementing the timestamp with a separate field in the posting record for conflict resolution, (C) generating artificial floating point precision for the timestamp or (D) adding a sequence number to the timestamp for disambiguation of postings.

Claim 10

A method according to claim 1 , wherein said pre-defined temporal order is reverse chronological order.

Claim 11

A method according to claim 1 , wherein said pre-defined temporal order is forward chronological order.

Claim 12

A method according to claim 1 , wherein said combining includes repeating the steps of selecting a posting record from the first posting list, selecting a posting record from the second posting list, performing a compare operation between posting records of the first and second posting lists, and determining whether there is a match, in date descending order of the first and second posting lists, from most recent to oldest, to determine which posting records satisfy the query.

Claim 13

A method according to claim 1 , further including: concluding said combining when a pre-defined number of results are determined to satisfy the query.

Claim 14

A method according to claim 12 , wherein said concluding includes concluding said combining when a pre-defined number of most recent documents satisfy the query.

Claim 15

A method according to claim 12 , wherein said concluding includes concluding said combining when a pre-defined number of documents satisfy a date range associated with the query.

Claim 16

A method according to claim 1 , further including: outputting a result set based on said combining that satisfies the query.

Claim 17

A computer readable storage medium comprising computer executable instructions for performing the method of claim 1 .

Claim 18

A computing device, including one or more processors, for deriving a posting list that contains posting records that identify documents that satisfy a logical combination of a plurality of terms of a query, wherein the computing device is configured to generate a temporally ordered posting list for each term of the plurality of terms of the query being executed against a content store, wherein a temporally ordered posting list includes posting records that identify documents in the content store that satisfy the each term of the query, wherein each posting record uniquely identifies a document by using a timestamp that is a document identifier, and wherein within each temporally ordered posting list, posting records are listed in a pre-defined temporal order based on the timestamps that are used as document identifiers by the posting records; wherein the computing device is configured to combine a first posting list and a second posting list of the temporally ordered posting lists by: selecting, based on the pre-defined temporal order of a first posting list having posting records that identify documents in the content store that satisfy a first term of the plurality of terms of the query, a posting record from the first posting list; selecting, based on the pre-defined temporal order of a second posting list having posting records that identify documents in the content store that satisfy a second term of the plurality of terms of the query, a posting record from the second posting list; performing a compare operation between the posting record from the first posting list and the posting record from the second posting list by comparing a first timestamp of the posting record from the first posting list with a second timestamp of the posting record from the second posting list; determining, based on the compare operation, whether there is a match between the posting record from the first posting list and the posting record from the second posting list; and in response to determining that there is a match, determining that the posting record from the first posting list or the posting record from the second posting list identifies a document that satisfies the query.

Claim 19

A computing device, including one or more processors, for deriving a posting list that contains posting records that identify documents that satisfy a logical combination of a plurality of terms of a query, wherein the computing device is configured to generate a temporally ordered posting list for each term of the plurality of terms of the query being executed against a content store, wherein a temporally ordered posting list includes posting records that identify documents in the content store that satisfy the each term of the query, wherein each posting record uniquely identifies a document by using a timestamp that is a document identifier, and wherein within each temporally ordered posting list, posting records are listed in a pre-defined temporal order based on the timestamps that are used as document identifiers by the posting records; wherein the computing device is configured to combine a first posting list and a second posting list of the temporally ordered posting lists by: selecting, based on the pre-defined temporal order of a first posting list having posting records that identify documents in the content store that satisfy a first term of the plurality of terms of the query, a posting record from the first posting list; selecting, based on the pre-defined temporal order of a second posting list having posting records that identify documents in the content store that satisfy a second term of the plurality of terms of the query, a posting record from the second posting list; performing a compare operation between the posting record from the first posting list and the posting record from the second posting list by comparing a first timestamp of the posting record from the first posting list with a second timestamp of the posting record from the second posting list; determining, based on the compare operation, whether there is a match between the posting record from the first posting list and the posting record from the second posting list; and in response to determining that there is a match, determining that the posting record from the first posting list or the posting record from the second posting list identifies a document that satisfies the query.

Claim 20

A computing device, including one or more processors, according to claim 17 , wherein said temporally ordered posting list is ordered according to a total order.

Claim 21

A computing device, including one or more processors, according to claim 18 , wherein: documents in the content store are assigned unique timestamps as document identifiers; and each posting record identifies a document in the content store by using the unique timestamp assigned to the document as a document identifier.

Claim 22

A computing device, including one or more processors, according to claim 19 , wherein the unique timestamps assigned as document identifiers are made unique by applying a Bloom filter to a plurality of existing timestamps assigned to documents in the content store as document identifiers.

Claim 23

A computing device, including one or more processors, according to claim 19 , wherein the uniqueness of a timestamp is enforced when it is generated by resolving a conflict with another pre-existing timestamp.

Claim 24

A computing device, including one or more processors, according to claim 21 , wherein the uniqueness of a timestamp is enforced when it is generated by modifying at least one bit of the timestamp.

Claim 25

A computing device, including one or more processors, according to claim 21 , wherein the uniqueness of a timestamp is enforced when it is modified by a pre-specified amount of time.

Claim 26

A computing device, including one or more processors, according to claim 21 , wherein the uniqueness of a timestamp is enforced when it is modified by at least one of (A) adding at least one bit to the timestamp, (B) adding a separate field to the posting record for timestamp conflict resolution, (C) generating artificial floating point precision to the timestamp or (D) adding a sequence number to the timestamp for disambiguation of posting records.

Claim 27

A computing device, including one or more processors, according to claim 17 , wherein said pre-defined temporal order is forward chronological order.

Claim 28

A computing device, including one or more processors, according to claim 17 , wherein said pre-defined temporal order is reverse chronological order.

Claim 29

A computing device, including one or more processors, according to claim 17 , wherein said the computing device is configured to combine by repeating the steps of selecting a posting record from the first posting list, selecting a posting record from the second posting list, performing a compare operation between posting records of the first and second posting lists, and determining whether there is a match, in date descending order of the first and second posting lists, from most recent to oldest, to determine which posting records satisfy the query.

Claim 30

A computing device, including one or more processors, according to claim 17 , wherein the computing device is configured to stop combining the first and second posting list when a pre-defined number of results are determined to satisfy the query.

Claim 31

A computing device, including one or more processors, according to claim 28 , wherein the computing device is configured to stop combining the first and second posting list when a pre-defined number of most recent documents satisfy the query.

Claim 32

A computing device, including one or more processors, according to claim 28 , wherein the computing device is configured to stop combining the first and second posting list when a pre-defined number of documents satisfy a date range associated with the query.

Claim 33

A computing device, including one or more processors, according to claim 17 , wherein the computing device is configured to output a result set based on combining the first and second posting list.