JP6333082B2 - Processing device, arithmetic device, processing method, arithmetic method, processing program, and arithmetic program - Google Patents

Description

  The present invention relates to a processing device, a processing method, and a processing program that process trajectory information, and a computing device, a computing method, and a computing program that compute the next node based on the trajectory information.

  In the prior art, there is one that calculates and obtains the next location based on a prefix tree classifier (classifier) (see, for example, Non-Patent Document 1).

Lemile, Daniel, and Anna Maclachlan. Slope One Predictors for Online Rating-Based Collaborative Filtering. SDM. Vol. 5.2005

  By the way, when calculating and determining the next node (for example, location), a server (hereinafter referred to as a cloud server) provided by a third party that does not protect privacy such as a public cloud is used. In such a case, it becomes difficult to protect the privacy of the query including the trajectory information. In other words, the privacy of the trajectory information cannot be protected in the process of calculating and obtaining the next node on the cloud server.

  The present invention provides a processing device, an arithmetic device, a processing method, an arithmetic method, a processing program, and an arithmetic program that can calculate and obtain the next node using a cloud server while protecting privacy. Objective.

  The processing device includes a plurality of nodes and edges, and a receiving unit that receives trajectory information created based on a user's behavior history, and a loop portion exists in the trajectory information received by the receiving unit Includes a division processing unit that divides a plurality of pieces of trajectory information to eliminate a loop, a weighting unit that weights each node constituting the trajectory information, and encrypts the weighted trajectory information. It is a structure provided with an encryption part and the transmission part which transmits the locus | trajectory information encrypted by the said encryption part.

  In the processing device, the division processing unit may be configured to resolve the loop by dividing the edge connected toward the looped node into a plurality of pieces of trajectory information.

  In the processing device, the weighting unit may be configured to perform weighting so that a value does not overlap each node constituting the trajectory information so that a high value is assigned to a node that is older in time.

  The computing device receives a first received trajectory information as the first trajectory information, and a second reception unit receives the encrypted trajectory information from the user terminal as the second trajectory information. Based on the second trajectory information, an integration unit that integrates a plurality of the first trajectory information received by the first reception unit, and the second trajectory information. It is a structure provided with the calculation part which calculates the node suitable as a next node following the last node which comprises, and the transmission part which transmits the information of the node calculated by the said calculation part to the said user terminal.

  In the arithmetic device, the calculation unit calculates a plurality of nodes suitable as the next node following the last node constituting the second trajectory information, and the transmission unit calculates the plurality of nodes calculated by the calculation unit. The node information may be transmitted to the user terminal.

  The processing method consists of a plurality of nodes and edges, and when there is a loop part in the trajectory information created based on the user's behavior history, the division that splits the trajectory information and eliminates the loop A processing step; a weighting step for weighting each node constituting the trajectory information; an encryption step for encrypting the weighted trajectory information; and the trajectory information encrypted by the encryption step. The transmission process of transmitting.

  The calculation method includes a first receiving step of receiving transmitted encrypted trajectory information as first trajectory information, and a second reception of receiving encrypted trajectory information from the user terminal as second trajectory information. A step of integrating a plurality of the first trajectory information received in the first receiving step as integrated information, and referring to the integrated information based on the second trajectory information; It is a structure provided with the calculation process which calculates the node suitable as the next node following the last node which comprises, and the transmission process which transmits the information of the node calculated by the said calculation process to the said user terminal.

  The processing program is composed of a plurality of nodes and edges in the computer, and if there is a loop portion in the trajectory information created based on the user's behavior history, the loop is divided into a plurality of trajectory information. The division processing step to be eliminated, the weighting step for weighting each node constituting the trajectory information, the encryption step for encrypting the weighted trajectory information, and the encryption step This is a program for executing the transmission step of transmitting the trajectory information.

  The arithmetic program receives the encrypted trajectory information transmitted to the computer as first trajectory information, and receives the encrypted trajectory information from the user terminal as second trajectory information. Based on the second reception step, the integration step of integrating the plurality of first trajectory information received in the first reception step as integration information, and referring to the integration information based on the second trajectory information, the second A calculation step for calculating a node suitable as the next node following the last node constituting the trajectory information, and a transmission step for transmitting the node information calculated by the calculation step to the user terminal. It is a program.

  According to the present invention, the next node can be calculated and obtained using a cloud server.

It is a block diagram which shows the structure of a processing system. It is a block diagram which shows the structure of a processing apparatus. It is a block diagram which shows the structure of an arithmetic unit. It is a figure which shows the 1st example of integrated information. It is a figure which shows the 2nd example of integrated information. It is a flowchart with which it uses for description about the flow of a process at the time of calculating the next place by a processing system.

This embodiment will be described below.
As shown in FIG. 1, a processing system 1 that calculates and calculates the next node using a server operated by a third party while protecting privacy, a processing device 10, an arithmetic device 20, The first terminal device 30 and the second terminal device 40 are configured. The 1st terminal device 30 and the 2nd terminal device 40 are terminal devices which have communication functions, such as a smart phone and a tablet, Comprising: Each is comprised from the several terminal device. The second terminal device 40 is not only a terminal device owned by the user, but also a terminal device, an information processing device owned by a third party service provider who makes an inquiry to the arithmetic device 20 on behalf of the user, It may be a server or the like.

The plurality of terminal devices constituting the first terminal device 30 and the plurality of terminal devices constituting the second terminal device 40 may partially or entirely overlap.
Hereinafter, the arithmetic device 20 will be described assuming a server (hereinafter referred to as a cloud server) provided by a third party that is not protected for privacy, such as a public cloud, but is not limited thereto.

As illustrated in FIG. 2, the processing device 10 includes a reception unit 11, a division processing unit 12, a weighting unit 13, an encryption unit 14, and a transmission unit 15.
The receiving unit 11 includes a plurality of nodes and edges, and receives from the first terminal device 30 trajectory information created based on the user's behavior history.

  When there is a loop portion in the trajectory information received by the receiving unit 11, the division processing unit 12 divides the trajectory information into a plurality of trajectory information and eliminates the loop. Note that the division processing performed by the division processing unit 12 may be performed by the first terminal device 30.

The weighting unit 13 weights each node constituting the trajectory information.
The encryption unit 14 encrypts the weighted trajectory information. Specifically, the encryption unit 14 encrypts the trajectory information using a homomorphic encryption method so that the arithmetic unit 20 can perform arithmetic processing with encryption.
The transmission unit 15 transmits the trajectory information encrypted by the encryption unit 14 to the arithmetic device 20.

For example, in the case where the trajectory information is configured with the location where the user visited as a node, when the user visits the same location, a loop portion is generated in the trajectory information. If weighting is performed on each node of the trajectory information in which the loop portion is generated, the same node is weighted repeatedly.
Therefore, in the processing apparatus 10, when a loop portion exists in the trajectory information by the division processing unit 12, the loop is eliminated by dividing the trajectory information into a plurality of trajectory information.

  In this way, the processing device 10 performs processing so that there is no loop portion in the trajectory information by the division processing, so that the weighting unit 13 can weight each node of the trajectory information without overlapping.

  Further, since the processing device 10 encrypts the trajectory information, the privacy of the user who provided the trajectory information can be protected even if the trajectory information is transmitted to the computing device 20 as a cloud server.

The division processing unit 12 may be configured to divide a plurality of pieces of trajectory information by dividing an edge connected toward a looped node to eliminate the loop.
For example, the case where the trajectory information is configured as “A → B → C → A → B → D → E → F” and loops at the node A will be described as an example.

The division processing unit 12 divides at the edge immediately before the node A that is the first node in the loop. The division processing unit 12 divides the trajectory information into “A → B → C” and “A → B → D → E → F”. Further, the division processing unit 12 modifies the latter trajectory information to “C → A → B → D → E → F” in order to leave the information from the node C to the node A.
In this way, the processing device 10 performs processing so that no loop portion exists in the trajectory information by the division processing.

The weighting unit 13 may be configured to perform weighting so that a value does not overlap each node constituting the trajectory information so that a high value is given to a temporally old node.
For example, when the trajectory information is composed of “A → B → C → D → E”, the weighting unit 13 is “5” for the node A, “4” for the node B, and “3” for the node C. ”,“ 2 ”is assigned to the node D, and“ 1 ”is assigned to the node D.
In this way, the processing device 10 can weight each node constituting the trajectory information.

As illustrated in FIG. 3, the arithmetic device 20 includes a first reception unit 21, a second reception unit 22, an integration unit 23, a calculation unit 24, and a transmission unit 25.
The first receiving unit 21 receives encrypted trajectory information transmitted by the processing device 10 as first trajectory information.
The second receiving unit 22 receives the locus information encrypted from the second terminal device 40 as the second locus information.

The integrating unit 23 integrates a plurality of pieces of first trajectory information received by the first receiving unit 21 as integrated information.
Here, the integrated information will be described. For example, the first receiving unit 21 receives encrypted trajectory information of a plurality of users (Mr. A, Mr. B, Mr. C, Mr. D, and Mr. E shown below) from the processing device 10. . For example, Mr. A's trajectory information is divided and weighted, and “A (5) → B (4) → C (3) → D (2) → E (1)” and “C (3)”. → B (2) → A (1) ”. For example, it is assumed that the trajectory information of Mr. B is “E (3) → C (2) → A (1)”. For example, it is assumed that the locus information of Mr. C is “B (3) → E (2) → C (1)”. For example, it is assumed that the track information of Mr. D is, for example, “A (3) → D (2) → E (1)”. For example, the locus information of Mr. E is, for example, “F (4) → G (3) → H (2) → I (1)”. The numbers in parentheses are the weighting values performed by the weighting unit 13.

  As shown in FIG. 4, the integration unit 23 merges the received trajectory information to generate integrated information. Note that the leftmost column (X in FIG. 4) of the table shown in FIG. 4 is not included in the integrated information because it has been deleted when transmitting from the processing device 10 to the computing device 20.

  Further, the weighting unit 13 of the processing device 10 is not limited to the above, and may perform weighting by normalizing to 1 as shown in FIG. Note that the leftmost column (X in FIG. 5) of the table shown in FIG. 5 is not included in the integrated information because it is deleted when the processing device 10 transmits to the arithmetic device 20. Further, the integrated information shown in FIGS. 4 and 5 is an example, and is not limited to this.

  The calculation unit 24 refers to the integrated information based on the second trajectory information, and calculates a node suitable for the next node following the last node constituting the second trajectory information. For example, when the second trajectory information is “A → B”, the calculation unit 24 refers to the integrated information illustrated in FIG. 4 or 5 and determines the node “C” having the highest weighting value as the node following “A → B”. Is calculated.

  The transmission unit 25 transmits the node information calculated by the calculation unit 24 to the second terminal device 40. Note that the node information transmitted from the transmission unit 25 is also encrypted.

  In this way, the computing device 20 generates integrated information from the encrypted first trajectory information, and refers to the integrated information to the next node following the last node constituting the second trajectory information. The node corresponding to is calculated, and the information of the calculated node is transmitted to the second terminal device 40. Therefore, the computing device 20 can provide information on the next node to the second terminal device 40 while protecting privacy.

The calculation unit 24 may be configured to calculate a plurality of nodes suitable for the next node following the last node constituting the second trajectory information.
The transmission unit 25 transmits information on a plurality of nodes calculated by the calculation unit 24 to the second terminal device 40.

  In this way, the computing device 20 can provide a plurality of nodes suitable as the next node to the second terminal device 40 while protecting privacy. For example, when the second trajectory information is “A → B”, the arithmetic unit 20 refers to the integrated information and calculates candidate nodes in order from the node with the highest weight value as the node following “A → B”. Then, the calculated nodes can be provided in order to the second terminal device 40.

  Here, a specific example of calculating the next node by applying the processing system 1 will be described with reference to FIG. In the following, a procedure for calculating the next place from the current place when traveling is described, but an application example of the processing system 1 according to the present embodiment is not limited thereto. For example, the present invention can be applied to calculation of a movie to be watched next.

In step S1, a data provider (corresponding to the first terminal device 30) transmits trajectory information to a data broker (corresponding to the processing device 10).
In step S2, the data broker generalizes (normalizes) the trajectory information so that it can be applied to collaborative filtering (for example, Slope One). Here, the generalization (normalization) is a process of assigning a weight value according to the place visited. For example, “5” is assigned to node A, “4” to node B, “3” to node C, “2” to node D, and “1” to node D.

  In step S3, the data broker encrypts each piece of trajectory information using, for example, a homomorphic encryption technique, and transmits the encrypted information to the cloud server (corresponding to the computing device 20). Note that, in the process of generalization, the data broker performs division when a loop exists in the trajectory information.

  In step S4, the cloud server generates integrated information based on the encrypted trajectory information.

In step S5, the user (corresponding to the second terminal device 40) transmits the trajectory information to the cloud server and searches for the next place (node).
For example, the user transmits “A → B → C” as trajectory information to the cloud server, and searches for a location (node) next to node C.

  In step S6, the cloud server refers to the integrated information based on the trajectory information transmitted from the user, calculates the next location (the node next to the node C), and transmits the calculation result to the user. The calculation result may include information (ranked) on one or a plurality of next places.

Note that, in the process of step 5, the trajectory information transmitted to the cloud server is encrypted to protect privacy.
For example, by using additive homomorphic encryption in privacy protection collaborative filtering (PPCF), the trajectory information is encrypted to protect privacy.

Further, the trajectory information is expressed by collaborative filtering by a so-called ordered tree structure (ordered vertex representation).
In addition, the original trajectory information generated by the first terminal device 30 and the second terminal device 40 is composed of location (coordinate) information, but is not limited to this, and user identity information and time stamp information. May be included.
The original trajectory information is integrated in space and time so that slight differences between different places are ignored, and converted into numerically sorted place orders (eg “A → B → C”, etc.) Then, the data is transmitted to the processing device 10 and the arithmetic device 20.

Next, the step S2 will be described in detail.
The processor 10 further converts the received trajectory information into an ordered tree structure (ordered vertex representation) by weighting all locations (nodes). For example, when the trajectory information is composed of “A → B → C → D → E”, the node A is “5”, the node B is “4”, the node C is “3”, and the node D is “2” and “1” are assigned to the node D.

  In addition, the range of weighting of the trajectory information is limited (see Non-Patent Document 1). A weight value is always given to the nodes constituting the trajectory information, and there is no node that becomes zero. It should be noted that the trajectory weight is zero at all locations outside the trajectory information.

  Further, the processing apparatus 10 determines that “A → B → C → C → D → E” is repeated when a certain node (node C in this embodiment) is repeated, such as “A → B → C → C → D → E”. B → C → D → E ”is performed, and the node that has been generated and repeated a plurality of times is deleted. That is, the processing apparatus 10 ignores (removes) the trajectory data that originally has one node and the trajectory data that has become one node due to deletion.

In this way, the processing system 1 according to the present embodiment performs encryption using the homomorphic encryption on the trajectory information, and therefore calculates the next place (node) using the cloud server (corresponding to the computing device 20). Even privacy can be protected.
In addition, since the user (corresponding to the second terminal device 40) encrypts his / her trajectory information by homomorphic encryption, the cloud server is used to set the next place (node) while protecting the privacy. You can search.

  In the present embodiment, the configuration and operation of the processing device 10 and the arithmetic device 20 of the processing system 1 that mainly calculates the next node using a server operated by a third party while protecting privacy. However, the present invention is not limited to this, and is configured as a method and program for calculating the next node by using a server operated by a third party while providing each component and protecting privacy. May be.

  Further, a program for realizing the functions of the processing device 10 and the arithmetic device 20 constituting the processing system 1 is recorded on a computer-readable recording medium, and the program recorded on the recording medium is read by the computer system. , May be realized by executing.

  The “computer system” here includes an OS and hardware such as peripheral devices. The “computer-readable recording medium” refers to a storage device such as a portable medium such as a flexible disk, a magneto-optical disk, a ROM, and a CD-ROM, and a hard disk built in the computer system.

  Furthermore, “computer-readable recording medium” means that a program is dynamically held for a short time, like a communication line when transmitting a program via a network such as the Internet or a communication line such as a telephone line. It is also possible to include one that holds a program for a certain time, such as a volatile memory inside a computer system that becomes a server or client in that case. Further, the program may be for realizing a part of the above-described functions, and may be capable of realizing the above-described functions in combination with a program already recorded in the computer system. .

DESCRIPTION OF SYMBOLS 1 Processing system 10 Processing apparatus 11 Reception part 12 Division | segmentation process part 13 Weighting part 14 Encryption part 15 Transmission part 20 Arithmetic apparatus 21 1st reception part 22 2nd reception part 23 Integration part 24 Calculation part 25 Transmission part 30 1st terminal device 40 Second terminal device

Claims (9)

A receiving unit configured with a plurality of nodes and edges, and receiving trajectory information created based on a user's behavior history;
When there is a loop portion in the trajectory information received by the receiving unit, a division processing unit that divides the trajectory information and eliminates the loop;
A weighting unit that weights each node constituting the trajectory information;
An encryption unit that encrypts the weighted trajectory information using a homomorphic encryption method;
A processing apparatus comprising: a transmission unit that transmits trajectory information encrypted by the encryption unit.   The processing apparatus according to claim 1, wherein the division processing unit divides the edge connected toward the looped node to divide the plurality of pieces of trajectory information to eliminate the loop.   The processing device according to claim 1, wherein the weighting unit performs weighting so that a value does not overlap each node constituting the trajectory information so that a high value is given to a node that is older in time. A first receiver that receives, as first trajectory information, trajectory information that has been transmitted using the homomorphic encryption method transmitted by the processing device according to claim 1;
A second receiving unit that receives trajectory information encrypted using a homomorphic encryption method as second trajectory information from the user terminal;
An integration unit that integrates a plurality of the first trajectory information received by the first reception unit as integrated information;
A calculation unit that refers to the integrated information based on the second trajectory information, and calculates a node suitable for the next node following the last node constituting the second trajectory information;
A computing device comprising a transmission unit for transmitting node information calculated by the calculation unit to the user terminal. The calculation unit calculates a plurality of nodes suitable for the next node following the last node constituting the second trajectory information,
The computing device according to claim 4, wherein the transmission unit transmits information on a plurality of nodes calculated by the calculation unit to the user terminal. Computer
Was created based on the action history Yu over The, when the loop portion exists in the trajectory information made up of a plurality of nodes and edges, a dividing process for eliminating the loop is divided into a plurality of track information ,
A weighting step for weighting each node constituting the trajectory information;
An encryption step of encrypting the weighted trajectory information using a homomorphic encryption method;
And a transmission step of transmitting the trajectory information encrypted by the encryption step. A first reception step of receiving, as first trajectory information, trajectory information encrypted by using a homomorphic encryption method transmitted by the computer according to the processing method according to claim 6;
A second receiving step for receiving, as second trajectory information, trajectory information encrypted using a homomorphic encryption method from a user terminal;
An integration step of integrating a plurality of the first trajectory information received in the first reception step as integration information;
A calculation step of referring to the integrated information based on the second trajectory information and calculating a node suitable for a next node following the last node constituting the second trajectory information;
A calculation method comprising a transmission step of transmitting node information calculated by the calculation step to the user terminal. On the computer,
When there is a loop portion in the trajectory information created based on the user's behavior history, which is composed of a plurality of nodes and edges, a division processing step for dividing the plural trajectory information and eliminating the loop;
A weighting step for weighting each node constituting the trajectory information;
An encryption step of encrypting the weighted trajectory information using a homomorphic encryption method;
The processing program for performing the transmission process which transmits the locus | trajectory information encrypted using the homomorphic encryption system by the said encryption process. On the computer,
A first receiving step of receiving, as first trajectory information, trajectory information encrypted by using a homomorphic encryption method transmitted by the processing program according to claim 8;
A second receiving step for receiving, as second trajectory information, trajectory information encrypted using a homomorphic encryption method from a user terminal;
An integration step of integrating a plurality of the first trajectory information received in the first reception step as integration information;
A calculation step of referring to the integrated information based on the second trajectory information and calculating a node suitable for a next node following the last node constituting the second trajectory information;
An arithmetic program for executing a transmission step of transmitting node information calculated by the calculation step to the user terminal.

Images