GIS INFORMATION RETRIEVAL METHOD USING DYNAMIC K-NEAREST NEIGHBOR SEARCH ALGORITHM IN AN OBSTACLE ENVIRONMENT

Abstract

The present disclosure relates to a GIS geographical information retrieval method using a dynamic k-nearest neighbor search algorithm in an obstacle environment, which has been devised to search for geographical information by using a dynamic k-nearest neighbor search algorithm in an obstacle environment. The GIS geographical information retrieval method using a dynamic k-nearest neighbor search algorithm in an obstacle environment has an effect in that it can optimize a search time by considering obstacles as a range of angles, not discrete objects, on the basis of a query point, using the shortest path characteristics at the same time, and assigning priority to neighbors based on the calculated range of angles.

Claims

1. A GIS (GIS) geographical information retrieval method using a dynamic k-nearest neighbor search algorithm in an obstacle environment, the method comprising: dividing a static data structure into smaller static data structures; considering obstacles as a range of angles on the basis of a query point; approximating and pre-processing the obstacles by using shortest path characteristics between the obstacles; and calculating a shortest distance from the query point to surrounding neighbors based on the approximated and pre-processed obstacles.

2. The method of claim 1, wherein in the dividing of the data structure, a surrounding situation is incorporated into only some of the divided data structures, not all of static data structures, in a situation in which the surrounding neighbors are changed in real time.

3. The method of claim 1, wherein the considering of the obstacles comprises an assumption that convex hulls of the obstacles do not cross each other.

4. The method of claim 3, wherein in the considering of the obstacles, the obstacles are represented as a continuous range of angles on the basis of a search point by substituting the obstacles with the convex hulls of the obstacles.

5. The method of claim 4, wherein in the approximating and pre-processing of the obstacles, a visibility graph using vertexes of the convex hulls of the obstacles as peaks is calculated.

6. The method of claim 5, wherein in the approximating and pre-processing of the obstacles, when a number of the peaks of the vertexes of the convex hulls of the obstacles is n, a time taken to calculate the visibility graph is determined as n log n.

7. The method of claim 1, wherein in the calculating of the shortest distance, a search time is optimized by assigning priority to the surrounding neighbors based on the calculated range of angles of the obstacles.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0018] FIG. 1 is a flowchart of a GIS geographical information retrieval method using a dynamic k-nearest neighbor search algorithm in an obstacle environment according to an embodiment of the present disclosure.

[0019] FIGS. 2(a) to 2(c) are diagrams simply illustrating a process of constructing an input which may be input to a computer based on actual geographical information and searching for the nearest neighbor by using the GIS geographical information retrieval method according to an embodiment of the present disclosure.

[0020] FIG. 3 is a schematic diagram illustrating a shape of a data structure that is constructed for a fast operation of a geographical information search algorithm that is proposed in an embodiment of the present disclosure.

DETAILED DESCRIPTION

[0021] The present disclosure relates to a method for improving GIS information retrieval performance through an improved dynamic k-nearest neighbor search algorithm in an obstacle environment.

[0022] Hereinafter, geographical information retrieval refers to a function of returning a facility near a given location, among facilities that currently provide a service to be used, when a current location and the service are given.

[0023] Most of conventional neighbor search algorithms do not reflect facility information that is changed in real time, and are not efficient because the neighbor search algorithms perform unnecessary search although the neighbor search algorithms reflect the facility information.

[0024] The present disclosure provides a more efficient GIS information retrieval function by narrowing a search range by using the shortest path characteristics between obstacles.

[0025] Hereinafter, the contents of the present disclosure will be described in more detail with reference to the drawings.

[0026] FIG. 1 is a flowchart of a method 100 of searching for, by a GIS, geographical information using a dynamic k-nearest neighbor search algorithm in an obstacle environment according to an embodiment of the present disclosure.

[0027] Referring to FIG. 1, the method 100 of searching for, by a GIS, geographical information using a dynamic k-nearest neighbor search algorithm in an obstacle environment according to an embodiment of the present disclosure includes step S110 of dividing a static data structure into smaller static data structures, step S120 of considering obstacles as a range of angles on the basis of a query point, step S130 of approximating and pre-processing the obstacles by using the shortest path characteristics between the obstacles, and step S140 of calculating the shortest distance from a query point to surrounding neighbors based on the approximated and pre-processed obstacles.

[0028] A detailed description of step S110 of dividing a static data structure into smaller static data structures to step S140 of calculating the shortest distance illustrated in FIG. 1 is as follows.

[0029] In step S110 of dividing a data structure, points, that is, neighbor search targets, are not considered as one set, but are divided into smaller sets, thus constructing a data structure. That is, a static data structure is divided into smaller static data structures in order to have the same effect as that of a dynamic data structure.

[0030] In this case, corresponding data structures are designed to support fast search for the nearest neighbor even in a dynamic situation in which neighbor search target points are added. Accordingly, there is an effect in that the time taken to search for the nearest neighbor can be finally reduced by applying, to each of the data structures, the shortest distance algorithm to be subsequently presented in step S140 of calculating the shortest distance.

[0031] FIGS. 2(a) to 2(c) are diagrams simply illustrating a process of constructing an input which may be input to a computer based on actual geographical information and searching for the nearest neighbor by using the GIS geographical information retrieval method according to an embodiment of the present disclosure. For example, FIGS. 2(a) to 2(c) illustrate a process of searching for a location of the nearest bank from a query point when geographical information around Jamsil Lotte Tower in Seoul and the query point are given.

[0032] FIG. 2(a) is a diagram illustrating the locations of a map and banks around Jamsil Lotte Tower in Seoul. In FIG. 2(b), obstacles (e.g., a building and a lake) are represented as convex hulls, which are indicated as O.sub.1, O.sub.2 to O.sub.8, respectively. The location of the bank is indicated as a square point, and a query point is indicated as “q”. In this case, the nearest obstacle, among the obstacles including the banks, is searched for, and the obstacle O.sub.4 is selected.

[0033] FIG. 2(c) illustrates internal structures of the obstacle O.sub.4. The nearest bank is searched for within the obstacle O.sub.4.

[0034] FIG. 3 is a schematic diagram illustrating a shape of a data structure that is constructed for a fast operation of a geographical information search algorithm that is proposed in an embodiment of the present disclosure.

[0035] Step S110 of dividing a data structure may be implemented as a programming code based on <Pseudo code 1> and <Pseudo code 2>.

TABLE-US-00001 <Pseudo code 1> Algorithm initializeDataStructure(S, O) Input : A set S of points and a set O of polygon obstacles wherein the number of points is n Output : A set of data structures DS for a k-nearest neighbor query based on S, O  1: initialize DS = Ø  2: initialize to i = 1  3: decrease from for j=log n to 1  4:  if S  ≥ 2.sup.j  5:   produce a subset S  of S having a size of 2.sup.j  6:   DS ← DS ∪ constructDataStructure(S , O)  7:   S ← S\S  8:     ←  + 1  9:  end if 10: end for 11: return DS indicates data missing or illegible when filed

TABLE-US-00002 <Pseudo code 2> Algorithm insertDataStructure(q) Input : data structures for a query DS , ... , DS  a point to be inserted Output : data structures including q DS , ... , DS  1: DS  ← initializeDataStructure({q}, O)  2: initialize to i = 1  3: while  4:  if |DS | ≠ |DS |  5:   break  6:   DS  ← initializeDataStructure({q}, O)  7:  end if  8:  DS  ← initializeDataStructure(S  ∪ S , O)  9:   i = i + 1 10: end while 11: from for j = 1 to t 12:  DS  ← DS 13: end for 14: return DS , . . . , DS indicates data missing or illegible when filed

[0036] In step S120 of considering obstacles, the obstacles are considered as a range of an angle based on a query point. In this case, assuming that the convex hulls of obstacles, such as a building and a house in most cases of real life, do not cross each other based on the ideas that the convex hulls do not cross each other, each obstacle is substituted with its convex hull. By substituting the obstacle with the convex hull, each obstacle may be represented as a continuous range of angles on the basis of a search point.

[0037] Step S120 of considering obstacles may be implemented as a programming code based on <Pseudo code 3>.

TABLE-US-00003 <Pseudo code 3> Algorithm constructDataStructure(S, O)  Input : a set S of points, a set O of polygon obstacles  Output : a data structures DS for a k-nearest neighbor query based  on S, O  1: initialize structure DS  2: initialize a set of convex hulls of obstacle O′ = Ø  3: for each obstacle o ∈ O  4: calculate convex hulls o′ of o  5: connect o and o′ by pointer  6:  O′ ← O′ ∪ {o′}  7: end for  8: calculate a visibility graph VG based on vertexes of O′ and s  9: store information on S, O, O′, VG 10: return DS

[0038] In step S130 of approximating and pre-processing the obstacles, the obstacles are approximated and pre-processed by using the shortest path characteristics between the obstacles. In particular, in this step, an algorithm may be designed to reduce the time taken to search for the nearest neighbor by using the shortest distance characteristics on a plane.

[0039] Specifically, a visibility graph is calculated by using, as peaks, the vertexes of the convex hulls calculated in step S120 of considering obstacles. Assuming that a total number of peaks are n in the graph in which the vertexes of convex polygons on a plane are peaks, a visibility graph may be calculated within a predetermined time corresponding to n log n. However, if the visibility graph is calculated by using the peaks of obstacles themselves not their convex hulls, the time corresponding to n{circumflex over ( )}2 is consumed assuming that the number of peaks is n.

[0040] Accordingly, an embodiment of the present disclosure can have an effect in that it can reduce the time taken to calculate a visibility graph by adding the assumption that the convex hulls of obstacles do not cross each other.

[0041] In step S140 of calculating the shortest distance, the shortest distance from a query point to surrounding neighbors is calculated based on the obstacles approximated and pre-processed in step S130 of approximating and pre-processing the obstacles, and the k-nearest neighbor is finally returned. In this case, the process of calculating the shortest distance up to the surrounding neighbors is performed by applying the shortest distance algorithm (e.g., Dijkstra's algorithm) on the visibility graph calculated in step S130 of approximating and pre-processing the obstacles.

[0042] In this case, if a site of a corresponding nearest neighbor does not belong to the convex hull of any obstacle, the distance up to the site can be rapidly calculated. If a site of a corresponding nearest neighbor belongs to the convex hull of any obstacle, a portion in which the site is present within the corresponding convex hull takes a form of a simple polygon. The algorithm operates in a way to apply the shortest distance algorithm again by adding, to the visibility graph, a portion corresponding to a simple polygon.

[0043] Step S130 of approximating and pre-processing the obstacles and step S140 of calculating the shortest distance may be implemented as programming codes based on <Pseudo code 4> and <Pseudo code 5>.

TABLE-US-00004 <Pseudo code 4> Algorithm queryDataStructure(q, k) Input : data structures for a query DS , ... , DS  a query point q, the number k of query requests Output : a set of k points nearest to q among points of a set S=U .sup.t=S  1: produce a heap H in which the number of leaf nodes is t and a key of all elements is 0  2: from for i = 1 to t  3:   H (S ) ←getNeighbors(q, DS  1, min(log n, |S |))  4:  connect i-th leaf node of H and root node of H (S )  5: end for  6:  7: produce an empty heap H′ and insert a root node of H  8: produce an array Q of empty points  9: from for i = 1 to k 10:  find an element 1 having the smallest key in H′ and remove the smallest key from H′ 11:  Insert q into Q 12:  find a partial heap H.sub.j(S.sub.k) to which q belongs in H 13:  if q is a node having the greatest key in H.sub.j(S.sub.k) 14:   H (S ) ←getNeighbors(q, DS  min((2  − 1) log n + 1 |S |), min((2.sup.j+1 − 1) log n, |S |)) 15:   connect q and the root node of H (S ) 16:  end if 17:  insert all child nodes of q into H′ 18: end for 19: return Q indicates data missing or illegible when filed

TABLE-US-00005 <Pseudo code 5> Algorithm getNeighbors( , DS, a, b)  Input : a start point s, a data structure DS for a k-nearest neighbor query, integers a, b  Assumption : convex hulls of two arbitrary obstacles included in DS do not overlap  Output : a min heap H in which a-th to b-th nearest neighborsfrom s are stored  1: calculate a list L in which the elements of S are arranged in order of short Euc an from s  2: add a vertex s to a visibility graph DS, VG and add main lines adjacent to s  3: initialize to a set of points C= Ø that are likely to becomes a k-nearest neighbor  4: initialize a min heap H so that the min heap H includes b nodes having a ∞ value  5:  6: while (a value of a b-th element of H) ≥ L[ ], dist  7:    8:  connect a node corresponding to t in C ← C ∪ {t}, C by a pointer  9:  if t is included in a convex hull o′ ∈ DS, O′ of a specific obstacle 10:   invoke an obstacle o′ ∈ DS, O connected to o′ and a pointer 11:   calculate a simple polygon area to which t belongs in a portion corresponding to o′−o 12:   add all vertexes of the corresponding area to DS, VG as vertexes and add corresponding main lines 13:  else 14:   add a vertex t to DS, VG and add main lines adjacent to t 15  end if 16  while until Dijkstra's algorithm is terminated in DS, VG 17:   perform Dijkstra's algorithm by one step 18:     : = (a maximum distance that is now updated) 19:   if 20:     21:    break 22:   else if a distance of a node c ∈ C is updated 23:    H 24    C ← C \ 25   end if 26:  end while 27:   28: end while 29: remove the first an elements from H 30: return H indicates data missing or illegible when filed

[0044] A GIS is an integrated system capable of effectively storing and processing all types of information on a geographic space. The GIS is used in various fields and provides knowledge for an efficient geographical distribution, which may be implemented by k-nearest neighbor search. The k-nearest neighbor search is to search for k facilities near a query point, when environment information including various types of facility information and the location of the query point are given. For example, when the nearest gas stations from a current location are searched for, the nearest k gas stations are searched for.

[0045] When there is a static data structure, the same effect as that of a dynamic data structure can be achieved by dividing the static data structure into an appropriate number of smaller static data structures. In other words, even in a situation in which neighbors are changed in real time, the same results as those of a conventional technology can be achieved only by incorporating the situation into only some of the divided data structures, not all of the data structures. In such a case, it is more efficient because the spatial complexity and design time of the data structure are asymptotically the same as those of the static data structure, but a total time required for the data structure is reduced compared to the conventional technology.

[0046] Furthermore, most of conventional algorithms do not use the shortest path characteristics between obstacles. In contrast, in an embodiment of the present disclosure, obstacles are considered as a range of angles, not discrete objects, on the basis of a query point, and the shortest path characteristics are used at the same time. Accordingly, the present disclosure optimizes a search time by assigning priority to neighbors based on the calculated range of angles.

[0047] This application claims the benefit of and priority to Korean Patent Application No. 10-2021-0185237 filed on Dec. 22, 2021, and U.S. Provisional Application No. 63/294,069 filed on Dec. 27, 2021, the entirety of each of which is incorporated herein by reference for all purposes.

[0048] Since the present disclosure may be variously modified and have various forms, specific embodiments are illustrated in the drawings and described in detail in the body. However, this is not intended to limit the present disclosure to specific disclosed forms, and should be understood to include all modifications, equivalents, and substitutes included in the spirit and technical scope of the present disclosure.

[0049] All terms used in the body including technical or scientific terms, unless otherwise defined, have the same meanings as the terms generally understood by those skilled in the art in the art to which the present disclosure pertains. Terms such as terms defined in dictionaries, which are generally used, should be interpreted as having meanings identical to contextual meanings of the related art, and are not interpreted as ideal or excessively formal meanings unless they are definitely defined in the present application.