SUPPORTING WEB-QUERY EXPANSION EFFICIENTLY USING MULTI-GRANULARITY INDEXING AND QUERY PROCESSING

• US 20020059161A1
• Filed: 11/03/1998
• Published: 05/16/2002
• Est. Priority Date: 11/03/1998
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: LI, WEN-SYAN
• Granted Patent: US 6,480,843 B2
• Time in Patent Office: Days
• US Class Current: 707/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 words of the query, being of the original granularity, with corresponding ones of the higher granularity concepts; and

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.

2. The method according to claim 1, further comprising

d) ranking the retrieved ones of the documents in order of relevance.

3. The method according to claim 2, wherein in the ranking step, the retrieved ones of the documents are ranked using the words of the query, being of the original granularity.

4. The method according to claim 3, 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.

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

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

7. 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.

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

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

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

11. The method according to claim 1, wherein the step of logically expanding the query further comprises:

b)(i) replacing only the words of the query meeting a predetermined criterion with the corresponding ones of the higher granularity concepts, wherein the higher granularity concepts are higher granularity semantic concepts.

12. The method according to claim 11, wherein the step of logically expanding the query further comprises:

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

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.

13. The method according to claim 12, wherein the step of logically expanding the query further comprises the steps of:

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.

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

15. 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.

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

17. 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.

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

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

20. The method according to claim 17, 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.

21. A method of querying a database of documents, the database including an index of reduced 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 words of the query, being of the original granularity, with corresponding ones of the higher granularity concepts; and

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

22. The method according to claim 21, wherein the step of logically expanding the query further comprises:

a)(i) replacing only words of the query meeting a predetermined criterion with the corresponding ones of the higher granularity concepts, wherein the higher granularity concepts are higher granularity semantic concepts.

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

24. The method according to claim 21, wherein the higher granularity concepts are higher granularity syntactical concepts.

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

26. The method according to claim 22, wherein the step of logically expanding the query further comprises:

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

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.

27. The method according to claim 26, wherein the step of logically expanding the query further comprises the steps of:

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.

28. The method according to claim 27, wherein the predetermined criterion is whether the word can be found in a lexical dictionary.

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

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

31. The method according to claim 21, further comprising the step of:

c) ranking the retrieved ones of the documents in order of relevance.

32. The method according to claim 31, wherein the retrieved ones of the documents are ranked using the words of the query, being of the original granularity.

33. The method according to claim 32, 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.

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

35. The method according to claim 21, 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.

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 method 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.

40. The system according to claim 39, wherein the processor ranks the retrieved ones of the documents in order of relevance.

41. The system according to claim 40, wherein in the processor ranks the retrieved ones of the documents using the words of the query, being of the original granularity.

42. The system according to claim 41, 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.

43. The system according to claim 39, wherein the higher granularity concepts are higher granularity semantic concepts.

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

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

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

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

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

49. The system according to claim 39, wherein the processor logically expands the query by further:

c)(i) replacing only the words of the query meeting a predetermined criterion with the corresponding ones of the higher granularity concepts, wherein the higher granularity concepts are higher granularity semantic concepts.

50. The system according to claim 49, wherein the processor logically expands the query by further:

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

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

51. The system according to claim 50, wherein the processor logically expands the query by further:

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.

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

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

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

55. 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.

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

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

58. The system according to claim 55, 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.

60. The system according to claim 59, wherein the processor logically expands the query by further:

b)(i) replacing only words of the query meeting a predetermined criterion with the corresponding ones of the higher granularity concepts, wherein the higher granularity concepts are higher granularity semantic concepts.

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

62. The system according to claim 59, the higher granularity concepts are higher granularity syntactical concepts.

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

64. The system according to claim 60, 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; and

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

65. The system according to claim 64, wherein the processor logically expands the query by further:

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.

66. The system according to claim 65, wherein the predetermined criterion is whether the word can be found in a lexical dictionary.

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

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

69. The system according to claim 59, wherein the processor further ranks the retrieved ones of the documents in order of relevance.

70. The system according to claim 69, wherein the retrieved ones of the documents are ranked using the words of the query, being of the original granularity.

71. The system according to claim 70, 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.

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

73. The system according to claim 59, 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.

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

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

76. The system according to claim 73, 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 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 words of the query, being of the original granularity, 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.

59. 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 words of the query, 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.