Supporting web-query expansion efficiently using multi-granularity indexing and query processing

• US 6,480,843 B2
• Filed: 11/03/1998
• Issued: 11/12/2002
• Est. Priority Date: 11/03/1998
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC USA (NEC Corporation)
• Inventors: Li, Wen-Syan
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): Wassum, Luke S
• Application Number:
  US09/185,323
• Publication Number:
  US 20020059161A1
• Time in Patent Office: 1,470 Days
• Field of Search: 707/1-6, 707/532, 704/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus for efficient query expansion using reduced size indices and for progressive query processing. Queries are expanded conceptually, using semantically similar and syntactically related words to those specified by the user in the query to reduce the chances of missing relevant documents. The notion of a multi-granularity information and processing structure is used to support efficient query expansion, which involves an indexing phase, a query processing and a ranking phase. In the indexing phase, semantically similar words are grouped into a concept which results in a substantial index size reduction due to the coarser granularity of semantic concepts. During query processing, the words in a query are mapped into their corresponding semantic concepts and syntactic extensions, resulting in a logical expansion of the original query. Additionally, the processing overhead is avoided. The initial query words can then be used to rank the documents in the answer set on the basis of exact, semantic and syntactic matches and also to perform progressive query processing.

Claims

1. A method of querying a database of documents, the database including a preliminary index of the documents, words contained in the documents and associations therebetween, the words in the preliminary index being of an original granularity, the method comprising the steps of:

a) replacing the words in the preliminary index with corresponding higher granularity concepts, resulting in a coarser granularity index of reduced index size;

b) logically expanding a query applied to the database of documents by replacing only the words of the query, being of the original granularity, meeting a predetermined criterion, which is whether the words can be found in a lexical dictionary with corresponding ones of the higher granularity concepts,

b)(i) wherein the higher granularity concepts are higher granularity semantic concepts,

b)(ii) further logically expanding the query by adding syntactically related words for each of the corresponding ones of the higher granularity concepts;

b)(iii) further logically expanding the query by adding syntactically related words for each of the words in the query failing to meet the predetermined criterion;

b)(iv) replacing ones of the syntactically related words meeting the predetermined criterion with associated ones of the higher granularity concepts; and

b)(v) removing any redundant ones of the syntactically related words and higher granularity concepts from the expanded query;

c) executing the logically expanded query to retrieve ones of the documents associated, through the coarser granularity index, with the corresponding ones of the higher granularity concepts; and

d) retrieving ones of the documents in order of relevance until a predetermined number of ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved, wherein the order of relevance is an exact match, a semantic match, a syntactical match and no match between the words of the query and the words contained in the retrieved ones of the documents.

2. The method according to claim 1, wherein in the replacing step, the higher granularity concepts are higher granularity semantic concepts.

3. The method according to claim 2, wherein the higher granularity semantic concepts each contain synonyms.

4. The method according to claim 1, wherein in the replacing step, only ones of the words in the preliminary index meeting a predetermined criterion are replaced by the corresponding higher granularity concepts.

5. The method according to claim 4, wherein the predetermined criterion is whether the words can be found in a lexical dictionary.

6. The method according to claim 1, wherein in the replacing step, the higher granularity concepts are higher granularity syntactical concepts.

7. The method according to claim 6, wherein the higher granularity syntactical concepts each contain words co-occurring in ones of the documents above a threshold level of frequency.

8. The method according to claim 1, wherein in the replacing step, ones of the words in the preliminary index having multiple meanings are replaced by multiple ones of the corresponding higher granularity concepts.

9. The method according to claim 1, wherein words failing to meet the predetermined criterion are proper nouns.

10. The method according to claim 1, wherein the step of executing progresses in successive stages until a predetermined number of the ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved.

11. The method according to claim 10, wherein each of the stages represents a class of expansion.

12. The method according to claim 10, wherein each of the stages represents a slot within a class of expansion.

13. The method according to claim 10, wherein within each of the stages, the ones of the documents are retrieved in an order reflecting a level of importance assigned to at least one of the words of the query.

14. A method querying a database of documents, the database including an index of reduces index size of the documents, higher granularity concepts and associations therebetween, the higher granularity concepts corresponding to words of original granularity contained in the documents, the method comprising the steps of:

a) logically expanding a query applied to the database of documents by replacing only words of the query, being of the original granularity, meeting a predetermined criterion, which is whether the words can be found in a lexical dictionary, with corresponding ones of the higher granularity concepts,

a)(i) wherein the higher granularity concepts are higher granularity semantic concepts,

a)(ii) further logically expanding the query by adding syntactically related words for each of the corresponding ones of the higher granularity concepts;

a)(iii) further logically expanding the query by adding syntactically related words for each of the words in the query failing to meet the predetermined criterion;

a)(iv) replacing ones of the syntactically related words meeting the predetermined criterion with associated ones of the higher granularity concepts; and

a)(v) removing any redundant ones of the syntactically related words and higher granularity concepts from the expanded query;

b) executing the logically expanded query to retrieve documents associated, through the index, with the corresponding ones of the higher granularity concepts; and

c) retrieving ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved, wherein the retrieved ones of the documents are ranked using the words of the query, being of the original granularity,

15. The method according to claim 14, wherein the higher granularity semantic concepts each contain synonyms.

16. The method according to claim 14, wherein the higher granularity concepts are higher granularity syntactical concepts.

17. The method according to claim 16, wherein the higher granularity syntactical concepts each contain words co-occurring in ones of the documents above a threshold level of frequency.

18. The method according to claim 14, wherein the words failing to meet the predetermined criterion are proper nouns.

19. The method according to claim 14, where the syntactically related words are words co-occurring in one of the documents above a threshold level of frequency.

20. The method according to claim 14, wherein the order of relevance is an exact match, a semantic match, a syntactical match and no match between the words of the query and words in the retrieved ones of the documents.

21. The method according to claim 14, wherein ones of the words of original granularity contained in the documents correspond to multiple ones of the higher granularity concepts.

22. The method according to claim 14, wherein the step of executing progresses in successive stages until a predetermined number of the ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved.

23. The method according to claim 22, wherein each of the stages represents a class of expansion.

24. The method according to claim 22, wherein each of the stages represents a slot within a class of expansion.

25. The method according to claim 22, wherein within each of the stages, the ones of the documents are retrieved in an order reflecting a level of importance assigned to at least one of the words of the query.

26. A system for querying a database of documents, the database including a preliminary index of the documents, words contained in the documents and associations therebetween, the words in the preliminary index being of an original granularity, the system comprising:

a) an indexer for replacing the words in the preliminary index with corresponding higher granularity concepts, resulting in a coarser granularity index of reduced index size;

b) a user interface for providing a query to be applied to the database of documents; and

c) a processor for logically expanding the query by replacing only the words of the query, being of the original granularity, meeting a predetermined criterion, which is whether the words can be found in a lexical dictionary, with corresponding ones of the higher granularity concepts, whereupon the processor executes the logically expanded query to retrieve ones of the documents associated, through the coarser granularity index, with the corresponding ones of the higher granularity concepts, wherein the processor retrieves ones of the documents in order of relevance until a predetermined number of ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved, using the words of the query, being of the original granularity, and wherein the order of relevance is an exact match, a semantic match, a syntactical match and no match between the words of the query and the words contained in the retrieved ones of the documents,

c)(i) wherein the higher granularity concepts are higher granularity semantic concepts, and wherein logically expanding the query further comprises;

c)(ii) adding syntactically related words for each of the corresponding ones of the higher granularity concepts;

c)(iii) adding syntactically related words for each of the words in the query failing to meet the predetermined criterion;

c)(iv) replacing ones of the syntactically related words meeting the predetermined criterion with associated ones of the higher granularity concepts; and

c)(v) removing any redundant ones of the syntactically related words and higher granularity concepts from the expanded query.

27. The system according to claim 26, wherein the higher granularity concepts are higher granularity semantic concepts.

28. The system according to claim 27, wherein the higher granularity semantic concepts each contain synonyms.

29. The system according to claim 26, wherein in the indexer replaces only ones of the words in the preliminary index meeting a predetermined criterion by the corresponding higher granularity concepts.

30. The system according to claim 29, wherein the predetermined criterion is whether the words can be found in a lexical dictionary.

31. The system according to claim 26, wherein the higher granularity concepts are higher granularity syntactical concepts.

32. The system according to claim 31, wherein the higher granularity syntactical concepts each contain words co-occurring in ones of the documents above a threshold level of frequency.

33. The system according to claim 26, wherein ones of the words in the preliminary index having multiple meanings are replaced by multiple ones of the corresponding higher granularity concepts.

34. The system according to claim 26, wherein words failing to meet the predetermined criterion are proper nouns.

35. The system according to claim 26, wherein the execution of the query progresses in successive stages until a predetermined number of the ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved.

36. The method according to claim 35, wherein each of the stages represents a class of expansion.

37. The method according to claim 35, wherein each of the stages represents a slot within a class of expansion.

38. The system according to claim 35, wherein within each of the stages, the ones of the documents are retrieved in an order reflecting a level of importance assigned to at least one of the words of the query.

39. A system of querying a database of documents, the database including an index of reduced index size of the documents, higher granularity concepts and associations there between, the higher granularity concepts corresponding to words of original granularity contained in the documents, the system comprising:

a) a user interface for providing a query to be applied to the database of documents; and

b) a processor for logically expanding the query replacing only words of the query meeting a predetermined criterion, which is whether the words can be found in a lexical dictionary, being of the original granularity, with corresponding ones of the higher granularity concepts, whereupon the processor executes the logically expanded query to retrieve documents associated, throughout the index, with the corresponding ones of the higher granularity concepts,

b)(i) wherein the higher granularity concepts are higher granularity semantic concepts, and wherein the processor logically expands the query by further;

b)(ii) adding syntactically related words for each of the corresponding ones of the higher granularity concepts;

b)(iii) adding syntactically related words for each of the words in the query failing to meet the predetermined criterion;

b)(iv) replacing ones of the syntactically related words meeting the predetermined criterion with associated ones of the higher granularity concepts; and

b)(v) removing any redundant ones of the syntactically related words and higher granularity concepts from the expanded query, wherein the processor further retrieves ones of the documents in order of relevance until a predetermined number of ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved.

40. The system according to claim 39, wherein the higher granularity semantic concepts each contain synonyms.

41. The system according to claim 39, the higher granularity concepts are higher granularity syntactical concepts.

42. The system according to claim 41, wherein the higher granularity syntactical concepts each contain words co-occurring in ones of the documents above a threshold level of frequency.

43. The system according to claim 39, wherein the words failing to meet the predetermined criterion are proper nouns.

44. The system according to claim 39, where the syntactically related words are words co-occurring in one of the documents above a threshold level of frequency.

45. The system according to claim 39, wherein the order of relevance is an exact match, a semantic match, a syntactical match and no match between the words of the query and words in the retrieved ones of the documents.

46. The system according to claim 39, wherein ones of the words of original granularity contained in the documents correspond to multiple ones of the higher granularity concepts.

47. The system according to claim 39, wherein the execution of the query progresses in successive stages until a predetermined number of the ones of the documents associated with the corresponding ones of the higher granularity concepts are retrieved.

48. The method according to claim 47, wherein each of the stages represents a class of expansion.

49. The method according to claim 47, wherein each of the stages represents a slot within a class of expansion.

50. The system according to claim 47, wherein within each of the stages, the ones of the documents are retrieved in an order reflecting a level of importance assigned to at least one of the words of the query.