Integrated full text search system and method

• US 7,376,642 B2
• Filed: 03/30/2004
• Issued: 05/20/2008
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Khanolkar, Nimish, Nayak, Tapas Kumar
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/813,312
• Publication Number:
  US 20050222975A1
• Time in Patent Office: 1,512 Days
• Field of Search: 707 2- 5, 707/10, 707/102, 709/203, 701/500
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The present invention relates to an integrated full-text search architecture that integrates full text search with database server applications in a tight manner so that it becomes part of the server in all aspects including storage, metadata, query processing, back/up restore and resource management. This provides improved performance with respect to queries as well as improved manageability. Furthermore, the subject architecture is open and schema directed unlike other conventional full-text search architectures. Accordingly, the full-text search architecture enables expert users (e.g., search providers) to define their own index structures as well as ranking algorithms.

Claims

1. A full-text search computer implemented system comprising:

a plug-in component executed on a computer provided by a third party developer that defines a relevant score algorithm and a full-text index schema, wherein the relevance algorithm facilitates ranking matching documents and providing a list of documents in order of their relevance; and

a search component to receive and utilize the plug-in component to query data from a data store, populate an index in accordance with the provided index schema and utilize the index to generate a list of matching documents in order of their relevance as specified by the relevant score algorithm, the query data is modified by one or more components specified by the third party developer;

wherein the third party developer specified components are executed as separate daemon processes managed by an external host controller component from within a database management system.

2. The system of claim 1, wherein the plug-in component specifies how the schema is to be populated.

3. The system of claim 1, wherein the search component is tightly integrated into a database management system.

4. The system of claim 3, wherein the database management system comprises a query execution engine that executes received full-text queries and database queries.

5. The system of claim 4, wherein the full-text queries are optimized by a database management system optimization component.

6. The system of claim 1, wherein the search component comprises an index system that creates an index in accordance with one or more consumer plug-in components and a query processing system that provides a mechanism for retrieving relevant documents utilizing the index.

7. The system of claim 6, wherein the index is a compressed nested data structure.

8. A full-text indexing computer implemented system comprising:

a gatherer component to retrieve a document from a data store;

a producer pipeline component that parses the structure and text of the retrieved document in accordance with a plurality of third party developer specified components; and

a consumer pipeline component that receives data from the producer pipeline component and persists data to an inverted index, upon receipt of data, the consumer pipeline component consumes the data and takes action via executing a message through transacted message queues;

the inverted index is modified by the third party developer specified components wherein the third party developer specified components are executed as separate daemon processes managed by an external host controller component from within a database management system.

9. The system of claim 8, wherein the gather component and the consumer pipeline component reside within a database management system.

10. The system of claim 8, wherein the producer pipeline component comprises a noise component to remove keywords that are diminutive in value as search criteria.

11. The system of claim 8, wherein the gatherer component retrieves documents from external databases.

12. A full text query computer implemented system tightly integrated with a database management system comprising:

a parser component that tokenizes received queries;

an execution plan generation system the generates an execution plan based on tokens received from the parser component and a ranking algorithm provided by a third party developer via a ranking plug-in component, wherein the ranking algorithm ranks documents from most to least relevant;

an execution engine component that utilizes the execution plan to search an index and produce a list of matching documents in order as specified by the ranking agorithm;

the execution plan is modified by the third party developer specified component wherein the third party developer specified component is executed as separate daemon process managed by an external host controller component from within a database management system.

13. The system of claim 12, further comprising a user interface component to receive queries from users.

14. The system of claim 12, wherein execution plan generator component produces a query tree, appends scoring functions to leaves, and transforms the query tree into a data base query expression.

15. The system of claim 14, further comprising an optimizer component that optimizes the database query structure based on information concerning the index to be searched.

16. The system of claim 15, further comprising an expander component that modifies keywords provided in the query structure.

17. The system of claim 16, wherein the expander component is executed as a separate daemon process from the execution engine.

18. The system of claim 17, wherein the expander component includes at least one of a stemmer component, a normalizer component, an inflection component, a thesaurus component, a custom expansion component, a homonym component, and a fuzzy component.

19. The system of claim 18, where the expander components and associated functionality are specified by a third party developer.

20. A computer implemented method of employing a customized full-text query comprising:

retrieving a full-text indexing schema and ranking algorithm from a plug-in component provided by a third party developer;

populating an index in accordance with the provided indexing schema;

receiving a query;

generating a list of documents utilizing the index;

displaying the list of documents by ranked in accordance with their relevance by the ranking algorithm, wherein the list of documents are displayed in order from most to least relevant; and

modifying the query by the third party developer specified component wherein the third party developer specified component is executed as separate daemon process managed by an external host controller component from within a database management system.

21. The method of claim 20, wherein the results are generated by a database management system query processor.

22. A customized indexing computer implemented methodology comprising:

retrieving a document from a data source;

removing document formatting data and emitting text chunks;

parsing the text chunks into keywords;

persisting the keywords to an index, the index schema being defined by a third party developer;

employing a ranking algorithm to facilitate ranking matching documents, wherein the ranking algorithm ranks documents from most to least relevant; and

displaying a list of documents by rank in accordance with the ranking algorithm; and

modifying the index by the third party developer specified component wherein the third party developer specified component is executed as separate daemon process managed by an external host controller component from within a database management system.

23. The method of claim 22, further comprising normalizing keywords.

24. The method of claim 22, further comprising removing keywords of diminutive value as search criteria.

25. The method of claim 22, further comprising identifying the language of each text chunk and generating an id indicative thereof.

26. The method of claim 22, further comprising determining and noting the position of each keyword within a respective document.

27. A full text search computer implemented methodology comprising:

receiving a search request;

generating a query expression in response to the search request which includes a third party developer specified ranking algorithm for determining the relevance of result documents, wherein the ranking algorithm ranks documents form most to least relevant;

modifying the query expression to include, remove, add, or modify keyword terms, wherein the query expression is modified by one or more components specified by a third party developer and the third party developer specified components are executed as separate daemon processes managed by an external host controller component from within a database management system; and

displaying a list of documents by rank in accordance with the ranking algorithm.

28. The method of claim 27, further comprising utilizing a database management system to optimize the query expression prior to execution.

29. The method of claim 28, further comprising employing a database execution engine to execute full text queries.

30. The method of claim 27, wherein the query expression is modified once at compile time and again at runtime.