Document retrieval by information unit

• US 6,847,960 B1
• Filed: 12/14/1999
• Issued: 01/25/2005
• Est. Priority Date: 03/29/1999
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Wu, Yi-Leh, Candan, K. Selcuk, Li, Wen-Syan
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/461,561
• Time in Patent Office: 1,869 Days
• Field of Search: 707/5, 707/100, 707/102, 707/104.1, 704/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method of searching a search space comprising a plurality of pages in response to a query comprising a plurality of keywords includes identifying at least one information unit. Where a query includes exactly two keywords, an information unit comprises one page which contains both keywords in the query or two pages selected from the search space such that the first page in the information unit contains the first keyword in the query and the second page in the information unit contains the second keyword in the query; where an information unit contains two pages, one page is linked, directly or indirectly, to the other page. Relaxed query processing techniques enable the method to identify information units which do not contain every keyword in the query, which have only semantically similar words or synonyms, and which have keywords of differing relative importance. The method is adapted to report the identified information units and to accommodate altered queries provided as a result of a report.

Claims

1. A method of identifying an information unit in response to a query of a search space, the search space comprising a plurality of pages;

said method comprising;

(a) responsive to a query comprising a plurality of keywords, determining a set of pages within the search space wherein each page in said set of pages contains at least one of said plurality of keywords; and

(b) identifying at least one information unit comprising one or more pages selected from said set of pages such that each page in said information unit contains at least one of said plurality of keywords;

every page in said information unit being linked, directly or indirectly, to every other page in said information unit.

2. The method according to claim 1 wherein said one or more pages in said at least one information unit collectively contain all of said plurality of keywords.

3. The method according to claim 1 further comprising:

reporting said at least one information unit to a user.

4. The method according to claim 1 wherein, responsive to a request for relaxed query processing, said identifying at least one information unit is performed such that said information unit comprises a page which does not contain at least one of said plurality of keywords.

5. The method according to claim 1 further comprising:

(c) reporting said at least one information unit to a user or, in the alternative, reporting that an information unit which satisfies the query cannot be found; and

(d) responsive to an altered query provided as a result of said reporting, repeating (a) through (c) for said altered query.

6. The method according to claim 5 wherein said altered query is a query with one keyword added to said plurality of keywords and one keyword eliminated from said plurality of keywords.

7. The method according to claim 6 wherein, responsive to a request for relaxed query processing, said identifying at least one information unit is performed such that said information unit comprises a page which does not contain said one keyword added to said plurality of keywords.

8. The method according to claim 1 wherein said identifying at least one information unit comprises identifying a plurality of information units.

9. The method according to claim 1 wherein the search space is the World Wide Web.

10. The method according to claim 1 wherein the search space is an XML database.

11. The method according to claim 1 wherein said plurality of keywords is greater than two.

12. The method according to claim 1 wherein said plurality of keywords is two.

13. The method according to claim 12 wherein said identifying at least one information unit comprises:

(i) determining, from said set of pages, a first set of pages wherein each page in said first set of pages contains the first of said plurality of keywords, and a second set of pages wherein each page in said second set of pages contains the second of said plurality of keywords; and

(ii) identifying an intersection of said first set of pages and said second set of pages such that each page within said intersection contains both of said plurality of keywords;

each said page within said intersection being a separate information unit.

14. The method according to claim 13 wherein said identifying at least one information unit further comprises:

(iii) selecting links associated with said pages contained in said first set of pages and said second set of pages to identify a plurality of pairs of pages;

each of said plurality of pairs of pages containing two pages which are related such that a first page contains the first of said plurality of keywords and a second page contains the second of said plurality of keywords and said first page and said second page are linked directly by exactly one link;

each of said plurality of pairs of pages being a separate information unit;

each page associated with a selected link which does not contain either of said plurality of keywords being an intervening page.

15. The method according to claim 14 wherein said identifying at least one information unit further comprises:

(iv) selecting links associated with said pages contained in said first set of pages and said second set of pages and links associated with each said intervening page to identify additional pairs of pages;

each of said additional pairs of pages containing two pages which are related such that a first additional page contains the first of said plurality of keywords and a second additional page contains the second of said plurality of keywords and said first additional page and said second additional page are linked indirectly by more than one link through at least one of said intervening pages;

each said additional pair of pages being a separate information unit.

16. The method according to claim 15 wherein said identifying at least one information unit further comprises:

(v) repeating said selecting links associated with said pages contained in said first set of pages and said second set of pages and links associated with each said intervening page to identify further additional information units which contain remote pairs of pages;

each of said remote pairs of pages containing two pages which are related such that a first remote page contains the first of said plurality of keywords and a second remote page contains the second of said plurality of keywords and said first remote page and said second remote page are separated by more than one intervening page;

each said remote pair of pages being a separate information unit.

17. The method according to claim 14 wherein each said link is assigned a link cost.

18. The method according to claim 17 wherein each said information unit is assigned a cost based upon said link cost assigned to each said link associated with said pages in each said information unit.

19. The method according to claim 18 wherein said selecting links associated with said pages contained in said first set of pages and said second set of pages is based upon said link cost assigned to each said link such that a plurality of information units are identified in order of increasing cost;

said method further comprising;

reporting said plurality of identified information units in order of increasing cost.

20. The method according to claim 12 wherein the search space is the World Wide Web, the pages in said first and second sets of pages are pages on the World Wide Web, and the links between said pages are hyperlinks.

21. The method according to claim 12 wherein the search space is an XML database, the pages in said first and second sets of pages are data records in the XML database, and the links between said data records are dynamic links.

22. A method of identifying and reporting an information unit in response to a query of a search space, the search space comprising a plurality of pages;

said method comprising;

(a) responsive to a query comprising a plurality of keywords, determining a set of pages within the search space wherein each page in said set of pages contains at least one of said plurality of keywords;

(b) identifying at least one information unit comprising one or more pages selected from said set of pages such that each page in said information unit contains at least one of said plurality of keywords;

every page in said information unit being linked, directly or indirectly, to every other page in said information unit;

(c) reporting said at least one information unit to a user or, in the alternative, reporting that an information unit which satisfies the query cannot be found; and

(d) responsive to an altered query provided as a result of said reporting, repeating (a) through (c) for said altered query.

23. The method according to claim 22 wherein said one or more pages in said information unit collectively contain all of said plurality of keywords.

24. The method according to claim 22 wherein said identifying at least one information unit comprises identifying a plurality of information units.

25. The method according to claim 22 wherein the search space is the World Wide Web.

26. The method according to claim 22 wherein the search space is an XML database.

27. The method according to claim 22 wherein, responsive to a request for relaxed query processing, said identifying at least one information unit is performed such that said information unit comprises a page which does not contain at least one of said plurality of keywords.

28. The method according to claim 22 wherein said altered query is a query with one keyword added to said plurality of keywords and one keyword eliminated from said plurality of keywords.

29. The method according to claim 28 wherein, responsive to a request for relaxed query processing, said identifying at least one information unit is performed such that said information unit comprises a page which does not contain at least one of said plurality of keywords.

30. The method according to claim 22 wherein said plurality of keywords is greater than two.

31. The method according to claim 22 wherein said plurality of keywords is two.

32. The method according to claim 31 wherein said identifying at least one information unit comprises:

(i) determining, from said set of pages, a first set of pages wherein each page in said first set of pages contains the first of said plurality of keywords, and a second set of pages wherein each page in said second set of pages contains the second of said plurality of keywords; and

(ii) identifying an intersection of said first set of pages and said second set of pages such that each page within said intersection contains both of said plurality of keywords;

each said page within said intersection being a separate information unit.

33. The method according to claim 32 wherein said identifying at least one information unit further comprises:

(iii) selecting links associated with said pages contained in said first set of pages and said second set of pages to identify a plurality of pairs of pages;

each of said plurality of pairs of pages containing two pages which are related such that a first page contains the first of said plurality of keywords and a second page contains the second of said plurality of keywords and said first page and said second page are linked directly by exactly one link;

each of said plurality of pairs of pages being a separate information unit;

each page associated with a selected link which does not contain either of said plurality of keywords being an intervening page.

34. The method according to claim 33 wherein said identifying at least one information unit further comprises:

(iv) selecting links associated with said pages contained in said first set of pages and said second set of pages and links associated with each said intervening page to identify additional pairs of pages;

each of said additional pairs of pages containing two pages which are related such that a first additional page contains the first of said plurality of keywords and a second additional page contains the second of said plurality of keywords and said first additional page and said second additional page are linked indirectly by more than one link through at least one of said intervening pages;

each said additional pair of pages being a separate information unit.

35. The method according to claim 34 wherein said identifying at least one information unit further comprises:

(v) repeating said selecting links associated with said pages contained in said first set of pages and said second set of pages and links associated with each said intervening page to identify further additional information units which contain remote pairs of pages;

each of said remote pairs of pages containing two pages which are related such that a first remote page contains the first of said plurality of keywords and a second remote page contains the second of said plurality of keywords and said first remote page and said second remote page are separated by more than one intervening page;

each said remote pair of pages being a separate information unit.

36. The method according to claim 33 wherein each said link is assigned a link cost.

37. The method according to claim 36 wherein each said information unit is assigned a cost based upon said link cost assigned to each said link associated with said pages in each said information unit.

38. The method according to claim 31 wherein the search space is the World Wide Web, the pages in said first and second sets of pages are pages on the World Wide Web, and the links between said pages are hyperlinks.

39. The method according to claim 31 wherein the search space is an XML database, the pages in said first and second sets of pages are data records in the XML database, and the links between said data records are dynamic links.

40. The method according to claim 37 wherein said selecting links associated with said pages contained in said first set of pages and said second set of pages is based upon said link cost assigned to each said link such that a plurality of information units are identified in order of increasing cost;

said method further comprising;

reporting said plurality of identified information units in order of increasing cost.

41. A computer-based system for identifying and reporting an information unit in response to a query of a search space, the search space comprising a plurality of pages;

said system comprising;

means for receiving a query input;

said query input comprising a plurality of keywords; and

means, responsive to said query input, for identifying at least one information unit;

said at least one information unit comprising one or more pages within the search space selected such that each page in said information unit contains at least one of said plurality of keywords;

every page in said information unit being linked, directly or indirectly, to every other page in said information unit.

42. The computer-based system according to claim 41 further comprising:

means for reporting said at least one information unit to a user or, in the alternative, reporting that an information unit which satisfies the query cannot be found.

43. The computer-based system according to claim 41 further comprising:

means for receiving an altered query input.

44. The computer-based system according to claim 41 further comprising:

means for receiving a relaxed query processing input; and

means, responsive to said relaxed query processing input, for identifying at least one information unit comprising a page which does not contain at least one of said plurality of keywords.

45. The computer-based system according to claim 41 further comprising:

means for ranking said at least one information unit such that, if a plurality of information units are identified, said plurality of information units are ranked in order; and

means for reporting said plurality of identified information units in rank order.