Multi-User Search System Using Tokens

Patent metadata

Field	Value
Publication number	US-2017011084-A1
Application number	US-201615275238-A
Country	US
Kind code	A1
Filing date	Sep 23, 2016
Priority date	Aug 21, 2014
Publication date	Jan 12, 2017
Grant date	—

Abstract

A multi-user search system with methodology for instant indexing. In one embodiment, for example, a system for instant indexing includes a token store storing sets of tokens for current versions of documents. The system further includes a tokenizer server configured to tokenize new versions of the documents and to generate sets of tokens for the new versions of the documents, an instant indexer configured to determine tokens to use to index the documents based on identified differences between the sets of tokens for the new versions of the documents and the sets of tokens for the current versions of the documents, and to generate index mutations including the tokens to use to index the documents, an index mutation journal configured to store the generated index mutations in association with timestamps, and an index mutation server configured to provide, to index servers, from the index mutation journal, generated index mutations for the index servers that are associated with timestamps that are newer than specified timestamps.

First claim

1 . A method performed by one or more computing devices, the method comprising:
generating an index mutation comprising one or more tokens, wherein the index mutation is based at least in part on one or more identified differences between a new version of a document and a previous version of the document; storing the index mutation and an associated time-based value; comparing the time-based value associated with the index mutation to a time-based value associated with an index of the document; and based at least in part on the comparing, providing the one or more tokens of the index mutation to an index server.

2 . The method of claim 1 , wherein at least one of the one or more tokens is identified in the new version of the document but not the previous version of the document.

3 . The method of claim 1 , wherein at least one of the one or more tokens is identified in the previous version of the document but not the new version of the document.

4 . The method of claim 1 , further comprising storing the index mutation and the associated time-based value in an append-only log.

5 . The method of claim 1 , wherein providing the one or more tokens of the index mutation causes the index server to update the index of the document based at least in part on the one or more tokens.

6 . The method of claim 1 , wherein the time-based value associated with the index mutation is a timestamp.

7 . The method of claim 1 , further comprising receiving the time-based value associated with the index of the document from the index server.

8 . The method of claim 1 , wherein the providing the one or more tokens of the index mutation to the index server is based, at least in part, on the index mutation corresponding to a document namespace assigned to the index server.

9 . The method of claim 1 ,
wherein the document belongs to a document namespace assigned to the index server; wherein the index mutation comprises an identifier of the document namespace; and wherein the providing the one or more tokens of the index mutation to the index server is based, at least in part, on the identifier of the document namespace of the index mutation.

10 . The method of claim 1 ,
wherein a result of the comparing indicates whether the index server is up-to-date with respect to the index mutation; and wherein the providing the one or more tokens of the index mutation to the index server is based at least in part on the result of the comparing.

11 . The method of claim 1 , wherein the other index mutation comprises tokens representing information on another document that is different than the document.

12 . The method of claim 1 , further comprising:
identifying the new version of the document based on information on the document from a message queue; wherein the message queue stores information on changes to one or more documents managed by a content management system; and wherein generating the index mutation is in response to the identifying the new version of the document.

13 . The method of claim 1 , wherein the index mutation is a first index mutation; wherein the document is a first document; and wherein the method further comprises:
generating a second index mutation that is not the first index mutation, the second index mutation comprising at least one token, wherein the second index mutation is based at least in part on at least one identified difference between a new version of a second document that is not the first document and a previous version of the second document; storing the second index mutation and an associated bypass flag value; and based at least in part on the bypass flag value, determining not to provide the at least one token of the second index mutation to an index server.

14 . One or more non-transitory computer-readable media storing instructions which, when executed by one or more computing devices, cause performance of operations comprising:
generating an index mutation comprising one or more tokens, wherein the index mutation is based on identified differences between a new version of a document and a previous version of the document; storing an indication of the index mutation in a log; and providing the one or more tokens from the stored index mutation to an index server that stores an index of the document, wherein the providing causes the index server to use the one or more tokens to update the index of the document.

15 . The one or more non-transitory computer-readable media storing instructions of claim 14 , wherein the previous version of the document does not include at least one token used to represent the new version of the document.

16 . The one or more non-transitory computer-readable media storing instructions of claim 14 , wherein the log is an append-only log.

17 . A system, comprising:
storage media; one or more processors; and instructions stored in the storage media and configured for execution by the one or more processors, the instructions configured for:
generating an index mutation comprising one or more tokens, wherein the one or more tokens are based at least in part on identified differences between a new version of a document and a previous version of the document;
associating the index mutation and a version indicator;
comparing the version indicator associated with the index mutation to a value associated with an index of the document; and
based at least in part on the comparing, providing the one or more tokens of the index mutation to an index server.

18 . The system of claim 17 , wherein at least one of the one or more tokens is identified in the new version of the document but not the previous version of the document.

19 . The system of claim 17 , wherein the version indicator is a clock value.

20 . The system of claim 17 , further comprising storing the index mutation and the associated version indicator in an append-only log.

Assignees

• Dropbox Inc

Inventors

• Goel Samir
• Chastagnol Franck
• Agrawal Abhishek

Classifications

• G06F16/219

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F16/328 Primary

  Management therefor · CPC title

• G06F16/24

  Querying · CPC title

• H04L63/101

  Access control lists [ACL] · CPC title

• G06F16/319

  Inverted lists · CPC title