Method for indexing for retrieving documents using particles

1. A computer implemented method for indexing and retrieving documents in a database, comprising the steps of:

constructing a set of particles and a simultaneously optimized particle-based language model using training documents, and in which a perplexity of the particle-based language model is at least ten times lower than the perplexity of a word-based language model constructed from the same training documents, wherein the set of particles applies expectation maximization to an objective function, and where the objective function considers any combination of:

a size of the set of particles;

errors in representing all documents in a document training set and a query training set;

a retrieval accuracy of using the set of particles;

an entropy of a statistical models that represent the set of particles; and

a particle-level language model derived from the documents and the queries in the training sets;

converting each document in a collection of documents to a document particle graph, the document particle graph including particles selected from the set of the particles;

extracting, for each document, a set of document keys from the corresponding particle graph;

storing the document keys for each document in an index to a database storing the collection of documents;

converting a query to a query particle graph including a set of query particles, the query graph including particles selected from the set of the particles;

extracting a set of query keys from the query particle graph;

retrieving relevant documents from the database according to the query keys and the document keys stored in the index; and

outputting the relevant documents to a user.

2. The method of claim 1 , in which the set of particles is substantially larger than a number of phonemes in a language of the documents, and substantially smaller than a number of words in the language.

3. The method of claim 1 , in which a particular particle traverses word boundaries.

4. The method of claim 1 , in which the document and the query are a form of text words.

5. The method of claim 1 , in which the document is in a form of text words, and the query is in a form of spoken words.

6. The method of claim 1 , in which the document and the query are a form of spoken words.

7. The method of claim 1 , in which the document is in a form of spoken words, and the query is in a form of text words.

8. The method of claim 1 , in which the query is spoken and the query particle graph is a lattice representing alternate sequential groupings of sound sequences in the spoken query.

9. The method of claim 1 , in which the set of particles represent all possible sound sequences that can occur in any query.

10. The method of claim 1 , in which the set of particles is derived from a pronunciation of any sequence of words from the document.

11. The method of claim 1 , in which the set of particles identifies the key in any document that the document from other documents.

12. The method of claim 1 , in which the document particle graph and the query particle graph are normalized by a spelling-to-pronunciation mechanism.

13. The method of claim 1 , in which the particles in the set of particles are acoustically distinct and self-contained.

14. The method of claim 1 , in which a predictability of the occurrence of particles must be high.

15. The method of claim 1 , in which each particle has a distinctive acoustic structure that distinguish the particle from all other particles, and has a relatively low acoustic variability between different instances of the same particle.

16. The method of claim 1 , in which a predictability of an occurrence of a particular particle is relatively high.

17. The method of claim 1 , in which the particle set is determined manually.

18. The method of claim 1 , in which the particle set is determined heuristically.

19. The method of claim 1 , in which each word in each document is first converted to a phonetic graph that represents all the possible pronunciations of the word, and then converting the phonetic graph to the document particle set.

20. The method of claim 1 , further comprising:

rank ordering the relevant documents.

21. An information retrieval system, comprising:

means for constructing a set of particles and a simultaneously optimized particle-based language model using training documents, and in which a perplexity of the particle-based language model is at least ten times lower than the perplexity of a word-based language model constructed from the same training documents, wherein the set of particles applies expectation maximization to an objective function, and where the objective function considers any combination of:

a size of the set of particles;

errors in representing all documents in a document training set and a query training set;

a retrieval accuracy of using the set of particles;

an entropy of a statistical models that represent the set of particles; and

a particle-level language model derived from the documents and the queries in the training sets;

means for converting each document in a collection of documents to a document particle graph, the document graph, the document graph including particles selected from a set of the particles;

means for extracting, for each document, a set of document keys from the corresponding particle graph;

means for storing the document keys for each document in an index to a database storing the collection of documents;

means for converting a query to query particle graph including a set of query particles, the query graph including particles selected from the set of the particles;

means for extracting a set of query keys from the query particle graph;

means for retrieving relevant documents from the database according to the query keys and the document keys stored in the index; and

means for outputting the relevant documents to a user.