Source: http://www.google.com/patents/US7644097?dq=5,963,646
Timestamp: 2017-12-18 05:27:09
Document Index: 229471421

Matched Legal Cases: ['art.\n2', 'art.\n4', 'art.\n7', 'art.\n10', 'art.\n11', 'art,\n15', 'art.\n16', 'art.\n17', 'art.\n18', 'art.\n21', 'art.\n24', 'art.\n25', 'art,\n29', 'art.\n30', 'art.\n31', 'art.\n37', 'art.\n40', 'art.\n41', 'art,\n45', 'art.\n46', 'art.\n47', 'art.\n49', 'art.\n52', 'art.\n53', 'art,\n57', 'art.\n58', 'art.\n59', 'art) 111', 'art 108', 'art 109', 'art 110', 'art) 112', 'art 204', 'art 211', 'art 204', 'art 209', 'art 210', 'art 204', 'art 211', 'art 204', 'art 212']

Patent US7644097 - Full-text search device performing merge processing by using full-text index ... - Google Patents
When a number of document data registered in one of full-text index-for-registration/deletion storage parts reaches a predetermined number, or when a capacity of the full-text index-for-registration/deletion storage part reaches a predetermined capacity, a merge processing is performed for merging data...http://www.google.com/patents/US7644097?utm_source=gb-gplus-sharePatent US7644097 - Full-text search device performing merge processing by using full-text index-for-registration/deletion storage part with performing registration/deletion processing by using other full-text index-for-registration/deletion storage part
Publication number US7644097 B2
Application number US 11/647,380
Also published as CN1297933C, CN1477564A, US7702666, US7730069, US20040006555, US20070118543, US20070136258
Publication number 11647380, 647380, US 7644097 B2, US 7644097B2, US-B2-7644097, US7644097 B2, US7644097B2
Inventors Kensaku Yamamoto, Yasushi Ogawa, Tetsuya Ikeda, Takuya Hiraoka, Hiroshi Takegawa, Kazushige Asada
Patent Citations (26), Non-Patent Citations (5), Referenced by (4), Classifications (10), Legal Events (3)
Full-text search device performing merge processing by using full-text index-for-registration/deletion storage part with performing registration/deletion processing by using other full-text index-for-registration/deletion storage part
US 7644097 B2
1. A full-text search device searching for document data including a search condition input from a document data storage part, which stores input document data, with the use of a first full-text index storage part for registration and a second full-text index storage part for search, the device comprising:
a registration processing part which obtains tokens and appearance position information of the tokens from the document data, and stores the tokens and the appearance position information of the tokens in the first full-text index storage part for registration;
a deletion processing part which determines whether tokens obtained from a document to be deleted are stored in the first full-text index storage part, and deletes the appearance position information of the tokens obtained from the document to be deleted from the first full-text index storage part when the tokens obtained from the document to be deleted are stored in the first full-text index storage part;
a search processing part which obtains a first set of tokens of document data including the input search condition with the use of an index of the first full-text index storage part, obtains a second set of tokens of document data including the input search condition with the use of an index of the second full-text index storage part, and subsequently outputs, as a search result, a set obtained from a union of the first and second sets;
a merging part which carries out merge processing by adding inverted lists of tokens from the first full-text index storage part to inverted lists of tokens corresponding to the index of the second full-text index storage part, and subsequently emptying the index of the first full-text index storage part.
2. The full-text search device as claimed in claim 1, wherein said merging part performs the merge processing of merging data from said first full-text index storage part to said second full-text index storage part for each of inverted lists composing the full-text index.
3. A full-text search device searching for document data including a search condition input from a document data storage part, which stores input document data, with the use of a first full-text index storage part for registration, a second full-text index storage part for deletion and a third full-text index storage part for search, the device comprising:
a deletion processing part which determines whether tokens obtained from a document to be deleted are stored in the first full-text index storage part, deletes the appearance position information of the tokens obtained from the document to be deleted from the first full-text index storage part when the tokens obtained from the document to be deleted are stored in the first full-text index storage part, and registers the tokens obtained from the document to be deleted and the appearance position information of the tokens obtained from the document to be deleted in the second full-text index storage part when the tokens obtained from the document to be deleted are not stored in the first full-text index storage part for registration;
a search processing part which obtains a first set of tokens of document data including the input search condition with the use of an index of the third full-text index storage part, obtains a second set of tokens of document data including the input search condition with the use of an index of the first full-text index storage part, obtains a third set of tokens of document data including the input search condition with the use of an index of the second full-text index storage part, and subsequently outputs, as a search result, a set obtained from subtracting the third set from a union of the first and second sets;
a merging part which carries out merge processing by adding inverted lists of tokens from the first full-text index storage part to inverted lists of tokens corresponding to the index of the third full-text index storage part, deleting appearance position information of tokens in inverted lists from the second full-text index storage part from inverted lists of tokens corresponding to the index of the third full-text index storage part, and subsequently emptying the index of the first full-text index storage part and the index of the second full-text index storage part.
4. The full-text search device as claimed in claim 3, wherein said merging part performs the merge processing of merging data from said first full-text index storage part and said second full-text index storage part to said third full-text index storage part for each of inverted lists composing the full-text index.
5. The full-text search device as claimed in claim 3, wherein said merging part performs the merge processing of merging data to said third full-text index storage part when a number of document data registered in said first full-text index storage part reaches a predetermined number.
6. The full-text search device as claimed in claim 5, comprising a plurality of the first full-text index storage parts,
wherein said registration processing part performs the registration processing by using another first full-text index storage part different from the first full-text index storage part undergoing the merge processing of merging data to said third full-text index storage part.
7. The full-text search device as claimed in claim 5, comprising two first full-text index storage parts,
wherein, while said merging part performs the merge processing of merging data from one of said two first full-text index storage parts to said third full-text index storage part, said registration processing part performs the registration processing by using the other of said two first full-text index storage parts.
8. The full-text search device as claimed in claim 5, comprising a storage part management part managing another first full-text index storage part different from said first full-text index storage part,
wherein said storage part management part newly creates another first full-text index storage part when there exists no first full-text index storage part in which the full-text index for registration can be stored upon said registration processing.
9. The full-text search device as claimed in claim 8, wherein said storage part management part deletes an excessive first full-text index storage part.
10. The full-text search device as claimed in claim 8, wherein, while said merging part performs the merge processing of merging data from one of the first full-text index storage parts to said third full-text index storage part, said registration processing part performs the registration processing by using another first full-text index storage part.
11. The full-text search device as claimed in claim 3, wherein said merging part performs the merge processing of merging data to said third full-text index storage part when a capacity of said first full-text index storage part reaches a predetermined capacity.
12. The full-text search device as claimed in claim 11, comprising a plurality of the first full-text index storage parts,
13. The full-text search device as claimed in claim 11, comprising two first full-text index storage parts,
14. The full-text search device as claimed in claim 11, comprising a storage part management part managing another first full-text index storage part different from said first full-text index storage part,
15. The full-text search device as claimed in claim 14, wherein said storage part management part deletes an excessive first full-text index storage part.
16. The full-text search device as claimed in claim 14, wherein, while said merging part performs the merge processing of merging data from one of the first full-text index storage parts to said third full-text index storage part, said registration processing part performs the registration processing by using another first full-text index storage part.
17. A full-text search device searching for document data including a search condition input from a document data storage part, which stores input document data, with the use of a first full-text index storage part for registration, a second full-text index storage part for deletion and a third full-text index storage part for search, the device comprising:
a merging part which carries out merge processing by deleting appearance position information of tokens in inverted lists from the first full-text index storage part from inverted lists of tokens corresponding to the index of the second full-text index storage part, and subsequently emptying the index of the first full-text index storage part.
18. The full-text search device as claimed in claim 17, wherein said merging part performs the merge processing of merging data from said second full-text index storage part to said third full-text index storage part for each of inverted lists composing the full-text index.
19. The full-text search device as claimed in claim 17, wherein said merging part performs the merge processing of merging data to said third full-text index storage part when a number of document data registered in said second full-text index storage part reaches a predetermined number.
20. The full-text search device as claimed in claim 19, comprising a plurality of the second full-text index storage parts,
wherein said deletion processing part performs the deletion processing part processing by using another second full-text index storage part different from the second full-text index storage part undergoing the merge processing of merging data to said third full-text index storage part.
21. The full-text search device as claimed in claim 19, comprising two second full-text index storage parts,
wherein, while said merging part performs the merge processing of merging data from one of said two second full-text index storage parts to said third full-text index storage part, said deletion processing part performs the deletion processing by using the other of said two second full-text index storage parts.
22. The full-text search device as claimed in claim 19, comprising a storage part management part managing another second full-text index storage part different from said second full-text index storage part,
wherein said storage part management part newly creates another second full-text index storage part when there exists no second full-text index storage part in which the full-text index for deletion can be stored upon said deletion processing.
23. The full-text search device as claimed in claim 22, wherein said storage part management part deletes an excessive second full-text index storage part.
24. The full-text search device as claimed in claim 22, wherein, while said merging part performs the merge processing of merging data from one of the second full-text index text index for deletion storage parts to said third full-text index storage part, said deletion processing part performs the deletion processing by using another second full-text index storage part.
25. The full-text search device as claimed in claim 17, wherein said merging part performs the merge processing of merging data to said third full-text index storage part when a capacity of said second full-text index storage part reaches a predetermined capacity.
26. The full-text search device as claimed in claim 25, comprising a plurality of the second full-text index storage parts,
27. The full-text search device as claimed in claim 25, comprising two second full-text index storage parts,
28. The full-text search device as claimed in claim 25, comprising a storage part management part managing another second full-text index storage part different from said second full-text index storage part,
29. The full-text search device as claimed in claim 28, wherein said storage part management part deletes an excessive second full-text index storage part.
30. The full-text search device as claimed in claim 28, wherein, while said merging part performs the merge processing of merging data from one of the second full-text index storage parts to said third full-text index storage part, said deletion processing part performs the deletion processing by using another second full-text index storage part.
31. A full-text search method in a full-text search system including a document data storage part for storing registered document data, a first full-text index storage part for registration, a second full-text index storage part for search, a registration processing part for performing a registration processing with respect to document data, a deletion processing part for performing a deletion processing with respect to document data, and a search processing part for performing a search processing so as to search for a document containing a specified character string from a plurality of document data, the method comprising:
an index storage step of storing a full-text index for registration in the first full-text index storage part provided aside from said second full-text index storage part; and
a merging step of merging data by adding inverted lists of tokens from the first full-text index storage part to inverted lists of tokens corresponding to the index of the second full-text index storage part, and subsequently emptying the index of the first full-text index storage part; and
a search step of searching for document data including a search condition input from the document data storage part by obtaining a first set of tokens of document data including the input search condition with the use of an index of the first full-text index storage part, obtaining a second set of tokens of document data including the input search condition with the use of an index of the second full-text index storage part, and subsequently outputting, as a search result, a set obtained from a union of the first and second sets.
32. The full-text search method as claimed in claim 31, wherein said merging step merges data from said first full-text index storage part to said second full-text index storage part for each of inverted lists composing the full-text index.
33. A full-text search method in a full-text search system including a document data storage part for storing registered document data, a first full-text index storage part for registration, a second full-text index storage part for deletion, a third full-text index storage part for search, a registration processing part for performing a registration processing with respect to document data, a deletion processing part for performing a deletion processing with respect to document data, and a search processing part for performing a search processing so as to search for a document containing a specified character string from a plurality of document data, the method comprising:
an index storage step of storing a full-text index for registration and a full-text index for deletion respectively in the first full-text index storage part and the second full-text index storage part provided aside from said third full-text index storage part;
a merging step of merging data by adding inverted lists of tokens from the first full-text index storage part to inverted lists of tokens corresponding to the index of the third full-text index storage part, deleting appearance position information of tokens in inverted lists from the second full-text index storage part from inverted lists of tokens corresponding to the index of the third full-text index storage part, and subsequently emptying the index of the first full-text index storage part and the index of the second full-text index storage part; and
a search step of searching for document data including a search condition input from the document data storage part by obtaining a first set of tokens of document data including the input search condition with the use of an index of the third full-text index storage part, obtaining a second set of tokens of document data including the input search condition with the use of an index of the first full-text index storage part, obtaining a third set of tokens of document data including the input search condition with the use of an index of the second full-text index storage part, and subsequently outputting, as a search result, a set obtained from subtracting the third set from a union of the first and second sets.
34. The full-text search method as claimed in claim 33, wherein said merging step merges data from said first full-text index storage part and said second full-text index storage part to said third full-text index storage part for each of inverted lists composing the full-text index.
35. The full-text search method as claimed in claim 33, wherein said merging step merges data to said third full-text index storage part when a number of document data registered in said first full-text index storage part reaches a predetermined number.
36. The full-text search method as claimed in claim 35, wherein said full-text search system includes a plurality of the first full-text index storage parts, and
the registration processing is performed by using another first full-text index storage part different from the first full-text index storage part undergoing the merging step of merging data to said third full-text index storage part.
37. The full-text search method as claimed in claim 35, wherein said full-text search system includes two first full-text index storage parts,
wherein, while said merging step merges data from one of said two first full-text index storage parts to said third full-text index storage part, the registration processing is performed by using the other of said two first full-text index storage parts.
38. The full-text search method as claimed in claim 35, comprising a storage part management step of managing another first full-text index storage part different from said first full-text index storage part,
wherein said storage part management step includes a step of newly creating another first full-text index storage part when there exists no first full-text index storage part in which the index storage step can store the full-text index for registration upon said registration processing.
39. The full-text search method as claimed in claim 38, wherein said storage part management step includes a step of deleting an excessive first full-text index storage part.
40. The full-text search method as claimed in claim 38, wherein, while said merging step merges data from one of the first full-text index storage parts to said third full-text index storage part, said registration processing part performs the registration processing by using another first full-text index storage part.
41. The full-text search method as claimed in claim 33, wherein said merging step merges data to said third full-text index storage part when a capacity of said first full-text index storage part reaches a predetermined capacity.
42. The full-text search method as claimed in claim 41, wherein said full-text search system includes a plurality of the first full-text index storage parts, and
43. The full-text search method as claimed in claim 41, wherein said full-text search system includes two first full-text index storage parts,
44. The full-text search method as claimed in claim 41, comprising a storage part management step of managing another first full-text index storage part different from said first full-text index storage part,
45. The full-text search method as claimed in claim 44, wherein said storage part management step includes a step of deleting an excessive first full-text index storage part.
46. The full-text search method as claimed in claim 44, wherein, while said merging step merges data from one of the first full-text index storage parts to said third full-text index storage part, said registration processing part performs the registration processing by using another first full-text index storage part.
47. The full-text search method as claimed in claim 33, wherein said merging step merges data to said third full-text index storage part when a number of document data registered in said second full-text index storage part reaches a predetermined number.
48. The full-text search method as claimed in claim 47, wherein said full-text search system includes a plurality of the second full-text index storage parts, and
the deletion processing is performed by using another second full-text index storage part different from the second full-text index storage part undergoing the merging step of merging data to said third full-text index storage part.
49. The full-text search method as claimed in claim 47, wherein said full-text search system includes two second full-text index storage parts,
wherein, while said merging step merges data from one of said two second full-text index storage parts to said third full-text index storage part, the deletion processing is performed by using the other of said two second full-text index storage parts.
50. The full-text search method as claimed in claim 47, comprising a storage part management step of managing another second full-text index storage part different from said second full-text index storage part,
wherein said storage part management step includes a step of newly creating another second full-text index storage part when there exists no second full-text index storage part in which the index storage step can store the full-text index for deletion upon said deletion processing.
51. The full-text search method as claimed in claim 50, wherein said storage part management step includes a step of deleting an excessive second full-text index storage part.
52. The full-text search method as claimed in claim 50, wherein, while said merging step merges data from one of the second full-text index storage parts to said third full-text index storage part, said deletion processing part performs the deletion processing by using another second full-text index storage part.
53. The full-text search method as claimed in claim 33, wherein said merging step merges data to said third full-text index storage part when a capacity of said second full-text index storage part reaches a predetermined capacity.
54. The full-text search method as claimed in claim 53, wherein said full-text search system includes a plurality of the second full-text index storage parts, and
55. The full-text search method as claimed in claim 53, wherein said full-text search system includes two second full-text index storage parts,
56. The full-text search method as claimed in claim 53, comprising a storage part management step of managing another second full-text index storage part different from said second full-text index storage part,
57. The full-text search method as claimed in claim 56, wherein said storage part management step includes a step of deleting an excessive second full-text index storage part.
58. The full-text search method as claimed in claim 56, wherein, while said merging step merges data from one of the second full-text index storage parts to said third full-text index storage part, said deletion processing part performs the deletion processing by using another second full-text index storage part.
59. A full-text search method in a full-text search system including a document data storage part for storing registered document data, a first full-text index storage part for registration, a second full-text index storage part for deletion, a third full-text index storage part for search, a registration processing part for performing a registration processing with respect to document data, a deletion processing part for performing a deletion processing with respect to document data, and a search processing part for performing a search processing so as to search for a document containing a specified character string from a plurality of document data, the method comprising:
an index storage step of storing a full-text index for deletion in a second full-text index storage part provided aside from said third full-text index storage part; and
a merging step of merging data by deleting appearance position information of tokens in inverted lists from the second full-text index storage part from inverted lists of tokens corresponding to the index of the third full-text index storage part, and subsequently emptying the index of the second full-text index storage part; and
60. The full-text search method as claimed in claim 59, wherein said merging step merges data from said second full-text index storage part to said third full-text index storage part for each of inverted lists composing the full-text index.
61. A computer readable recording medium storing a full-text search program for causing a computer to function as a full-text search device searching for document data including a search condition input from a document data storage part, which stores input document data, with the use of a first full-text index storage part for registration, a second full-text index storage part for deletion and a third full-text index storage part for search, comprising:
62. A computer readable recording medium storing a full-text search program for causing a computer to perform a full-text search method in a full-text search system including a document data storage part for storing registered document data, a first full-text index storage part for registration, a second full-text index storage part for deletion, a third full-text index storage part for search, a registration processing part for performing a registration processing with respect to document data, a deletion processing part for performing a deletion processing with respect to document data, and a search processing part for performing a search processing so as to search for a document containing a specified character string from a plurality of document data, comprising:
Completely isolating transactions guarantees the consistency of data at any point of time. However, a reduction in a concurrent execution property may result in a reduction in a throughput as a whole considerably. In order to solve this problem, a concept of an isolation level is used. The isolation level is explained in detail in (2) “‘A Critique of ANSI SQL Isolation Levels’ Hal Bereson, Philip A Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, Patrick E. O'Neil Proc. ACM SIGMOD Conf. (June 1995) p. 1-10”.
FIG. 18 is a chart for explaining a merge processing by taking an inverted list of a token
in the full-text index shown in FIG. 17 as an example;
S (Sharing) Used in read-only processing, such as SELECT
X (Exclusion) Used in data-changing processing, such as
UPDATE, INSERT or DELETE, to avoid
simultaneously updating one resource
IS (Intent Indicating presence of transaction for reading
Sharing) an S-locked resource in a lower tier
IX (Intent Indicating presence of transaction for changing
Exclusion) an X-locked resource in a lower tier
SIX (Sharing with Allowing simultaneous reading of a resource with
Intent Exclusion) indicating presence of transaction to change an
IX-locked resource in a lower tier
6. Apply a lock on a table (target of operation: tuples; content of operation: reading and writing).
A merging part (a data transfer part) 111 performs data transferring among the large-scale full-text index-for-search storage part 108, the small-scale full-text index-for-registration storage part 109, and the small-scale full-text index-for-deletion storage part 110. A merge time storage part (a data transfer time storage part) 112 records a time required for a data transfer.
in the full-text-index 163 shown in FIG. 17 as an example.
Next, a description will be given of a full-text search device according to a ninth embodiment of the present invention, in which a write delay database management method/device, which is described in still another patent application filed also by the applicant of the present application, is applied to the full-text search device according to the foregoing embodiment. The full-text search device according to the present embodiment solves a problem that, while performing a data transfer (a merge processing of inverted lists) from a small-scale full-text index for registration or, for deletion to a large-scale full-text index for search, the small-scale full-text index storage part for registration or for deletion cannot be used, and a registration processing or a deletion processing cannot be performed.
When the merge starting condition is fulfilled, and either of the other small-scale full-text index-for-deletion storage parts B (210 b) and C (210 c) is not undergoing a merge processing (NO in step ST107/ST108), the deletion processing part 204 starts the same merge processing (steps ST111-ST113) as in steps ST59-ST61 shown in FIG. 26 with respect to the small-scale full-text index-for-deletion A in the small-scale full-text index-for-deletion storage part A (210 a), and switches the storage parts to which the recording is performed for a next deletion processing, from the small-scale full-text index-for-deletion storage part A (210 a) to another small-scale full-text index-for-deletion storage part B (210 b)/C (210 c) (step ST109/ST111). When the merge processing is started, the merging part 211 performs the merge processing asynchronously with the deletion processing part 204.
Besides, in the present eleventh embodiment, the small-scale full-text index-for-registration storage part 209 described with reference to FIG. 19 timely increases a number of storage parts from only the small-scale full-text index-for-registration storage part A (209 a) to the small-scale full-text index-for-registration storage parts B (209 b), C (209 c), D (209 d), (in random order), and timely deletes these storage parts. The small-scale full-text index-for-deletion storage part 210 described with reference to FIG. 19 timely increases a number of storage parts from only the small-scale full-text index-for-deletion storage part A (210 a) to the small-scale full-text index-for-deletion storage parts B (210 b), C (210 c), D (210 d), . . . , (in random order), and timely deletes these storage parts.
When the merge starting condition is fulfilled, and the other small-scale full-text index-for-deletion storage part B (210 b)/A (210 a) is not undergoing a merge processing (NO in step ST170), the deletion processing part 204 starts a similar merge processing (steps ST172-ST174) as in steps ST59-ST61 shown in FIG. 26 with respect to the small-scale full-text index-for-deletion A/C in the small-scale full-text index-for-deletion storage part A (210 a)/C, and switches the storage parts to which the recording is performed for a next deletion processing, from the small-scale full-text index-for-deletion storage part A (210 a)/C to the other small-scale full-text index-for-deletion storage part B (210 b)/A (210 a) (step ST171). When the merge processing is started, the merging part 211 performs the merge processing asynchronously with the deletion processing part 204. Besides, the storage part management part 212 may delete excessive full-text index-for-deletion storage parts (not to be used in She next processing) upon the merge processing, or timely.
US6097797 May 18, 1998 Aug 1, 2000 Ricoh Company, Ltd. Network facsimile apparatus capable of E-mail communications
US6286004 Dec 7, 1998 Sep 4, 2001 Ricoh Company, Ltd. Distributed type of database system, consistency managing method for the same, and a computer-readable recording medium with a program for making a computer execute each step of the method stored therein
US6546383 Jun 9, 2000 Apr 8, 2003 Ricoh Company, Ltd. Method and device for document retrieval
US6640225 * Sep 29, 2000 Oct 28, 2003 International Business Machines Corporation Search method using an index file and an apparatus therefor
US7016914 Jun 5, 2002 Mar 21, 2006 Microsoft Corporation Performant and scalable merge strategy for text indexing
US20030033297 Jul 31, 2002 Feb 13, 2003 Yasushi Ogawa Document retrieval using index of reduced size
US20030220950 Nov 26, 2002 Nov 27, 2003 Takuya Hiraoka Database controlling system
JP2000163294A Title not available
JPH0198020A Title not available
JPH1173429A Title not available
JPH07146880A Title not available
JPH09265420A Title not available
JPH10143412A Title not available
JPH10240754A Title not available
Cooperative Classification Y10S707/99942, G06F17/30622, G06F17/30631, G06F17/30613
European Classification G06F17/30T1P1, G06F17/30T1P9, G06F17/30T1