Source: http://www.google.com/patents/US6622139?ie=ISO-8859-1
Timestamp: 2014-08-20 15:45:49
Document Index: 566641534

Matched Legal Cases: ['art 110', 'art 130', 'art 110', 'art 140', 'art 150', 'art 140', 'art 310', 'art 320', 'art 330', 'art 340', 'art 330']

Patent US6622139 - Information retrieval apparatus and computer-readable recording medium ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsIn retrieval in which information having meaningful consistence is regarded as one unit, useful information within a hypertext structure retrieved is rendered capable of being effectively perused. A node group constituting part constitutes node groups to be retrieved on the basis of combination through...http://www.google.com/patents/US6622139?utm_source=gb-gplus-sharePatent US6622139 - Information retrieval apparatus and computer-readable recording medium having information retrieval program recorded thereinAdvanced Patent SearchPublication numberUS6622139 B1Publication typeGrantApplication numberUS 09/377,057Publication dateSep 16, 2003Filing dateAug 19, 1999Priority dateSep 10, 1998Fee statusPaidPublication number09377057, 377057, US 6622139 B1, US 6622139B1, US-B1-6622139, US6622139 B1, US6622139B1InventorsTakehiro Nakayama, Hiroki Kato, Hidetaka MiyakeOriginal AssigneeFuji Xerox Co., Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (2), Non-Patent Citations (2), Referenced by (12), Classifications (10), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetInformation retrieval apparatus and computer-readable recording medium having information retrieval program recorded thereinUS 6622139 B1Abstract In retrieval in which information having meaningful consistence is regarded as one unit, useful information within a hypertext structure retrieved is rendered capable of being effectively perused. A node group constituting part constitutes node groups to be retrieved on the basis of combination through links and the degree of similarity in contents from information in a hyper-document system. A component node storing part stores node group identification address information sent from the node group constituting part. When a retrieval request is given, an information retrieval part calculates the degree of similarity between the retrieval request and the node group. A similarity calculation part acquires the component nodes of a node group similar to the retrieval request from the component node storing part, and calculates the degrees of similarity between the component nodes acquired and the retrieval condition profile to rank the component nodes. A similarity retrieval result display part displays access paths to each component node in such a manner that component nodes having a high ordinal rank in the degree of similarity can be distinguished.
SUMMARY OF THE INVENTION The present invention has been achieved in the light of the above-described points, and is aimed to provide an information retrieval apparatus capable of effectively perusing useful information within the hyper-text structure retrieved in the retrieval in which information having meaningful consistence is regarded as one unit.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a view showing the structure of a first embodiment of information retrieval apparatus according to the present invention;
DETAILED DESCRIPTION OF PREFERRED EMBODIMENT Embodiments of the Invention
The node group constituting part 110 constitutes node groups to be retrieved on the basis of combination through links and degrees of similarity in contents from information dispersedly arranged in the hyper-document system 10. More specifically, a node obtained by scanning a certain node existing in the hyper-document 10 at random is set to a starting point node. Next, a set of nodes, which can be reached by following links from the starting point node, and which have contents similar to the starting point node is determined to constitute a node group. A profile (hereinafter, referred to as �retrieval object profile�) indicating features of the contents of the node group thus constituted is generated, and is held by relating it to the identification address of the starting point node. Hereinafter, the node group generated can be specified by the identification address of the starting point node. In this respect, the identification address here means an absolute address uniquely given to the node, and indicates URL (Uniform Resource Locator) in the case of, for example, World Wide Web.
When a retrieval request (expressed in a keyword train, text or a hyper-structure) is given, the information retrieval part 130 generates a profile (hereinafter, referred to as �retrieval request profile�) representing the features of the contents of the retrieval request. Concretely, it analyzes the contents of the retrieval request, and extracts a pair of set consisting of words by which the contents of the retrieval request are characterized, and values indicating their importance to constitute the retrieval request profile. Thus, it calculates a degree of similarity between each retrieval object profile held by the node group constituting part 110 and the retrieval request profile. If the degrees of similarity between all node groups and the retrieval object profile have been obtained, starting point node identification addresses for the node groups, which have been sequenced in accordance with the magnitude of degree of similarity, are used as the retrieval result. The retrieval result and the retrieval request profile are supplied to the similarity calculation part 140. In this case, only node groups having degrees of similarity equal to or higher than a certain threshold may be narrowed down as candidates for retrieval result. In this respect, a known vector inner product operation method is used for calculation of the degree of similarity.
The similarity retrieval result displaying part 150 displays paths for accessing each node constituting the node groups obtained by the similarity calculation part 140 in such a manner that component nodes having high degrees of similarity to the retrieval request can be distinguished. This enables the user to recognize which component nodes are more similar to the retrieval condition among node groups similar to the retrieval condition. For example, the node groups are represented by a tree structure with the starting point node as a root, and a value of degree of similarity is indicated to each node. At this time, a path from the starting point node to a node having the highest degree of similarity is highlighted. In the example shown in the figure, the node having a degree of similarity of �0.33� has the highest degree of similarity. Since there is a high possibility that a node having a high degree of similarity contains useful information for the user, the user can effectively acquire useful information by giving priority to these nodes for browsing.
The component node feature profile generating unit 142 generates a profile (hereinafter, referred to as �component node profile�) representing the feature of the contents of a node acquired at the component node acquisition unit 141. The detail of the component node profile generation process is the same as the process shown in the flow-chart of FIG. 3.
FIG. 10 is a view showing an example of a node group extracted by the information retrieval part. In the node group shown in this example, there exist six nodes 11 to 16 as component nodes. A node 11 indicated as �root� is a starting point node. Also, three nodes 12, 15 and 16 exceed the threshold of the degree of similarity in retrieval request. The node 12 with the wording �first ordinal rank� is a node having the highest degree of similarity, the node 16 with the wording �second ordinal rank� is a node having the second highest degree of similarity, and the node 15 with the wording �third ordinal rank� is a node having the third highest degree of similarity. Arrows connecting between each node 11 to 16 designate links 21 to 26. As shown in FIG. 10, there are two paths along which the node 15 having the third degree of similarity is reached by following the links from the root node 11.
First, nodes of �first ordinal rank�, �second ordinal rank� and �third ordinal rank� are stored in the node table (step S21). Next, the node 12 of the �first ordinal rank� is selected from the node table (step S22), a link 21 from the �root� node 11 to the node 12 of the �first ordinal rank� is stored in the link table, and the node 12 of the �first ordinal rank� is deleted from the node table (step S23) . Next, the node of the �third ordinal rank�, which is a node reachable from the node of the �first ordinal rank�, is deleted from the node table, and the link 22 and the link 23 are added to the link table (step S24).
FIG. 12 is a view showing a node group displayed in accordance with the third embodiment. In the third embodiment, the paths will be indicated if the links can be followed from a node having higher degree of similarity to a node having lower degree of similarity as shown in FIG. 12. Accordingly, links 22 and 23 from the node 12 of the �first ordinal rank� to the node 15 of the �third ordinal rank� are displayed, and a link along which the node 15 of the �third ordinal rank� is reached from the �root� node 11 by way of the first node is not displayed.
An inter-node similarity calculation part 310 calculates a degree of similarity between nodes which are two pieces of information connected through a link from information dispersedly arranged in the hyper-document system 10. The similarity calculation process is the same as the process performed by the similarity determining unit 114 of FIG. 2. At this time, in a �node A� and a �node C�, a degree of similarity between the nodes connected through a link in the form of reference from the �node A� to the �node C� is represented by Sim(A, C). An inter-node similarity storing part 320 stores an inter-node degree of similarity calculated by the intern ode similarity calculation part.
A retrieval request similarity calculation part 330 calculates degrees of similarity between a retrieval request profile generated from a retrieval request and nodes representing individual pieces of information dispersedly arranged in the hyper-document system. The similarity calculation process is the same as the process performed by the similarity calculation unit 143 (shown in FIG. 5) according to the first embodiment. At this time, a degree of similarity between the �node C� and the retrieval request is represented by Sim (Q, C) . A retrieval request similarity storing part 340 stores the retrieval request similarity calculated by the retrieval request similarity calculation part 330.
FIG. 14 is a view showing an example of calculation for link weight between nodes by the link weight calculation part. When the �node C� is referred to from the �node A� and the �node C� is referred to from the �node B� as shown in FIG. 14, weight of link between �node A� and �node C�, and weight of link between �node B� and �node C� are calculated by W(A, C) Sim(A, C)�Sim(Q, C) and W(B, C)=Sim(B, C)�Sim(Q, C) respectively.
[S37] A node group referred to by the relation of �weight W >threshold� is extracted from the node M.
FIG. 16 is a view showing a part of information in the hyper-document system. In FIG. 16, nodes 31 and 32 with the wording �first ordinal rank� and �second ordinal rank� respectively are a node with the highest degree of similarity to the retrieval request and a node with the second highest degree respectively. Arrows indicated by solid lines connecting between 31 to 36 represent links 41 to 44 having weight equal to or higher than the threshold, and arrows indicated by broken lines represent links 45 and 46 having weight equal to or lower than the threshold.
First, the node 31 of the �first ordinal rank� having the highest degree of similarity to the retrieval request is selected, and the process is performed with the node 31 as a starting point in accordance with the flow-chart of FIG. 15. Whether or not the node 31 is contained in the existing node table is determined, but since nothing has been registered in the existing node table at this stage, the node 31 of the �first ordinal rank� is added to the node set NC, C1 and the existing node table respectively. The node 31 of the �first ordinal rank� is taken out from the node set NC, and nodes 33 and 35, to which this node refers, and whose weight exceeds the threshold, are added to the node set NC, C1 and the existing node table. Next, this operation is likewise repeated for the nodes 33 and 35 which are contained in the node set NC, and is repeated until the node set NC becomes empty. In this example, the node 31 of the �first ordinal rank�, the node 32 of the �second ordinal rank�, the node 33 and the node 35 are placed in the node set C1 to terminate the process.
Next, as �k=2�, a process with the node 32 of the �second ordinal rank� as the starting point is started, and the node 32 has already been contained in the existing node table. For this reason, the node set C2 is not prepared, but the process proceeds to a process with the node of the �third ordinal rank� as the starting point. Similarly hereinafter, the generation process for a node set is repeated until all nodes exceeding the threshold which has been given in advance are contained in any of the node set Ck.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5526443Nov 9, 1995Jun 11, 1996Xerox CorporationMethod and apparatus for highlighting and categorizing documents using coded word tokensUS6233571 *May 4, 1998May 15, 2001Daniel EggerMethod and apparatus for indexing, searching and displaying data* Cited by examinerNon-Patent CitationsReference1Gerard Salton et al. "Third Annual Symposium on Document Analysis and Information Retrieval" "Text Retrieval Using the Vector Processing Model" pp. 9-21, Apr. 11-13, 1994.2Paul S. Jacobs "Third Conference on Applied Natural Language Processing" "Joining Statistics with NLP for Text Categorization" pp. 178-185, Mar.-Apr. 3, 1992.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7191400 *Feb 2, 2001Mar 13, 2007Stanford UniversityMethods for generating and viewing hyperlinked pagesUS7203679 *Jul 29, 2003Apr 10, 2007International Business Machines CorporationDetermining structural similarity in semi-structured documentsUS7593961 *Apr 21, 2004Sep 22, 2009Canon Kabushiki KaishaInformation processing apparatus for retrieving image data similar to an entered imageUS7680812Sep 16, 2005Mar 16, 2010Telenor AsaMethod, system, and computer program product for searching for, navigating among, and ranking of documents in a personal webUS7693822May 21, 2007Apr 6, 2010International Business Machines CorporationApparatus of generating browsing paths for data and method for browsing dataUS7752198Apr 24, 2007Jul 6, 2010Telenor AsaMethod and device for efficiently ranking documents in a similarity graphUS8037403 *Jan 11, 2007Oct 11, 2011Kabushiki Kaisha ToshibaApparatus, method, and computer program product for extracting structured documentUS8112374 *Nov 22, 2006Feb 7, 2012Henry Van Dyke ParunakHierarchical ant clustering and foragingUS8285723Nov 27, 2009Oct 9, 2012Ntt Docomo, Inc.System and method for indexing documents and retrieving similar document based on link transition count distance calculationsCN100472522CAug 25, 2005Mar 25, 2009特里诺尔公司A method, system, and computer program product for searching for, navigating among, and ranking of documents in a personal webWO2006033763A2 *Aug 25, 2005Mar 30, 2006Telenor AsaA method, system, and computer program product for searching for, navigating among, and ranking of documents in a personal webWO2007123416A1 *Apr 24, 2007Nov 1, 2007Telenor AsaMethod and device for efficiently ranking documents in a similarity graph* Cited by examinerClassifications U.S. Classification707/749, 707/E17.013, 707/999.003, 707/758, 707/999.01International ClassificationG06F17/30, G06F12/00Cooperative ClassificationY10S707/99933, G06F17/30014European ClassificationG06F17/30D4Legal EventsDateCodeEventDescriptionFeb 22, 2011FPAYFee paymentYear of fee payment: 8Feb 16, 2007FPAYFee paymentYear of fee payment: 4Aug 19, 1999ASAssignmentOwner name: FUJI XEROX CO, LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:NAKAYAMA, TAKEHIRO;KATO, HIROKI;MIYAKE, HIDETAKA;REEL/FRAME:010190/0981Effective date: 19990812RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google