KR20220083489A - Method for location selection using user location with differential privacy applied - Google Patents

Abstract

A method for a location selection system operated by at least one processor to select a location for a query using a location of a user, comprising: a plurality of candidate locations selectable by the query, an existing facility for a plurality of existing facilities Locations, and at least one user is located in the target area, and upon receipt of a query, check the area of influence for each candidate location. The target area is composed of a plurality of Voronoi areas based on the location of each of the existing facilities, and based on the arbitrary Voronoi area and existing facilities around the arbitrary Voronoi area, the upper limit area for the arbitrary Voronoi area After configuring , the optimal location for the received query is selected by reflecting noise in the number of users located in the upper limit region.

Description

{Method for location selection using user location with differential privacy applied}

The present invention relates to a location selection method using a user location to which differential privacy is applied.

Since the use of mobile devices and location information services have become common in recent years, various services using point of interest (POI) information and users' location information have been provided. In particular, due to the development of a geographic information system (GIS), a map search service is widely used.

In addition, open platform services (eg, OpenStreet Map) provide open APIs for global GIS, making it possible to develop various location-based services using them. While user location information is being accumulated through various platforms like this, many studies are being conducted to improve user convenience and efficiently process new services using user location information.

One of them, the optimal location selection query, is a query processing technique used in commercial area analysis or establishment planning of public institutions. The optimal location selection query refers to a query that finds the optimal location for a new facility to enter, considering the locations of existing facilities and the locations of users who use them.

When the optimal location selection query is given a user set C and a set of existing facilities F, the location that has the most influence on the user is selected and returned from among the set P of candidate locations that the user can select. In this case, it is assumed that all objects and users have location information, and that users use the facility closest to their location.

While this optimal location selection query has the advantage of being applicable to practical services, it has a disadvantage in that many problems arise due to the exposure of personal location information.

Accordingly, the present invention provides a location selection method for selecting a location of maximum influence using a location of a user to which differential privacy is applied.

As a method of selecting a location for a query by using a location of a user, a location selection system operated by at least one processor, which is a feature of the present invention for achieving the technical problem of the present invention,

A plurality of candidate locations that can be selected by a query, existing facility locations for a plurality of existing facilities, and at least one user are located in a target area, and upon receiving a query, identify an impact area for each candidate location configuring the target area into a plurality of Voronoi areas based on the locations of each of the existing facilities, based on an arbitrary Voronoi area and existing facilities around the arbitrary Voronoi area, the arbitrary constructing an upper limit region for the Voronoi region of and selecting an optimal place for a query.

The step of constructing the upper limit region includes the steps of constructing a Delaunay triangle with a first existing facility located in the arbitrary Voronoi area and other second existing facilities around the first existing facility, a first circumscribed circle of the Delaunay triangle confirming, obtaining a second circumscribed circle overlapping with the arbitrary Voronoi region, and combining Voronoi cells of each of the existing facilities included in the first and second circumscribed circles to form the upper limit region may include steps.

The configuring of the Voronoi regions may include receiving a first tree for the candidate locations, a second tree for the existing facilities, and a privacy budget.

The second tree may be configured as an aR-tree for the Voronoi region for the existing facilities.

The receiving of the privacy budget may include dividing the input privacy budget into a first privacy budget and a second privacy budget.

The first privacy budget may be used to find the second tree, and the second privacy budget may be used when partitioning the Voronoi region.

As another feature of the present invention for achieving the technical problem of the present invention, a location selection system operated by at least one processor selects a location for a query by using the user's location,

A plurality of candidate locations that can be selected by a query, existing facility locations for a plurality of existing facilities, and at least one user are located in a target area, and upon receiving a query, identify an impact area for each candidate location constructing a Voronoi area for each candidate location based on the location of the existing facilities, and checking an intersection area between each Voronoi area, in the affected area consisting of a plurality of Voronoi areas for any candidate location, dividing an overlapping area and a non-overlapping area where the area affected by another candidate location overlaps, counting the number of users located in at least one Voronoi area included in the overlapping area, and each of the at least one Voronoi area calculating a noise value by reflecting the noise to the number of users, checking the number of users to which the noise is reflected for each candidate location, and selecting an optimal place for the received query.

In the checking of the intersection area between each Voronoi area, a set of points closest to the existing facilities for each candidate location may be divided using a Voronoi area division technique to generate a plurality of Voronoi areas.

The dividing of the overlapping area and the non-overlapping area may include receiving as inputs a Voronoi area set of each candidate location, a set of candidate locations, the user's location, and a privacy budget.

In the calculating of the noise value, Laplace noise may be added for each number of users located in the Voronoi region.

The calculating of the noise value may include calculating the number of users to which the noise of each candidate position is reflected by adding noise values calculated for each candidate position and a plurality of Voronoi regions.

According to the present invention, by applying differential privacy to the user's location, it is possible to protect the user's location, that is, personal information.

In addition, it is possible to solve the problem of decreasing accuracy due to the overlapping problem of the affected area when applying differential privacy when processing the optimal place selection query.

1 is an exemplary diagram of a conventional optimal place selection query.
2 is a structural diagram of a location selection system according to an embodiment of the present invention.
3 is a flowchart of a location selection method according to the first embodiment of the present invention.
4 is an exemplary diagram of a Voronoi region division method according to the first embodiment of the present invention.
5 is a flowchart of a location selection method according to a second embodiment of the present invention.
6 is an exemplary diagram illustrating a process of configuring an upper limit region of a Voronoi region according to an embodiment of the present invention.

Hereinafter, with reference to the accompanying drawings, the embodiments of the present invention will be described in detail so that those of ordinary skill in the art to which the present invention pertains can easily implement them. However, the present invention may be embodied in several different forms and is not limited to the embodiments described herein. And in order to clearly explain the present invention in the drawings, parts irrelevant to the description are omitted, and similar reference numerals are attached to similar parts throughout the specification.

Throughout the specification, when a part "includes" a certain element, it means that other elements may be further included, rather than excluding other elements, unless otherwise stated.

Hereinafter, a system and method for selecting a location using a user's location according to an embodiment of the present invention will be described in detail with reference to the drawings. Prior to describing an embodiment of the present invention, an example of selecting an optimal place by various methods in the prior art will be first described with reference to FIG. 1 .

1 is an exemplary diagram of a conventional optimal place selection query.

The optimal location selection query refers to a query that finds the optimal location for a new facility to enter, considering the locations of existing facilities and the locations of users who use them. Given a user set C and a set of existing facilities F, the optimal location selection query selects and returns the candidate location that has the most influence on the user from among the set P of candidate locations that the user can select.

In this case, it is assumed that all objects and users have location information, and that users use the facility closest to their location. The optimal location selection query can have different objective functions depending on the application service. It is mainly divided into the following three methods according to the user's selection purpose.

The first method is the optimal location selection query method (Max-inf), which maximizes the users affected to attract customers, such as the analysis of the commercial area. As another method, there is a method used to reduce the distance from all customers (min-sum), such as when a new franchise restaurant is opened, and finally, for the installation of public institutions such as fire stations or police stations, the distance of the furthest user is calculated. There is a method used to minimize (Min-max).

As shown in Fig. 1(a), the first method (Max-inf) wants to find a location that can influence as many users as possible among candidate locations when the query requester is located in a competitive commercial area. . At this time, it is assumed that all place objects and users are points located on the Euclidean plane, and the distance between the two objects as an objective function uses the Euclidean distance to determine the position with the highest influence on the user among the given candidate sets using Equation 1 find out

Here, w(c) denotes the influence of users, and may be applied differently for each application service. However, since this value does not fundamentally affect the query processing method, it is assumed to be 1 for explanation.

And, IS(p) means a set of users affected by candidate locations on the assumption that users use the most recent facility. The user set affected by the candidate location can be defined as in Equation 2 below.

In (a) of FIG. 1 , users affected by P ₁ are {c ₂ }, users affected by P ₂ are {c ₃ , c ₄ }, and users affected by P ₃ are {c ₃ , c ₄ , c ₅ }. According to Equation 1, in the Max-inf method, since P ₃ can affect the most users, it is returned to the optimal place.

Meanwhile, as shown in (b) of FIG. 1 , the second method, the min-sum method, selects and returns a new point for providing service convenience to the user from the point of view of the brand manager. Since it is assumed that all existing facilities play complementary roles, the goal is to find a candidate location with the smallest sum of distances to users.

Min-sum, like Max-inf, assumes that all users use the nearest facility, and the objective function of Min-sum is defined as in Equation 3 below.

The result when the objective function is changed to Min-sum for an example such as Max-inf is as shown in (b) of FIG. 1 .

And, when the cost function value for p ₁ among each candidate position is obtained using Equation 3, d(f ₁ ,c ₁ )+d(f ₁ ,c ₃ )+d(f ₂ ,c ₄ )+d( f ₂ ,c ₅ )+d(p ₁ ,c ₂ )=8+16+13+9+5=51. On the other hand, p ₂ is 48 and p ₃ is 51, so in case of min-sum, p ₂ is the optimal place.

Another method, Min-max, aims to provide public services to users. Therefore, the candidate facility is selected in a direction in which the largest distance value among the distances from each facility to the user becomes smaller. Like min-sum, each facility plays a complementary role, and it is assumed that users use the nearest facility. The objective function of the Min-max method is defined as in Equation 4 below.

As shown in Fig. 1(c), when the optimal place is selected with Max-max, the cost function is d(c ₂ ,f ₁ ) because both p ₁ and p ₃ do not have an effect on d(c 2 ,f 1 ) with the largest distance. =25 is maintained. On the other hand, since p ₁ is the nearest facility to c ₂ , the cost function value is lowered from d(c ₂ ,f ₁ )=25 to d(c ₃ ,f ₁ )=16. Therefore, in case of Min-max, p ₁ is the optimal place.

As described above, when querying for optimal location selection using the conventional method, when candidate locations are close to each other, user information is duplicated, and thus the user location is exposed.

Accordingly, an embodiment of the present invention provides a system and method for selecting a place with high accuracy while protecting personal location information by applying differential privacy when processing an optimal place selection query. In the embodiment of the present invention, for convenience of description, Max-inf is used as an example as a query technique, but the present invention is not limited thereto.

In the embodiment of the present invention, two embodiments will be described as an example for the location selection system 100 to select a location for an optimal location selection query. Before describing the embodiment of the present invention, terms mentioned in the embodiment of the present invention, that is, differential privacy, sensitivity, sequential configuration, and affected area are first defined as follows.

Differential privacy is a privacy protection technique. Given an arbitrary mechanism M and an event set _S⊆Range (M), _{for two neighboring databases D 1 and D 2 that satisfy} When Equation 5 below is satisfied, the mechanism M satisfies differential privacy.

In Equation 5, ε means a privacy protection budget, and means a degree of protection of data to be protected as a system parameter. Also, ?, ? ₁ means the L ₁ norm, and the neighbor database refers to a database pair that differs only in the existence or nonexistence of any one tuple.

As another important parameter in the concept of differential privacy, the sensitivity that affects the query accuracy is a value determined according to the mechanism M. That is, given the neighboring databases D ₁ and D ₂ , the sensitivity of the mechanism M is a measure indicating how much influence on the result of M in the worst case depending on the existence of one tuple, Equation 6 is expressed as

In Equation 6, the sensitivity may be defined differently as the L ₁ norm and the L ₂ norm, depending on the applied mechanism. However, in the case of a counting query query related to an embodiment of the present invention, since it is defined as the L ₁ norm, all sensitivities to be described later refer to sensitivities defined as the L ₁ norm unless otherwise specified.

Due to the nature of the definition of differential privacy, if a query to the same database is repeated, the possibility of personal information being leaked increases. This problem is called sequential configuration, and no matter what mechanism is used, it has the following properties.

Given two arbitrary mechanisms M ₁ and M ₂ and privacy budgets ε ₁ and ε ₂ for each mechanism, the combination M _1,2 of the two mechanisms satisfies (ε ₁ +ε ₂ )-differential privacy. Therefore, the combination of successive mechanisms will increase the privacy budget linearly, and if the result of the entire mechanism is to use the total amount of privacy budget, more noise should be added to each mechanism.

In order to process the optimal place selection query based on differential privacy, the query must be processed by applying a mechanism that satisfies the differential privacy for each objective function when selecting the optimal place. However, when candidate locations are close to each other, a problem in which user information is duplicated and exposed commonly occurs. For convenience, the Max-inf method is described.

An intuitive way to apply differential privacy to the Max-inf method is to apply the Laplace mechanism in query processing. The Laplace mechanism satisfies differential privacy by generating and adding noise from the Laplace distribution to the query result.

In order to apply the Laplace mechanism to the Max-inf method, it is necessary to first configure the area where the candidate position affects. This is called an influence region of the candidate location.

All users located in the affected area use the candidate area p as the nearest facility, which means that the set of these users is IS(p) in Equation 2 above. Therefore, if an influence region is configured for every candidate region, an optimal place selection query can be performed.

2 is a structural diagram of a location selection system according to an embodiment of the present invention.

As shown in FIG. 2 , in the location selection system 100 operated by at least one processor, a program including instructions described to perform the operation of the present invention is executed. The program may be stored in a computer-readable storage medium and may be distributed.

Hardware of the location selection system 100 may include at least one processor 110 , a memory 120 , a storage 130 , and a communication interface 140 , and may be connected through a bus. In addition, hardware such as an input device and an output device may be included. The location selection system 100 may be loaded with various software including an operating system capable of driving a program.

The processor 110 is a device for controlling the operation of the location selection system 100 and may be various types of processors that process instructions included in a program, for example, a central processing unit (CPU), a micro processor (MPU) unit), microcontroller unit (MCU), graphic processing unit (GPU), or the like.

The processor 110 constructs a candidate location and an influence region for any point on the Euclidean space in order to process the differential privacy-based best place selection query. A method of constructing a candidate location and an area of influence for an arbitrary point will be described in detail later.

In addition, the processor 110 divides the affected region into a plurality of Voronoi regions using a voronoi region partitioning technique. In addition, the processor 110 identifies at least one overlapping candidate location in order to protect personal location information, and applies differential privacy to the checked overlapping candidate location.

In addition, the processor 110 calculates an upper bound region for the influence region of the candidate location by using the extended Voronoi region pruning technique based on the R-tree structure. When the processor 110 calculates the upper bound region, Delaunay triangulation is used, which will be described in detail.

The memory 120 loads the corresponding program so that the instructions described to execute the operation of the present invention are processed by the processor 110 . The memory 120 may be, for example, read only memory (ROM), random access memory (RAM), or the like. The storage 130 stores various data and programs required to execute the operation of the present invention. The communication interface 140 may be a wired/wireless communication module.

A method for the location selection system 100 described above to select an optimal location by processing an optimal location selection query will be described with reference to FIGS. 3 to 6 . In FIG. 3, a method according to the first embodiment of processing an optimal place selection query using the Voronoi region partitioning technique is described. In FIG. 5, the optimal place selection using the extended Voronoi region pruning technique based on the R-tree structure is described. A method according to the second embodiment of processing a query will be described.

3 is a flowchart of a location selection method according to the first embodiment of the present invention.

When an optimal place selection query is performed by applying a sequential configuration through the prior art, there is a problem in that the accuracy is exponentially reduced. To solve this problem, an embodiment of the present invention proposes a Voronoi region partitioning method (VPM) in which a parallel composition is applied by dividing a Voronoi region. Here, the Voronoi region refers to an area obtained by dividing a two-dimensional plane into a set of points having the closest distance from an arbitrary point on a two-dimensional plane in which a plurality of existing facilities are located to the existing facility.

As shown in Fig. 3, in order to apply the Voronoi region segmentation method in the process of returning the optimal position for the query, the position selection system 100 first selects the optimal position for the query in the Euclidean space, that is, two-dimensional. A candidate location is identified in the entire area (hereinafter, referred to as a 'target area' for convenience of description) composed of the coordinate plane of ( S100 ). Here, the candidate position is preset at an arbitrary position in the target area.

The location selection system 100 generates influence regions based on each candidate location ( S110 ). Here, the affected area is a Voronoi area created by combining any one candidate location and existing facilities for each candidate location is referred to as an impact area of the corresponding candidate location. That is, a set of points having the closest distance to a candidate location among arbitrary points on a two-dimensional plane may be referred to as an influence region. Since the method for the location selection system 100 to generate the affected area based on the candidate location can be generated in various ways, the embodiment of the present invention is not limited to any one method.

The location selection system 100 configures the Voronoi area with the existing facilities for each candidate location, and checks the intersection area between the Voronoi areas (S120). Then, the location selection system 100 receives as inputs a Voronoi area set of each candidate location, a set of candidate locations, a user location, and a privacy budget ( S130 ).

The location selection system 100 divides an overlapping area and a non-overlapping area that overlaps the impact area identified by another candidate location among the affected areas of each candidate location received in step S130 (S140). And the location selection system 100 counts the number of users located in the Voronoi area of the confirmed overlapping area (S150).

After counting the number of users in the Voronoi region of the overlapping region, the location selection system 100 calculates a noise value for each Voronoi region by reflecting the noise to the number of users for each Voronoi region (S160). In the embodiment of the present invention, the Laplace mechanism is applied to reflect noise to the number of users located in each Voronoi region of the overlapping region as an example, and the Laplace mechanism is already known, and detailed description is omitted in the embodiment of the present invention.

The position selection system 100 calculates a noise value for a corresponding candidate position by adding noise values for each Voronoi region of the overlapping region, and selects an optimal place among a plurality of candidate regions based on the calculated noise value for each candidate position to provide (S170).

4 is an exemplary diagram of a Voronoi region division method according to the first embodiment of the present invention.

As shown in Figure 4, the location selection system 100 calculates an area of influence for every candidate location. The location selection system 100 receives as inputs a Voronoi region set of candidate locations, a set of candidate locations, a user location, and a privacy budget, and performs the algorithm shown in Table 1 below.

The algorithm of Table 1 is an algorithm showing the process of generating a noise count for each Voronoi region, and the algorithm of Table 2 is an algorithm for the process of calculating the divided region.

The location selection system 100 uses the algorithm of Table 1 to first obtain a set of duplicate candidate locations in which an intersection area occurs for each candidate location, and then calls the algorithm of Table 2 to calculate the partitioned area.

When the segmented area is obtained, the location selection system 100 generates a noise count for each segmented area, and then returns a candidate location having the largest noise count. Lines 5 to 7 of the algorithm in Table 1 are the part to obtain a set of duplicate candidate positions, and the 8th line is the part to call the algorithm in Table 2 to calculate the partition area.

Finally, it returns the segmented region and generates noise counts from the 10th to 12th lines. The algorithm in Table 2 is called recursively with a code that calculates a partition region in a divide-and-conquer manner. Here, pv denotes an area divided up to now, and j denotes an index of the number of candidate positions from the set of overlapping candidate positions to which the overlapping region is calculated.

The location selection system 100 repeats the algorithm of Table 2 until it calculates the overlapping area of all candidate locations in the set of redundant candidate locations. Then, in the algorithm of Table 2, the intersection area is calculated in the 8th line, and the intersection area and the non-intersecting area are divided in the 9th line. Then, the location selection system 100 recursively calls the algorithm to calculate the overlapping area with other candidate locations for each case in lines 10-11. Finally, the partitioned regions are combined and returned.

Referring to the case of p ₁ in (a) of FIG. 1 described above as an example, the location selection system 100 selects the Voronoi regions A to C for p ₁ as shown in FIG. 4 (a). make up And, when users included in areas A, B, and C are found, A:{c ₂ }, B:{ }, and C:{ } are obtained as shown in FIG. 4(b). And the noise value of p ₁ becomes (2+n _A )+(0+n _B )+(0+n _C )=(2+n _A +n _B +n _C ). Here, n _X means noise added to the area X, respectively.

In this way, when the Voronoi region is divided and a noise count is generated for each Voronoi region, the affected region overlapping problem can be solved because the affected regions of the candidate locations do not intersect.

에 비례하여 증가하기 때문에 정확도 면에서 순차구성보다 더 효과적이다. In addition, when noise is added to the divided Voronoi region, a parallel configuration of differential privacy can be applied. If the number of divided regions in the Voronoi region division method is N, the total noise added according to the characteristics of the parallel configuration is

Since it increases in proportion to , it is more effective than sequential configuration in terms of accuracy.

Next, a method for high-accuracy and efficient query processing by dividing a privacy budget in order to reduce unnecessary computation costs by filtering out candidate locations having little influence on users in advance will be described as a second embodiment. That is, a method of selecting an optimal position using the R-tree structure-based extended Voronoi region pruning technique rather than the Voronoi region division technique will be described with reference to FIG. 5 .

5 is a flowchart of a location selection method according to a second embodiment of the present invention.

As shown in FIG. 5 , the location selection system 100 first checks the locations of the existing facilities in the target area (S200), and then checks the affected areas based on the candidate locations located in the target area (S210) .

And it is divided into Voronoi areas based on each existing facility (S220). At this time, the method for the location selection system 100 to divide the Voronoi areas based on existing facilities may be performed in various ways, so the embodiment of the present invention is not limited to any one method. And the candidate position is included in any one of the plurality of Voronoi regions.

The location selection system 100 receives a first tree (R _p ) for candidate locations, a second tree (R _f ) for each existing facility, and a privacy budget as inputs ( S230 ). Here, the shapes of the first tree and the second tree are not limited to any one shape.

And the location selection system 100 divides the received privacy budget into a first privacy budget (ε ₁ ) and a second privacy budget (ε ₂ ) ( S240 ). ε ₁ is used to find a candidate location with low influence, that is, R _f , which is the second tree, and ε ₂ is used when applying the Voronoi domain partitioning technique in the query processing process. In the embodiment of the present invention, the method for the location selection system 100 to divide the privacy budget into the first privacy budget and the second privacy budget, and the dividing ratio are not described as limiting to either one.

The location selection system 100 selects an arbitrary Voronoi region to configure the upper limit region from among the plurality of Voronoi regions ( S250 ). There are various methods for the location selection system 100 to select an arbitrary Voronoi region, and since an upper limit region is configured for all Voronoi regions, a selected Voronoi region is not specifically described.

The location selection system 100 configures a Delaunay triangle with other existing facilities located in the Voronoi area around the selected Voronoi area (S260). That is, the position selection system 100 obtains the circumscribed circle of the Delaunay triangle overlapping the selected Voronoi region.

Here, the Delaunay triangle is a method of creating a triangle by connecting three neighboring points based on the vertices of the Voronoi region when there is a set of discrete points comprising the Voronoi diagram, and dividing the plane so that no other points enter the circumcircle of the triangle. . At this time, the center of the circumscribed circle becomes the vertex of the Voronoi region. If a new point is input, all Delaunay triangles in which the input point is located within the circumcircle are affected, and the points related to this triangle become Voronoi neighbors of the newly input point.

The position selection system 100 configures an upper limit region of the selected Voronoi region (S270). That is, the Voronoi cells of the existing facilities related to the circumscribed circles obtained in step S260 are combined to form an upper limit region of the selected Voronoi region. In this case, the configured upper limit region is larger than the influence region of the candidate located in the selected Voronoi region. And even if the candidate area is located elsewhere within the Voronoi cell of the existing facilities, the affected area is smaller than the upper limit area.

The location selection system 100 reflects the noise to the number of users located in the upper limit region configured in step S270 (S280). To this end, the location selection system 100 uses two R-trees, and can be divided into an R-tree (R _p ) for a candidate location and an R-tree (R _f ) for an existing facility location.

Here, R _f , which is an R-tree for the location of an existing facility, is composed of an aR-tree for the Voronoi region of the existing facilities. The aR-tree is a modified form of the R-tree, and each node has aggregation values. In the embodiment of the present invention, it will be described as an example having an upper limit value of the noise count.

The location selection system 100 selects and returns an optimal location based on the number of users to which noise is reflected for each upper limit region of each candidate location in step S280 (S290).

Next, a process of configuring the upper limit region of the Voronoi region will be described with reference to FIG. 6 .

6 is an exemplary diagram illustrating a process of configuring an upper limit region of a Voronoi region according to an embodiment of the present invention.

As shown in (a) of Figure 6, the location selection system 100 constitutes a Voronoi diagram with existing facilities. This is shown to show that when the upper limit area is configured with a random candidate location p ₁ , the affected area of the candidate location is wider than the impact area of the existing facility f ₂ . In the embodiment of the present invention, p ₁ among a plurality of candidate locations will be described as an example, and configuration of an upper limit region of f ₂ among a plurality of existing facilities will be described as an example.

As shown in (b) of FIG. 6 , the shaded Voronoi area indicates the Voronoi area of the existing facility, which is a target for configuring the upper limit area.

The location selection system 100 goes through the following steps to configure the upper limit area of the selected existing facility f ₂ . First, it composes the Delaunay triangle with other existing facilities in the vicinity.

To this end, the location selection system 100 constructs the circumscribed circle of the Delaunay triangle, and as shown in FIG. 6(c) , obtains a circumscribed circle overlapping the Voronoi region of f ₂ . Then, the location selection system 100 finds the circumscribed circle of each Delaunay triangle, and finds the circumscribed circles overlapping the shaded area shown in FIG. 6( c ).

And, as shown in (d) of FIG. 6, the location selection system 100 constitutes an upper limit region of f ₂ . At this time, the Voronoi cells of the existing facilities related to the circumscribed circles obtained in (c) of FIG. 6 are combined to form an upper limit region. It can be seen that the upper limit area configured by the location selection system 100 is larger than the area affected by the candidate location (hatched area, ①), as shown in FIG. 6E .

At this time, when a new candidate position is input as a point, all Delaunay triangles in which the input point is located within the circumcircle are affected. Points related to this triangle become Voronoi neighbors of the newly input point. The location selection system 100 defines a candidate Voronoi neighbor as in Equation 7 below.

Here, if DT is the Delaunay triangle set composed of the set of existing facilities, and Disk() is the circumscribed circle of the Delaunay triangle, the candidate Voronoi neighborhood is defined as a subset of the existing facilities.

A candidate Voronoi neighborhood is an upper bound set of existing facilities that will be affected if any candidate location p is located in V(f). Therefore, the affected area of the candidate location p cannot be larger than the Voronoi area of existing facilities included in the candidate Voronoi neighborhood. Therefore, a set of Voronoi regions of existing facilities included in CVN(p) is called an extended Voronoi region, and a noise count is generated using ε ₁ . When the position selection system 100 generates the noise count, the following equations (8) and (9) are used.

Equation 9 has the same form as Equation 6 described above, except that 1 is entered in the Laplace noise part instead of the size of the set of overlapping candidate positions.

After finding candidate Voronoi neighbors for Voronoi regions of all existing facilities and generating noise counts, unnecessary candidate positions may be pruned during query processing. In the extended Voronoi domain method, the index R _f of existing facilities is constructed using aR-tree, and query processing is performed by searching for R _f using the best first search method.

In the terminal node of R _f , the largest value among the Voronoi region of existing facilities and the upper limit of the noise count is stored. In addition, upper limit values for own child nodes are stored in the root node and the intermediate node. The upper limit of the noise count for each node is calculated as in Equation 10 when the node is an intermediate node including the root node, and is calculated as Equation 11 in other cases.

The Voronoi region-based query processing method uses three R-tree structures: an R-tree R _p for candidate locations, an R-tree R _c for user locations, and an aR-tree R _f for existing facilities. . The Voronoi envelope based filtering method (VEM) basically searches for R _f while searching for intermediate nodes of R _p , and at the same time prunes when the upper limit of the noise count is lower than the optimal count calculated so far.

If the terminal node is reached, the region is divided based on Voronoi for the relevant candidate positions. When E _p (E _f ) is a node or objects of R _p (R _f ), the overall query processing process can be divided into the following four cases according to the types of nodes.

i) When E _p , E _f are both nodes of the R-tree,

ii) When E _p is a candidate location object, and E _f is a node of the R-tree,

iii) When E _p is an R-tree node, and E _f is the Voronoi region of an existing facility,

iv) When E _p is a candidate location object, and E _f is the Voronoi area of an existing facility,

The position selection system 100 uses the priority queue to find the candidate Voronoi neighbors related to the candidate positions in the above four cases, and at the same time compares the noise count upper limit value with the optimal count value to determine whether or not to insert it into the queue .

In case i), the child nodes of E _p and E _f are searched, and the child node pairs where their MBRs intersect are found and inserted into the queue only when the noise count upper limit is greater than the optimal count value.

In case ii), the child nodes of E _f are searched, the child nodes containing E _p are found, and the noise count upper limit is greater than the optimal count value and inserted into the queue.

In case iii), the child nodes of E _p are searched, and only when the upper limit of the noise count of E _f is greater than the optimal count value, it is inserted into the queue.

Finally, in case iv), Voronoi-based region division is performed and, if necessary, the optimal count value is updated.

Although the embodiments of the present invention have been described in detail above, the scope of the present invention is not limited thereto, and various modifications and improvements by those skilled in the art using the basic concept of the present invention as defined in the following claims are also provided. is within the scope of the right.

Claims (11)

A method for a location selection system operated by at least one processor to use a location of a user to select a location for a query, the method comprising:
A plurality of candidate locations that can be selected by a query, existing facility locations for a plurality of existing facilities, and at least one user are located in the target area;
upon receiving a query, identifying an area of influence for each candidate location;
Composing the target area into a plurality of Voronoi areas based on the location of each of the existing facilities;
Constructing an upper limit area for the arbitrary Voronoi area based on the arbitrary Voronoi area and existing facilities around the arbitrary Voronoi area;
reflecting noise to the number of users located in the upper limit region; and
Checking the number of users to which noise is reflected for each candidate location composed of at least one upper limit region, and selecting an optimal location for the received query
A method of selecting a location, including. According to claim 1,
The step of configuring the upper limit region comprises:
constructing a Delaunay triangle with a first existing facility located in the arbitrary Voronoi area and other second existing facilities around the first existing facility;
identifying a first circumscribed circle of the Delaunay triangle;
obtaining a second circumscribed circle overlapping the arbitrary Voronoi region, and
Combining Voronoi cells of each of the existing facilities included in the first circumscribed circle and the second circumscribed circle to form the upper limit region
A method for selecting a location, including. 3. The method of claim 2,
The step of configuring the Voronoi regions comprises:
receiving a first tree for the candidate locations, a second tree for the existing facilities, and a privacy budget;
A method of selecting a location, including. 4. The method of claim 3,
The second tree is composed of an aR-tree for the Voronoi region for the existing facilities. 5. The method of claim 4,
Receiving the privacy budget comprises:
and dividing the input privacy budget into a first privacy budget and a second privacy budget. 6. The method of claim 5,
wherein the first privacy budget is used to find the second tree, and the second privacy budget is used when partitioning the Voronoi region. A method for a location selection system operated by at least one processor to use a location of a user to select a location for a query, the method comprising:
A plurality of candidate locations that can be selected by a query, existing facility locations for a plurality of existing facilities, and at least one user are located in the target area;
upon receiving a query, identifying an area of influence for each candidate location;
constructing a Voronoi area for each candidate location based on the locations of the existing facilities, and checking an intersection area between each Voronoi area;
dividing an overlapping area and a non-overlapping area in which an area of influence by another candidate location overlaps in an area of influence composed of a plurality of Voronoi areas for any candidate position;
counting the number of users located in at least one Voronoi region included in the overlapping region, and calculating a noise value by reflecting noise in the number of users for each Voronoi region; And
Checking the number of users with noise reflected for each candidate location, and selecting an optimal location for the received query
A method for selecting a location, including. 8. The method of claim 7,
The step of confirming the intersection area between each Voronoi area is,
A location selection method for generating a plurality of Voronoi areas by dividing a set of points closest to the existing facilities for each candidate location using a Voronoi area segmentation technique. 9. The method of claim 8,
The step of dividing the overlapping region and the non-overlapping region includes:
receiving as inputs a Voronoi area set of each candidate location, a set of candidate locations, a location of the user, and a privacy budget;
A method of selecting a location, including. 10. The method of claim 9,
Calculating the noise value comprises:
A location selection method of adding Laplace noise according to the number of users located in the Voronoi region. 11. The method of claim 10,
Calculating the noise value comprises:
For each candidate location, the number of users to which the noise for each candidate location is reflected by adding the calculated noise values for a plurality of Voronoi regions is calculated as a location selection method.

Images