JP5910337B2 - Information processing method and apparatus for concealment query - Google Patents

Description

  The present technology relates to search concealment technology.

  In recent years, the use of cloud computing by companies has been expanding. Among them, a cloud called an industry cloud is attracting attention. The industry cloud is a cloud that includes computer resources owned by a plurality of different organizations belonging to the same industry, and uses each resource mutually. For example, in the case of a medical cloud, it is obtained by combining computer resources possessed by a plurality of hospitals, and it is expected to provide advanced medical services to customers by exchanging medical information and the like possessed by each. In this way, the industry cloud aims to provide a higher quality service by effectively utilizing data each of which different organizations in the same industry have.

  For example, a credit cloud is known as one form of an industry cloud. The credit cloud stores credit information such as personal debt calendars owned by different organizations. More specifically, a so-called black list is managed. For this reason, when a financial institution such as a bank makes a loan to a customer, a credit cloud is used to investigate the creditworthiness of the customer. In the credit cloud, black lists from different organizations are accumulated, so that a very wide range of credit information can be provided by the credit cloud. On the other hand, since data from different organizations are combined, even the same person may be registered as different data. For example, “Watabe” from Company X may be registered as “Watabe” from Company Y. In order to absorb such data differences and distinguish the same person indicated by different data, a process called “name identification” is performed.

  In name identification, the similarity between two character strings is calculated, and if they are equal to or greater than a predetermined threshold, they are determined to be the same person. Various methods are known for calculating the similarity, but a method called an edit distance is generally used.

  The edit distance is a method for evaluating the similarity between character strings by “how many characters have been deleted, inserted, or replaced?”. For example, since “Watabe” is a character string obtained by deleting one character from “Watanabe”, the editing distance of “Watabe” viewed from “Watanabe” is 1D. However, D is a parameter representing a weight as an edit distance by deleting one character. On the contrary, since “Watanabe” is a character string in which one character is inserted into “Watabe”, the editing distance of “Watanabe” viewed from “Watabe” is 1I. Here, I is a parameter representing a weight as an editing distance by inserting one character.

  For example, the credit cloud has a black list database managed by a plurality of organizations, such as a database of company X and a database of company Y. A financial institution A such as a bank transmits a customer's customer name as a query to the credit cloud to investigate whether or not the customer is a blacklisted person. For this investigation, financial institution A sends its customer name “Watanabe Takashi” as a query to the credit cloud. In the credit cloud, the server that performs name identification processing receives the customer name “Watanabe Takashi” of financial institution A. The server performs a cross-sectional name identification process on the received “Watanabe Takashi” and the names included in each of the blacklist databases of multiple organizations. As a result, among the names listed in the black list, “Wata Takashi” whose similarity exceeds the threshold is selected as a name that matches the query, and is returned to the financial institution A as a query response. As described above, the financial institution A can perform a credit check as to whether or not its customer is a blacklisted person.

  However, in such a credit cloud, there are concerns about privacy issues. The first problem is that the company customer name is notified to the credit cloud as it is, and the company customer name to be investigated leaks to the credit cloud side. Further, when the company customer name is a blacklist person, the fact that the subject company customer name to be investigated is a blacklist person leaks to the credit cloud side.

  As a result, companies and organizations that send queries to the credit cloud are exposed to the risk of leaking important privacy information called their customer names. Such problems can be avoided by using a data encryption technology such as SSL (Secure Socket Layer) or VPN (Virtual Private Network) because the data is decrypted by the server that performs name identification inside the credit cloud. Can not. In order to cope with such information leakage, there is no technique for converting a query.

JP 2011-118545 A JP 2007-72959 A

  An object of the present technology is, according to one aspect, to provide a technology for concealing a query.

  The information processing method according to the present technology includes (A) an acquisition process for acquiring a second character string to be mixed with a first character string designated as a search target, and (B) a plurality of items included in the first character string. The third character string is generated by mixing the second character string with the first character string while maintaining the order relationship of the characters and the order relationship of the plurality of characters included in the second character string. And (C) a process of outputting a query including the third character string stored in the data storage unit to a search computer that performs a character string search using the edit distance. Including.

  The query can be kept secret.

FIG. 1 is a diagram illustrating a configuration example of a system according to the first embodiment. FIG. 2 is a functional block diagram of the client device. FIG. 3 is a diagram for explaining the outline of the first embodiment. FIG. 4 is a diagram for explaining a comparative example. FIG. 5 is a diagram for explaining confidentiality according to the first embodiment. FIG. 6 is a diagram for explaining confidentiality according to the first embodiment. FIG. 7 is a diagram for explaining the nature of the edit distance. FIG. 8 is a diagram showing a main processing flow in the first embodiment. FIG. 9 is a diagram showing a processing flow of concealment processing. FIG. 10 is a diagram illustrating a processing flow of the mixing process. FIG. 11 is a diagram illustrating a processing flow of the mixing process. FIG. 12 is a diagram illustrating a processing flow of the mixing process. FIG. 13 is a diagram illustrating a processing flow of the mixing process. FIG. 14 is a diagram illustrating a processing flow of search processing. FIG. 15 is a diagram illustrating a process flow of the edit distance calculation process. FIG. 16 is a diagram for explaining the edit distance calculation processing. FIG. 17 is a diagram for explaining the edit distance calculation processing. FIG. 18 is a diagram illustrating a processing flow of edit distance calculation processing. FIG. 19 is a diagram for explaining the edit distance calculation processing. FIG. 20 is a diagram illustrating an example of a co-occurrence table. FIG. 21 is a diagram illustrating an example of a co-occurrence table. FIG. 22 is a diagram illustrating a process flow of the concealment process according to the second embodiment. FIG. 23 is a diagram illustrating a processing flow of the extraction processing according to the second embodiment. FIG. 24 is a functional block diagram of a computer.

[Embodiment 1]
The system outline of this embodiment will be described with reference to FIG. In the example of FIG. 1, a search server 5 that performs name identification processing and one or a plurality of client devices 3 (3a and 3b in FIG. 1) are connected to a network 1 such as the Internet. The search server 5 is a server included in a credit cloud, for example, and includes, for example, a first DB 51 that stores data such as a black list of a first company, a second DB 52 that stores data such as a black list of a second company, and the like. They are connected and perform name identification processing across these databases. When the client device 3 transmits the query to the search server 5, the search server 5 extracts a character string whose edit distance from the character string included in the query is equal to or less than the threshold from the first DB 51 and the like, and the client device that is the query transmission source 3 is returned as a search result.

  A functional block diagram of the client device 3 is shown in FIG. The client device 3 includes an input unit 31, a first data storage unit 32, a second data storage unit 33, a first extraction unit 34, a third data storage unit 35, a mixing unit 36, and a fourth data storage. A unit 37, a query transmission unit 38, a search result reception unit 39, a fifth data storage unit 40, a second extraction unit 41, a sixth data storage unit 42, and an output unit 43.

  The input unit 31 accepts input of a character string such as a customer's first and last name to be subject to credit check from the user, and stores it in the first data storage unit 32.

  The second data storage unit 33 stores data as surname and first name candidates to be mixed by the mixing unit 36. The first extraction unit 34 extracts a predetermined number of last names and first names from the second data storage unit 33 and stores them in the third data storage unit 35. The mixing unit 36 mixes the character string stored in the first data storage unit 32 and the character string stored in the third data storage unit 35 while maintaining the appearance order of the characters included in the character string. Then, the mixed result is stored in the fourth data storage unit 37. The query transmission unit 38 transmits a query including data stored in the fourth data storage unit 37 to the search server 5.

  The search result receiving unit 39 receives the search result from the search server 5 and stores it in the fifth data storage unit 40. The second extraction unit 41 extracts a character string similar to a character string such as a customer's first and last name stored in the first data storage unit 32 from the search result stored in the fifth data storage unit 40, 6 is stored in the data storage unit 42. The output unit 43 outputs the data stored in the sixth data storage unit 42 to an output device such as a display device or another computer connected to the client device 3.

  Next, processing contents of the system shown in FIG. 1 will be described. First, the outline of the present embodiment will be described with reference to FIGS.

  In the present embodiment, the client terminal 3 mixes the search target character string “Watanabe Takashi” and the dummy character strings “Yoshida Daiki” and “Hiroyoshiko” while maintaining the appearance order in those character strings. As a result, the query “Hiwarotayoshiinabedayodatakashikiko” is generated and transmitted to the search server 5. In this way, the query itself is concealed. When the search server 5 receives the query, the search server 5 extracts a character string whose edit distance is equal to or less than a threshold value across the first DB 51 and the second DB 52. Here, “Watabe Takashi” and “Hirotaka Takako” are extracted. That is, on the search server 5 side, it is unknown whether one of “Watabe Takashi” or “Hirotaka Takako” was to be extracted. Even if only one character string is extracted, there may be different character strings such as “Watabe Takashi” and “Watana Takashi”. In addition, only “Hirotaka Takako” may be extracted. That is, the character string included in the query cannot be specified from the query result. Since the client device 3 holds the search target character string “Watabe Takashi”, it is possible to extract a similar character string “Watabe Takashi” from the query results “Watabe Takashi” and “Hirotaka Takako”. Become.

  This embodiment is advantageous in terms of secrecy even with respect to a comparative example as described below. That is, as shown in FIG. 4, a query including “Watanabe Takashi”, “Yoshida Daiki” and “Hiroyoshiko” is output to the search server 5 without being mixed even if dummy character strings are used. In this case, when the search server 5 extracts the character string whose edit distance is equal to or smaller than the threshold with respect to the first DB 51 and the second DB 52, only “Watabe Takashi” is extracted. In such a case, the original search target character string “Watanabe Takashi” is concealed, but since the query result indicates that “Watabe Takashi” is a blacklist person, the “Watanabe Takashi” included in the query From the relationship with “Takashi”, the search server 5 side leaks that “Watabe Takashi” included in the query is registered in the black list as “Watabe Takashi”.

  This is because of the following problems. That is, assuming that n dummy character strings are used, the query includes n + 1 character strings, so that when viewed from the search server 5 side, the number of candidates is n + 1, which is concealed. . On the other hand, for n + 1 character strings including dummy character strings, the number of character strings hit in the first DB 51 and the second DB 52 (for example, black list) is expected to be (n + 1) / B. Note that B is a constant representing a ratio that one of B is included in the black list.

  If B = 100, that is, if 1% of the population is a blacklist person, if n = 99 is not set, the dummy character string will not be hit even if the query includes the dummy character string. Absent. As B is smaller, the dummy character string will not be hit unless the value of n is increased. Therefore, if the dummy character string is attempted to be hit, the data amount of the query becomes enormous. This also reduces system processing efficiency. Considering that the number obtained by dividing the number of candidates viewed from the search server 5 by B as it is is the number of hits in the black list, it is preferable to efficiently increase the number of candidates viewed from the search server 5 with respect to n. . That is, with respect to the number n of dummy character strings, the number of candidates viewed from the search server 5 is made to appear to be the number of orders larger than a linear proportion with respect to n.

  On the other hand, if the mixed method of the search target character string and the dummy character string as shown in FIG. 3 is adopted, the number of candidates viewed from the search server 5 can be made larger than the linear proportion with respect to n.

That is, as shown in FIG. 5, when the search target character string “Tanaka Kouki” and the dummy character string “Koji Makiichi” are mixed and used as a query “Takonaka Jima Kikoichi”, when viewed from the search server 5, “ In addition to the four types of “Koji Makiichi”, “Tanaka Koki”, “Koji Maki Kuki”, and “Tana Kakiichi”, there are km ^v types of candidates such as “Nakajima Makiichi”. That is, when the total m = n + 1 types of character strings including the search target character string and n types of dummy character strings are mixed, the number of candidates is only m in the comparative example as shown in FIG. In this case, the number of candidates is m ² + km ^v (k is a constant, v is a constant of 8 or more).

  Thus, in the present embodiment, the number of candidates increases dramatically in proportion to a function of n to the 8th power or more, so that the number of candidates can be seen as an order number larger than a linear proportion to n. it can.

The term m ² is the number of candidates when m types of surnames and m types of first names are combined without mixing in the last name and first name units. The term km ^v is the number of candidates when m types of surnames are mixed in character string units and m types of names are mixed in character string units. When mixed m types surnames with each other in a string units, candidate number candidates in proportion to m ^u occurs for u ≧ 4. When m types of names are mixed in units of character strings, the number of candidates in proportion to m ^w is generated for w ≧ 4. Therefore, in the combination of surname and surname, the number of candidates is proportional to m ^{u + w} and u + w ≧ 8, which are the products of these.

  Next, the reason why the number of candidates when m types of surnames or first names are mixed in units of character strings is proportional to m to the fourth power or higher will be described with reference to FIG.

  FIG. 6 shows the number of candidates in an example in which two types of three-character names (first name or last name) are mixed in units of characters. When two types of three-character names are mixed, the total is six characters. Assuming that these 6 characters match other names, the name can be expressed by 2 to 4 characters. As a result, 2 out of 6 characters match other names and 3 out of 6 characters There are three types of patterns: a pattern that matches the name and a pattern that matches four of the six characters.

Of these, the pattern in which 2 out of 6 characters match other names is a pattern of random 2 characters compared to ₆ C ₂ which is the total number of combinations of random character strings obtained by selecting 2 characters out of ₆ characters. The character string is α ₆ C ₂ multiplied by a probability constant α that matches another name. However, _a C _b is a symbol representing the total number of combinations when b is selected from _a , and _a C _b = a × (a−1) ×... × (a−b + 1) / (1 × 2 ×... Xb), for example, ₆ C ₂ = 6 × 5 / (1 × 2) = 15, ₆ C ₃ = 6 × 5 × 4 / (1 × 2 × 3) = 20 .

The number of patterns in which a random three-character string matches other names is similarly expressed as β ₆ C ₃ . Where β is a constant representing the probability that a random three-character string matches another name. Furthermore, the number of patterns in which a random four-character string matches another name is expressed as γ ₆ C ₄ . However, γ is a constant representing the probability that a random four-character string matches another name. From the above, the number of candidates is expressed as follows.
α ₆ C ₂ + β ₆ C ₃ + γ ₆ C ₄ (1)

Equation (1) is the number of candidates when two types of three-character names are mixed and a total of six characters are used, but this is generalized when m types of two to four-character names are mixed. In this case, the total number of characters after mixing is expressed as mH. However, H is the average number of characters in the name and is a constant between 2 and 4. Therefore, by replacing “6” in equation (1) with “mH”, the number of candidates when generalized can be obtained.
α _mH C ₂ + β _mH C ₃ + γ _mH C ₄ (2)

_From the definition of _a C _b , _mH C ₂ is a quadratic expression relating to m, _mH C ₃ is a cubic expression relating to m, and _mH C ₄ is a quaternary expression relating to m. It becomes. That is, the number of candidates is proportional to the fourth power of m.

Note that when character strings are mixed, the order relationship (that is, the appearance order) between the n + 1 character strings before mixing is not changed. For example, when the dummy name “Hirota” is mixed with the correct customer name “Watanabe”, the following two points are observed.
・ After “wa”, “ta”, after “ta”, “na”, after “na”, “be”
・ "Ro" after "Hi", "Ta" after "Ro"

That is, in order "cotton Hiro pan data" or "cotton arsenide Na B base data" is according to the above rules, but the correct mixing, "cotton Hiro Vena data", "Cotton human na data base b", the former "base "" Before "na", and the latter "right" before "ro", it is not a correct mixture that satisfies the above requirements.

  By satisfying this requirement, the edit distance calculated in the search server 5 has a property as shown in FIG.

  That is, the search target character strings “Tanaka Kukiki” and “Koji Makiichi”, the character strings “Tanaka Kou” and “Koji Makiichi” included in the black list, and the character string “Takana Kagi Kikoui” as a result of mixing the search target character strings. The edit distance from “Kichi” is calculated. Then, if the editing distance between “Tanakakouuki” and “Tanakakou” is “1” and the editing distance between “Koji Makiichi” and “Kojimaki Ichirou” is “2”, “Takana Koji Makiko Ikiichi” and “Tanakakou” The edit distance is increased by 6 characters and the edit distance is +6, so that the edit distance becomes “7”. Similarly, the edit distance between “Takonakajimaki Kouichiki” and “Kojimaki Chihiro” is increased by 6 characters, so that the edit distance is also +6 and “8” is obtained. That is, since the relative similarity (= edit distance) is basically maintained even after character string mixing, the threshold used for name identification processing is lowered, that is, the edit distance is raised to increase the edit distance. An appropriate character string can be extracted without affecting the calculation of the distance itself.

  Note that the edit distance may be shorter for another character string. For example, if the character string “Nakajima Kouichi” is on the black list, the editing distance here is “4”, which is shorter than “Tanaka Kou” and “Koji Maki Chihiro”. Since this cannot be filtered by the search server 5, filtering is performed on the client device 3 side.

  Next, specific processing contents of the system shown in FIG. 1 will be described with reference to FIGS.

  First, the input unit 31 of the client device 3 receives an input of a search target character string from a searcher (step S <b> 1) and stores it in the first data storage unit 32. In the present embodiment, it is assumed that the surname and first name for one person are specified. That is, it is assumed here that the query surname and query name are input. And the 1st extraction part 34 and the mixing part 36 implement a concealment process (step S3). This concealment process will be described with reference to FIGS.

  The first extraction unit 34 randomly extracts k dummy surnames and k dummy names from the second data storage unit 33 and stores them in the third data storage unit 35 (step S21). For example, k dummy surnames are randomly extracted from the dummy surname list registered in the second data storage unit 33. A plurality of surnames are registered in the dummy surname list. Similarly, k dummy names are randomly extracted from the dummy name list registered in the second data storage unit 33. A plurality of names are registered in the dummy name list.

  And the mixing part 36 performs the process which inserts the character of a dummy surname into the query surname S at random, maintaining the order of appearance, and stores a process result in the 4th data storage part 37 (step S23). Further, the mixing unit 36 performs a process of randomly inserting the dummy name characters into the query name G while maintaining the appearance order, and stores the processing result in the fourth data storage unit 37 (step S25). Then, the process returns to the caller process.

  In step S23, in order to maintain the appearance order of the characters included in the query surname, the characters included in the dummy surname are also inserted according to the appearance order. That is, for k dummy surnames, the processing for one dummy surname is not completed until the processing for another dummy surname is completed. In step S25, in order to maintain the appearance order of characters included in the query name, the characters included in the dummy name are also inserted according to the appearance order. The k dummy names are processed one by one in an arbitrary order (eg, extraction order).

  Step S23 is processed by a processing flow as shown in FIGS. 10 and 11, for example.

  First, the mixing unit 36 substitutes the number of characters of the query surname S for the variable s_len (step S31). Further, the mixing unit 36 initializes the counter i to 0 (step S33). In addition, the mixing unit 36 substitutes the number of characters of the i-th dummy surname Sai into the variable sd_len, inputs a NULL character to the array T of the mixed character string, and initializes the counters jx and jy to 0 (step) S35). Furthermore, the mixing unit 36 initializes j to 0 (step S37).

  Thereafter, the mixing unit 36 generates a random number b of 0 or more and 1 or less (step S39), and determines whether b is greater than or equal to s_len / (s_len + sd_len) (step S41). That is, it is determined whether or not the ratio of the number of S characters to the sum of the number of S characters and the number of dummy surnames Sai is equal to or greater than b.

  If this condition is satisfied, the mixing unit 36 sets the jx-th character of S to T [j], increments j by 1 and increments jx by 1 (step S43). Then, the processing shifts to the processing in FIG. On the other hand, when the condition of step S41 is not satisfied, the mixing unit 36 sets the jy-th character of the dummy surname Sai to T [j], increments j by 1, and increments jy by 1 (step S45). ). Then, the processing shifts to the processing in FIG.

  Shifting to the description of the processing in FIG. 11, the mixing unit 36 determines whether jx is s_len (step S47). That is, it is determined whether or not processing has been performed up to the last character of S. When jx becomes s_len, the mixing unit 36 determines that T [j + 1] = Sai [j + 1],. . , T [s_len + sd_len-1] = Sai [sd_len-1] (step S49). That is, unprocessed characters in the dummy surname Sai are set in the array T in that order. Then, the process proceeds to step S57.

  On the other hand, when jx = s_len is not satisfied, the mixing unit 36 determines whether jy = sd_len is satisfied (step S51). That is, it is determined whether the last character of the dummy surname Sai has been processed. When jy = sd_len, the mixing unit 36 determines that T [j + 1] = S [jx + 1],. . , T [s_len + sd_len-1] = S [s_len-1] (step S53). That is, unprocessed characters in S are set in the array T in that order. Then, the process proceeds to step S57.

  On the other hand, when jy = sd_len is not satisfied, the mixing unit 36 determines whether j is larger than s_len + sd_len−1 (step S55). If this condition is not satisfied, the process returns to step S39 in FIG. On the other hand, when this condition is satisfied, the process proceeds to step S57.

  In step S57, the mixing unit 36 substitutes T for S and substitutes s_len + sd_len for s_len (step S57). That is, the mixing result with the dummy name Sai is set as S, and the mixing process with the next dummy name Sa (i + 1) is performed. The mixing unit 36 increments i by 1 (step S59). Thereafter, the mixing unit 36 determines whether i is larger than k−1 (step S61). If i is not larger than k−1, the process returns to step S35 in FIG. 10 in order to perform processing for the remaining dummy surname Sai through the terminal C. On the other hand, when i becomes larger than k−1, that is, when the mixing process for all dummy surnames Sai is completed, the process returns to the caller process.

  If it does in this way, it will become possible to mix, maintaining the order of appearance of each character included in both query surname S and dummy surname Sai.

  Next, step S25 is processed by a processing flow as shown in FIGS. 12 and 13, for example.

  First, the mixing unit 36 substitutes the number of characters of the query name G for the variable g_len (step S71). Further, the mixing unit 36 initializes the counter i to 0 (step S73). Further, the mixing unit 36 substitutes the number of characters of the i-th dummy name Gai for the variable gd_len, inputs NULL characters to the mixed character string array T, and initializes the counters jx and jy to 0 (step S40). S75). Further, the mixing unit 36 initializes j to 0 (step S77).

  Thereafter, the mixing unit 36 generates a random number b of 0 or more and 1 or less (step S79), and determines whether b is greater than or equal to g_len / (g_len + gd_len) (step S81). That is, it is determined whether the ratio of the number of characters of the query name G to the sum of the number of characters of the query name G and the number of characters of the dummy name Gai is equal to or greater than b.

  When this condition is satisfied, the mixing unit 36 sets the jx-th character of the query name G to T [j], increments j by 1 and increments jx by 1 (step S83). Then, the processing shifts to the processing in FIG. On the other hand, when the condition of step S81 is not satisfied, the mixing unit 36 sets the jy-th character of the dummy name Gai to T [j], increments j by 1, and also increments jy by 1 (step S85). ). Then, the processing shifts to the processing in FIG.

  Shifting to the description of the processing in FIG. 13, the mixing unit 36 determines whether jx becomes g_len (step S <b> 87). That is, it is determined whether the last letter of G has been processed. When jx becomes g_len, the mixing unit 36 determines that T [j + 1] = Gai [ji + 1],. . , T [g_len + gd_len−1] = Gai [gd_len−1] (step S89). That is, unprocessed characters in the dummy name Gai are set in the array T in that order. Then, the process proceeds to step S97.

  On the other hand, when jx = g_len is not satisfied, the mixing unit 36 determines whether jy = gd_len is satisfied (step S91). That is, it is determined whether the last character of the dummy name Gai has been processed. When jy = gd_len, the mixing unit 36 determines that T [j + 1] = G [jx + 1],. . , T [g_len + gd_len-1] = G [g_len-1] (step S93). That is, unprocessed characters in G are set in the array T in that order. Then, the process proceeds to step S97.

  On the other hand, when jy = gd_len is not satisfied, the mixing unit 36 determines whether j is larger than g_len + gd_len−1 (step S95). If this condition is not satisfied, the process returns to step S79 in FIG. On the other hand, when this condition is satisfied, the process proceeds to step S97.

  In step S97, the mixing unit 36 substitutes T for G and substitutes g_len + gd_len for g_len (step S97). In other words, the mixing result with the dummy name Gai is set as G, and the mixing process with the next dummy name Ga (i + 1) is performed. The mixing unit 36 increments i by 1 (step S99). Thereafter, the mixing unit 36 determines whether i is larger than k−1 (step S101). If i is not larger than k−1, the process returns to step S75 in FIG. 12 in order to process the remaining dummy name Gai via the terminal F. On the other hand, when i becomes larger than k−1, that is, when the mixing process for all dummy names Gai is completed, the process returns to the caller process.

  If it does in this way, it will become possible to mix, maintaining the order of appearance of each character included in both query name G and dummy name Gai.

  Returning to the description of the processing in FIG. 8, the query transmission unit 38 concatenates the query last name and the query name after the mixing processing stored in the fourth data storage unit 37 and includes the query last name and the query name. The query is transmitted to the search server 5 (step S5).

  On the other hand, the search server 5 receives a query from the client device 3 (step S7), and performs a search process (step S9). The search process is, for example, a process as shown in FIG.

  The search server 5 reads one unprocessed character string to be searched in the first DB 51, the second DB 52, and the like (step S111). Then, the search server 5 calculates the edit distance between the query and the searched character string (step S113).

  A method called Levenshtein distance is generally used to calculate the edit distance. The processing flow of this method will be described with reference to FIGS.

  The search server 5 uses the character strings str_1 [1,. . , Xmax] and str_2 [1,. . . , Ymax], the query character string and the searched character string are set (step S121). In addition, as an initial setting, the search server 5 sets x times d [x, 0] = D and y times d [0, y] = I for 0 ≦ x ≦ Xmax and 0 ≦ y ≦ Ymax. (Step S123). D is the weight of the deletion cost, and I is the weight of the insertion cost.

  For example, a case where the edit distance between “Watanabe” and “Watabe” is calculated will be described as an example. The arrangement d [x, y] is an arrangement as shown in FIG. In other words, how to correct both character strings in a state where a blank is inserted at the beginning of each character string, that is, “number of corrected characters × weight of correction operation” is registered for each character. For example, the leading blank of “Watabe” and the leading blank of “Watanabe” match, so d [0,0] = 0, and the leading blank of “Watabe” and “wa” of “Watanabe” If one character is deleted from the latter, they match, so d [1, 0] = 1D. The leading blank of “Watabe” and “Watabe” of “Watanabe” match if the latter two characters are deleted, so d (2, 0) = 2D. The same applies hereinafter. On the other hand, “W” of “Watabe” and the leading blank of “Watanabe” match when “wa” is inserted into the latter, so d [0, 1] = 1I. Since “Wata” of “Watabe” and the leading blank of “Watanabe” match when “Wata” is inserted into the latter, d [0, 2] = 2I. The same applies hereinafter.

  The search server 5 sets y = 1 (step S125), and further sets x = 1 (step S127).

  Thereafter, the search server 5 determines whether str_1 [x] = str_2 [y] is satisfied (step S129). If str_1 [x] = str_2 [y], the search server 5 sets d [x, y] = min (d [x, y-1] + I, d [x-1, y-1], d [ x-1, y] + D) (step S131). Then, control goes to a step S135. On the other hand, if str_1 [x] = str_2 [y] is not satisfied, the search server 5 sets d [x, y] = min (d [x, y−1] + I, d [x−1, y−1] + S. , D [x-1, y] + D) (step S133). Then, control goes to a step S135.

  In this algorithm, as shown in FIG. 17, when calculating the cost of the lower right cell M, the cost for matching by inserting one character from the character string of the cell above M (above M) The cost of matching the cell cost + 1 character insertion cost I) with the replacement of the last character in the upper left square character string by replacing one character (the cost of the upper left diagonal cell + 1 character replacement) The minimum cost is adopted between the cost S) and the cost (M cost of the left cell of M + 1 character deletion cost D) in the case of matching by deleting the last character of the left cell of M by one character. However, if the characters related to the process match in both character strings, the replacement cost S to be added to the cost of the upper left square of M is 0, so that there is a difference between steps S131 and S133.

  Then, the search server 5 increments x by 1 (step S135), and determines whether x exceeds Xmax (step S137). If x is less than or equal to Xmax, the process returns to step S129. On the other hand, if x exceeds Xmax, the processing shifts to the processing in FIG.

  Shifting to the description of the processing in FIG. 18, the search server 5 increments y by 1 (step S139) and determines whether y exceeds Ymax (step S141). If y is equal to or less than Ymax, the process returns to step S127 in FIG. On the other hand, if y exceeds Ymax, the search server 5 outputs d [Xmax, Ymax] as the edit distance (step S143). Then, the process returns to the caller process.

  In this way, for example, as shown in FIG. 19, processing is performed in the order of the arrows, and as shown in FIG. 17, the cost of each square is calculated from the cost of the three squares, and finally d [4 , 3] is the final edit distance. Note that hatched squares are squares whose edit distance is determined in step S131.

  Returning to the description of the processing in FIG. 14, the search server 5 determines whether or not the calculated edit distance is equal to or less than a threshold (step S115). In this embodiment, Q−L + E is adopted as a threshold value from the number Q of characters included in the character string of the query, the number L of characters included in the character string to be searched, and the original threshold value E. Q-L indicates a threshold offset due to the mixing process. However, for example, the number of characters included in the original search target character string may be L, and may be transmitted from the client device 3 to the search server 5 by a query, and used for threshold determination.

  If the edit distance exceeds the threshold, the process proceeds to step S119. On the other hand, if the edit distance is equal to or smaller than the threshold, the search server 5 adds the searched character string to the search result (step S117). Then, the search server 5 determines whether or not there is an unprocessed character string to be searched in the first DB 51 and the second DB 52 (step S119). If there is an unprocessed character string to be searched, the process returns to step S111. On the other hand, if there is no unprocessed character string to be searched, the process returns to the caller process.

  If such a process is performed, it becomes possible to extract a character string having an edit distance equal to or less than the threshold based on a threshold that takes into account the edit distance that has increased due to the influence of the mixing process.

  Returning to the description of the processing in FIG. 8, the search server 5 returns the search result to the client device 3 that is the transmission source of the query (step S <b> 11). Upon receiving the search result, the search result receiving unit 39 of the client device 3 stores it in the fifth data storage unit 40 (step S13). The second extraction unit 41 extracts the search result corresponding to the query from the search target character string stored in the first data storage unit 32, and the search result stored in the fifth data storage unit 40. 6 is stored in the data storage unit 42 (step S15). Then, the output unit 43 outputs the data stored in the sixth data storage unit 42 to an output device or other devices.

  The process in step S15 may be any process. For example, the determination may be made again based on the edit distance between the search target character string and the character string included in the search result.

  In this way, it is possible to conceal the query and also conceal the search result.

[Embodiment 2]
In the first embodiment, a dummy character string is randomly selected. Although this can be sufficiently concealed, in this embodiment, by selecting dummy character strings in consideration of co-occurrence between characters, the number of candidates seen from the search server 5 side is increased, and concealment is performed. Increase the effect of crystallization.

  Before describing the details of this embodiment in detail, the concept of improving the privacy protection effect using co-occurrence between characters will be described. “Co-occurrence” represents the strength of correlation of occurrence frequency between characters. For example, if surnames such as “Tanaka” and “Tajima” appear frequently, “Naka” is a highly correlated character for “Ta” and “Jima” is also correlated as a suffix for “Ta”. Is a high character. Also, when surnames such as “Sato”, “Kato”, “Saito” and “Ito” appear frequently, “S”, “K”, “Sai” and “I” are prefixed characters with high correlation. . The strength of this correlation is called “co-occurrence rate”. When the correlation is high, it is called “high co-occurrence rate”, and when the correlation is low, it is called “low co-occurrence rate”. By selecting the dummy character string in consideration of the co-occurrence rate, the number of candidates viewed from the search server 5 side is further increased, so that concealment can be further improved.

  As mentioned above, the co-occurrence rate of “sa”, “f” and “b” is higher than “to”. That is, it is desirable for concealment that the result of concealing “Sato” is also visible to “Ito” and “Kato”. That is, when concealing “Sato”, a dummy character string including as many “I” and “K” characters as possible with a high co-occurrence rate is desirable. However, “sa” has a high co-occurrence rate, but is excluded.

  As a case where the co-occurrence rate is not considered, “Machida” that does not include these characters may be selected as a dummy character string. The concealment result is “Masachi Toda”, but when this concealment result is viewed from the search server 5, two types of “Machida” or “Sato” are candidate names.

  When the co-occurrence rate is taken into consideration, “Kaya” including many “I” and “K” is selected as a dummy character string. The concealment result is “Kasaiya Tou”, but when viewed from the search server 5 side, six types of “Kato”, “Sato”, “Ito”, “Saito”, “Kaiya” and “Kasai” are candidate names. In this way, if a lot of character strings are included in the search result, it becomes possible to prevent leakage of the search target character string from the search result.

  When the co-occurrence rate is used as in the present embodiment, a co-occurrence table for surnames and a co-occurrence table for first names as shown in FIGS. 20 and 21 are additionally stored in the second data storage unit 33. Keep it. And the 1st extraction part 34 extracts the character or character string with a high co-occurrence rate based on the search object character string stored in the 1st data storage part 32, The said extracted character or character string is used. The surnames and first names that are included are further extracted.

  FIG. 20 shows an example of a co-occurrence table for surnames. In the example of FIG. 20, a character or character string “sa” or the like whose co-occurrence rate is equal to or greater than a threshold when a character or character string such as “to” appears in the last name is registered. Similarly, FIG. 21 shows an example of a co-occurrence table for names. In the example of FIG. 21, when a character or character string such as “low” appears in the name, a character or character string “ichi” or the like whose co-occurrence rate is equal to or greater than a threshold is registered.

  Further, the concealment process in FIG. 9 is changed to a process as shown in FIG.

  For the surname S and surname G of the search target character string stored in the first data storage unit 32, the first extraction unit 34 uses a character or a character string (co-occurrence character Scp (0 ≦ p ≦ P−1) and Gcq (0 ≦ q ≦ Q−1) are extracted (step S201). However, when a co-occurrence character appears in the surname S, the co-occurrence character is not adopted. The same applies to the name G. For example, when the surname S of the search target character string is “Ito”, the prefix “I” of “To” is not extracted as a co-occurrence character.

  Then, the first extraction unit 34 performs a dummy surname extraction process (step S203). This dummy surname extraction process will be described with reference to FIG.

  First, the first extraction unit 34 initializes i to 1 (step S211), and randomly selects one dummy character string (a surname if a dummy surname extraction process) (step S213). Then, the first extraction unit 34 counts the number of co-occurrence characters (Scp or Scq) included in the selected dummy character string (step S215). It is assumed that “I” and “K” are specified as co-occurrence characters having a co-occurrence rate equal to or greater than a threshold for “Sato”. In this case, the number of co-occurrence characters is “2” for the dummy character string “KAYA”. Further, the number of co-occurrence characters is “1” for the dummy character string “Hello”.

  Then, the first extraction unit 34 determines whether the counted number of characters is greater than or equal to the threshold (step S217). You may judge by the ratio of the number of count characters with respect to the number of characters contained in a dummy character string.

  If the number of characters is less than the threshold value, the dummy character string is not adopted and the process proceeds to step S223. On the other hand, if the number of characters is equal to or greater than the threshold, the first extraction unit 34 sets the dummy character string to Sai or Gai (step S219). If it is a dummy surname extraction process, it is set to Sai, and if it is a dummy name extraction process, it is set to Gai. Then, the first extraction unit 34 increments i by 1 (step S221). Further, the first extraction unit 34 determines whether i exceeds N (step S223). If i is equal to or less than N, the process returns to step S213. On the other hand, if i exceeds N, the process returns to the caller process.

  As described above, in the processing flow of FIG. 23, it is ensured that any co-occurrence character includes more than the threshold number of characters in each dummy character string, but this processing is not limited to this. Absent. For example, if n dummy character strings are to be extracted, it may be sufficient to extract dummy character strings that include co-occurrence characters at a rate exceeding a predetermined threshold, such as 80% of n characters. Furthermore, since it is preferable that all types of co-occurrence characters are included in the dummy character string as much as possible, the dummy character string may be extracted so that the coverage rate of the co-occurrence characters is equal to or higher than a predetermined threshold.

  Returning to the description of the processing in FIG. 22, the first extraction unit 34 performs dummy name extraction processing (step S <b> 205). In this process, the process shown in FIG. 23 is performed for the dummy name.

  Then, the mixing unit 36 performs a process of randomly inserting characters of the dummy surname into the query surname S while maintaining the appearance order, and stores the processing result in the fourth data storage unit 37 (step S207). Further, the mixing unit 36 performs a process of randomly inserting the dummy name characters into the query name G while maintaining the appearance order, and stores the processing result in the fourth data storage unit 37 (step S209). Then, the process returns to the calling process. Steps S207 and S209 are processed in the processing flow of FIGS.

  In this way, the search result that is the processing result of the search server 5 is more likely to include a search result derived from the dummy character string, and as a result, concealment of the search result is improved.

  Although the embodiments of the present technology have been described above, the present technology is not limited to these.

For example, the functional block diagram of FIG. 2 is an example and may not necessarily match the actual program module configuration. As for the processing flow, as long as the processing result does not change, the steps can be executed in parallel or the execution order can be changed.

  Further, the functions of the client device 3 and the search server 5 may be implemented by a single computer or may be implemented by a plurality of computers.

  The client device 3 and the search server 5 described above are computer devices, and as shown in FIG. 24, a memory 2501, a CPU (Central Processing Unit) 2503, and a hard disk drive (HDD: Hard Disk Drive) 2505. A display control unit 2507 connected to the display device 2509, a drive device 2513 for the removable disk 2511, an input device 2515, and a communication control unit 2517 for connecting to a network are connected by a bus 2519. An operating system (OS) and an application program for executing the processing in this embodiment are stored in the HDD 2505, and are read from the HDD 2505 to the memory 2501 when executed by the CPU 2503. The CPU 2503 controls the display control unit 2507, the communication control unit 2517, and the drive device 2513 according to the processing content of the application program, and performs a predetermined operation. Further, data in the middle of processing is mainly stored in the memory 2501, but may be stored in the HDD 2505. In an embodiment of the present technology, an application program for performing the above-described processing is stored in a computer-readable removable disk 2511 and distributed, and installed from the drive device 2513 to the HDD 2505. In some cases, the HDD 2505 may be installed via a network such as the Internet and the communication control unit 2517. Such a computer apparatus realizes various functions as described above by organically cooperating hardware such as the CPU 2503 and the memory 2501 described above and programs such as the OS and application programs. .

  The above-described embodiment can be summarized as follows.

  The information processing method according to the present embodiment includes (A) an acquisition process for acquiring one or a plurality of second character strings to be mixed with a first character string designated as a search target, and (B) For the first character string while maintaining the appearance order or order relationship of the plurality of characters included in the first character string and the appearance order or order relationship of the plurality of characters included in the one or more second character strings A process of generating a third character string by mixing one or a plurality of second character strings and storing the third character string in the data storage unit; and (C) a third character string stored in the data storage unit. And a process of outputting a query including the query to a search computer that performs a character string search using the edit distance.

  In this way, the query itself is concealed, and since the true search result cannot be specified for the search result detected by the search computer, the query is concealed.

  Further, in the information processing method according to the present embodiment, (D) when a search result including a plurality of fourth character strings is received from the search computer, the first character string is calculated from the plurality of fourth character strings. A process of extracting a character string corresponding to may be further included. Even if a plurality of fourth character strings are simply presented to the searcher, the first character string can be extracted because it is known, but it may be automatically extracted in this way.

  In addition, the acquisition process described above is performed by (a1) from the second data storage unit in which characters or character strings having a co-occurrence rate equal to or greater than a threshold value are associated with each character or character string, A process of extracting a character or character string associated with the character or character string included in the character string and not included in the first character string, and (a2) the extracted character or character A second acquisition process of acquiring one or a plurality of second character strings including at least one of the columns. By doing in this way, since it becomes easy to enter into a search result the character string with a thin relationship with a 1st character string in a search result, concealment of a search result is also improved.

  In addition, the acquisition process described above is performed from the second data storage unit (a11) in which a character or character string having a co-occurrence rate equal to or greater than a threshold value is stored in association with each character or character string. A process of extracting a character or character string associated with the character or character string included in the character string and not included in the first character string, and (a12) the extracted character or character And a selection process for selecting the second character string using the column. In this case, the selection process described above is (a12-1) Among the extracted characters or character strings, the number or ratio of characters or character strings included in one second character string is a first predetermined value. As described above, the process of selecting the second character string, (a12-2) When the total number of second character strings to be selected is set in advance, at least one of the extracted characters or character strings is A process of obtaining a second character string corresponding to the total number of selections, or (a12-3) an extracted character or character so that the ratio of the second character string to be included is greater than or equal to a second predetermined value When there are a plurality of types of strings and a plurality of second character strings, the number or ratio of the types of characters or character strings included in the plurality of second character strings among the extracted characters or character strings is Including a process of selecting a plurality of second character strings so as to be equal to or greater than a predetermined value of 3. It may be so. There are various selection methods for the second character string.

  The threshold for the edit distance may be determined based on the number of characters in the third character string, or the threshold for the edit distance may be determined based on the number of characters in the third character string and the number of characters in the first character string. good. This is based on the nature of edit distance.

  It is possible to create a program for causing a computer to carry out the processing described above, such as a flexible disk, an optical disk such as a CD-ROM, a magneto-optical disk, and a semiconductor memory (for example, ROM). Or a computer-readable storage medium such as a hard disk or a storage device.

  The following supplementary notes are further disclosed with respect to the embodiments including the above examples.

(Appendix 1)
An information processing method executed by a computer,
An acquisition process for acquiring a second character string mixed with the first character string designated as a search target;
While maintaining the order relationship between the plurality of characters included in the first character string and the order relationship between the plurality of characters included in the second character string, the second character string is compared with the second character string. Generating a third character string by mixing the character strings and storing the third character string in the data storage unit;
A process of outputting a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
An information processing method including:

(Appendix 2)
A process in which the computer receives a search result including a plurality of fourth character strings from the search computer and extracts a character string corresponding to the first character string from the plurality of fourth character strings; The information processing method according to supplementary note 1, further including:

(Appendix 3)
The acquisition process includes
Corresponding characters or character strings included in the first character string from the second data storage unit in which characters or character strings having a co-occurrence rate equal to or greater than a threshold value are associated and stored for each character or character string A second character string including at least one of the character or the character string extracted by the process of extracting the character or the character string that is not included in the first character string. The information processing method according to claim 1 or 2, wherein the information processing method is:

(Appendix 4)
The acquisition process
Corresponding characters or character strings included in the first character string from the second data storage unit in which characters or character strings having a co-occurrence rate equal to or greater than a threshold value are associated and stored for each character or character string A process of extracting characters or character strings that are not included in the first character string,
A selection process for selecting the second character string using the extracted character or character string;
Including
The selection process is
The second character string is selected so that the number or ratio of characters or character strings included in one second character string is equal to or greater than a first predetermined value among the extracted characters or character strings. processing,
When the total selection number of the second character string is set in advance, a ratio of the extracted second character string including at least one of the character or the character string to the total selection number is a second predetermined value. As described above, the process of obtaining the second character string corresponding to the selected total number, or the extracted character or character string is a plurality of types, and the plurality of second character strings are extracted. The plurality of second character strings are set such that the number or ratio of the types of characters or character strings included in the plurality of second character strings among the characters or character strings is equal to or greater than a third predetermined value. The information processing method according to claim 1, comprising a process of selecting.

(Appendix 5)
The threshold value for the editing distance is determined based on the number of characters of the third character string, or based on the number of characters of the third character string and the number of characters of the first character string. The information processing method described.

(Appendix 6)
An acquisition process for acquiring a second character string mixed with the first character string designated as a search target;
While maintaining the order relationship between the plurality of characters included in the first character string and the order relationship between the plurality of characters included in the second character string, the second character string is compared with the second character string. Generating a third character string by mixing the character strings and storing the third character string in the data storage unit;
A process of outputting a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
A program that causes a computer to execute.

(Appendix 7)
A second character string to be mixed with the first character string designated as a search target is acquired, and an order relationship between a plurality of characters included in the first character string and a plurality of characters included in the second character string A mixing unit for generating a third character string by mixing the second character string with the first character string and storing the third character string in a data storage unit,
An output unit that outputs a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
An information processing apparatus.

1 Network 3 Client Device 5 Search Server 51 1st DB
52 2nd DB
31 Input unit 32 First data storage unit 33 Second data storage unit 34 First extraction unit 35 Third data storage unit 36 Mixing unit 37 Fourth data storage unit 38 Query transmission unit 39 Search result reception unit 40 Fifth data storage unit 41 Second extraction unit 42 Sixth data storage unit 43 Output unit

Claims (7)

An information processing method executed by a computer,
An acquisition process for acquiring a second character string mixed with the first character string designated as a search target;
While maintaining the order relationship between the plurality of characters included in the first character string and the order relationship between the plurality of characters included in the second character string, the second character string is compared with the second character string. Generating a third character string by mixing the character strings and storing the third character string in the data storage unit;
A process of outputting a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
An information processing method including: A process in which the computer receives a search result including a plurality of fourth character strings from the search computer and extracts a character string corresponding to the first character string from the plurality of fourth character strings; The information processing method according to claim 1, further comprising: The acquisition process includes
Corresponding characters or character strings included in the first character string from the second data storage unit in which characters or character strings having a co-occurrence rate equal to or greater than a threshold value are associated and stored for each character or character string A second character string including at least one of the character or the character string extracted by the process of extracting the character or the character string that is not included in the first character string. The information processing method according to claim 1 or 2, wherein the information processing method is: The acquisition process
Corresponding characters or character strings included in the first character string from the second data storage unit in which characters or character strings having a co-occurrence rate equal to or greater than a threshold value are associated and stored for each character or character string A process of extracting characters or character strings that are not included in the first character string,
A selection process for selecting the second character string using the extracted character or character string;
Including
The selection process is
The second character string is selected so that the number or ratio of characters or character strings included in one second character string is equal to or greater than a first predetermined value among the extracted characters or character strings. processing,
When the total selection number of the second character string is set in advance, a ratio of the extracted second character string including at least one of the character or the character string to the total selection number is a second predetermined value. As described above, the process of obtaining the second character string corresponding to the selected total number, or the extracted character or character string is a plurality of types, and the plurality of second character strings are extracted. The plurality of second character strings are set such that the number or ratio of the types of characters or character strings included in the plurality of second character strings among the characters or character strings is equal to or greater than a third predetermined value. The information processing method according to claim 1, comprising a process of selecting. The threshold for the edit distance is determined based on the number of characters of the third character string, or based on the number of characters of the third character string and the number of characters of the first character string. Information processing method. An acquisition process for acquiring a second character string mixed with the first character string designated as a search target;
While maintaining the order relationship between the plurality of characters included in the first character string and the order relationship between the plurality of characters included in the second character string, the second character string is compared with the second character string. Generating a third character string by mixing the character strings and storing the third character string in the data storage unit;
A process of outputting a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
A program that causes a computer to execute. A second character string to be mixed with the first character string designated as a search target is acquired, and an order relationship between a plurality of characters included in the first character string and a plurality of characters included in the second character string A mixing unit for generating a third character string by mixing the second character string with the first character string and storing the third character string in a data storage unit,
An output unit that outputs a query including the third character string stored in the data storage unit to a search computer that performs a character string search using an edit distance;
An information processing apparatus.

Images