KR20170011722A - Optimal location determination method based on maximizing range sum on road network - Google Patents
Optimal location determination method based on maximizing range sum on road network Download PDFInfo
- Publication number
- KR20170011722A KR20170011722A KR1020150104872A KR20150104872A KR20170011722A KR 20170011722 A KR20170011722 A KR 20170011722A KR 1020150104872 A KR1020150104872 A KR 1020150104872A KR 20150104872 A KR20150104872 A KR 20150104872A KR 20170011722 A KR20170011722 A KR 20170011722A
- Authority
- KR
- South Korea
- Prior art keywords
- target point
- vertex
- road network
- candidate
- edge
- Prior art date
Links
Images
Classifications
-
- G—PHYSICS
- G08—SIGNALLING
- G08G—TRAFFIC CONTROL SYSTEMS
- G08G1/00—Traffic control systems for road vehicles
- G08G1/20—Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Navigation (AREA)
Abstract
Description
이하 설명하는 기술은 최대영역집계 질의에 기반한 최적 위치 결정 방법에 관한 것이다.The technique described below relates to an optimal positioning method based on a maximum area aggregation query.
모바일 컴퓨팅 장치의 보급과 함께 위치 기반 서비스 시장이 커지고 있다. 위치 기반 서비스는 기본적으로 위치 관련 질의(query)에 기반한다. 위치 관련 질의는 범위 질의, 최근접 질의 및 최대영역집계 질의 등이 있다.With the spread of mobile computing devices, the market for location-based services is growing. Location based services are basically based on location related queries. Location-related queries include range query, nearest neighbor query, and maximum region aggregate query.
이하 설명하는 기술은 도로 네트워크에서 최대영역집계 질의를 적용하여 최적 위치를 찾는 기법을 제공하고자 한다.The technique described below is to provide a technique of finding an optimal location by applying a maximum area aggregation query in a road network.
최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법은 컴퓨터 장치가 도로 네트워크를 구성하는 복수의 정점 식별자, 상기 도로 네트워크를 구성하는 복수의 에지에 대한 길이, 상기 에지에 위치하는 적어도 하나의 타겟 지점, 상기 적어도 하나의 타겟 지점에 대한 위치 정보 및 기준 거리를 획득하는 단계, 상기 컴퓨터 장치가 상기 적어도 하나의 타겟 지점 각각에 대해 상기 기준 거리를 이용하여 상기 에지 상에 상기 타겟 지점으로부터 시작하는 후보 구간을 생성하는 단계 및 상기 컴퓨터 장치가 상기 후보 구간이 가장 많이 중첩되는 영역을 목표 구간으로 결정하는 단계를 포함한다.A method for determining an optimal location in a road network based on a maximum area aggregation query includes determining a plurality of vertex identifiers constituting a road network, a length for a plurality of edges constituting the road network, at least one Acquiring positional information and a reference distance for the at least one target point, wherein the computer device starts from the target point on the edge using the reference distance for each of the at least one target point, And the computer device determines a region in which the candidate region is most overlapped as a target region.
다른 측면에서 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법은 컴퓨터 장치가 도로 네트워크를 구성하는 복수의 정점 식별자, 상기 도로 네트워크를 구성하는 복수의 에지에 대한 길이, 상기 에지에 위치하는 적어도 하나의 타겟 지점, 상기 적어도 하나의 타겟 지점에 대한 위치 정보, 상기 타겟 지점에 대한 가중치 및 기준 거리를 획득하는 단계, 상기 컴퓨터 장치가 상기 적어도 하나의 타겟 지점 각각에 대해 상기 기준 거리를 이용하여 상기 에지 상에 상기 타겟 지점으로부터 시작하는 후보 구간을 생성하는 단계 및 상기 컴퓨터 장치가 상기 후보 구간 중 가중치가 가장 높은 구간을 목표 구간으로 결정하는 단계를 포함한다. 상기 후보 구간은 상기 후보 구간에 포함되는 상기 타겟 지점의 가중치를 갖고, 복수의 후보 구간이 중첩되는 구간은 각 후보 구간의 가중치를 합산한 가중치를 갖는다.In another aspect, a method for determining an optimal location in a road network based on a maximum area aggregation query includes determining a plurality of vertex identifiers constituting a road network, a length for a plurality of edges constituting the road network, Obtaining a weight and a reference distance for the target point, the computer device using the reference distance for each of the at least one target point, the at least one target point, the at least one target point, Generating a candidate section starting from the target point on the edge, and determining, by the computer device, a section having the highest weight among the candidate sections as a target section. The candidate section has a weight of the target point included in the candidate section, and a section in which a plurality of candidate sections are overlapped has a weight which is a sum of weights of the candidate sections.
이하 설명하는 기술은 도로 네트워크에서 객체가 실제 이동 가능한 경로를 고려하여, 실질적인 최적 위치를 찾는다.The technique described below finds a practical optimal location, taking into account the actual movable path of the object in the road network.
도 1은 최대영역집계 질의의 예를 도시한다.
도 2는 도로 네트워크와 타겟 지점을 도시한 예이다.
도 3은 도로 네트워크에서 타겟 지점을 기준으로 세그먼트를 생성하는 예를 도시한다.
도 4는 타겟 지점이 위치하는 에지에서 타겟 지점과 하나의 노드 사이에 세그먼트를 생성하는 과정(100)에 대한 순서도의 예이다.
도 5는 도 2(a)의 도로 네트워크에 대해 타겟 지점 f1에 대한 세그먼트를 생성하는 과정에 대한 예이다.
도 6은 하나의 에지에 존재하는 동일한 타겟 지점에 대한 세그먼트의 예를 도시한다.
도 7은 도로 네트워크에서 에지별로 세그먼트를 병합하고, 정리한 결과를 도시한 예이다.
도 8은 도 2(a)의 도로 네트워크에 대해 최대 세그먼트를 결정한 예를 도시한다.Figure 1 shows an example of a maximum area aggregation query.
2 is an example showing a road network and a target point.
3 shows an example of generating a segment with respect to a target point in the road network.
4 is an example of a flowchart for a
5 is an example of a process of generating a segment of the target point f 1 for the road network of Figure 2 (a).
Figure 6 shows an example of a segment for the same target point present on one edge.
FIG. 7 is an example showing segments obtained by merging segments according to edges in a road network.
Fig. 8 shows an example of determining the maximum segment for the road network of Fig. 2 (a).
이하 설명하는 기술은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세하게 설명하고자 한다. 그러나, 이는 이하 설명하는 기술을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 이하 설명하는 기술의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.The following description is intended to illustrate and describe specific embodiments in the drawings, since various changes may be made and the embodiments may have various embodiments. However, it should be understood that the following description does not limit the specific embodiments, but includes all changes, equivalents, and alternatives falling within the spirit and scope of the following description.
제1, 제2, A, B 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 해당 구성요소들은 상기 용어들에 의해 한정되지는 않으며, 단지 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 이하 설명하는 기술의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의 조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.The terms first, second, A, B, etc., may be used to describe various components, but the components are not limited by the terms, but may be used to distinguish one component from another . For example, without departing from the scope of the following description, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component. And / or < / RTI > includes any combination of a plurality of related listed items or any of a plurality of related listed items.
본 명세서에서 사용되는 용어에서 단수의 표현은 문맥상 명백하게 다르게 해석되지 않는 한 복수의 표현을 포함하는 것으로 이해되어야 하고, "포함한다" 등의 용어는 설시된 특징, 개수, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함을 의미하는 것이지, 하나 또는 그 이상의 다른 특징들이나 개수, 단계 동작 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 배제하지 않는 것으로 이해되어야 한다.As used herein, the singular " include "should be understood to include a plurality of representations unless the context clearly dictates otherwise, and the terms" comprises & , Parts or combinations thereof, and does not preclude the presence or addition of one or more other features, integers, steps, components, components, or combinations thereof.
도면에 대한 상세한 설명을 하기에 앞서, 본 명세서에서의 구성부들에 대한 구분은 각 구성부가 담당하는 주기능 별로 구분한 것에 불과함을 명확히 하고자 한다. 즉, 이하에서 설명할 2개 이상의 구성부가 하나의 구성부로 합쳐지거나 또는 하나의 구성부가 보다 세분화된 기능별로 2개 이상으로 분화되어 구비될 수도 있다. 그리고 이하에서 설명할 구성부 각각은 자신이 담당하는 주기능 이외에도 다른 구성부가 담당하는 기능 중 일부 또는 전부의 기능을 추가적으로 수행할 수도 있으며, 구성부 각각이 담당하는 주기능 중 일부 기능이 다른 구성부에 의해 전담되어 수행될 수도 있음은 물론이다.Before describing the drawings in detail, it is to be clarified that the division of constituent parts in this specification is merely a division by main functions of each constituent part. That is, two or more constituent parts to be described below may be combined into one constituent part, or one constituent part may be divided into two or more functions according to functions that are more subdivided. In addition, each of the constituent units described below may additionally perform some or all of the functions of other constituent units in addition to the main functions of the constituent units themselves, and that some of the main functions, And may be carried out in a dedicated manner.
또, 방법 또는 동작 방법을 수행함에 있어서, 상기 방법을 이루는 각 과정들은 문맥상 명백하게 특정 순서를 기재하지 않은 이상 명기된 순서와 다르게 일어날 수 있다. 즉, 각 과정들은 명기된 순서와 동일하게 일어날 수도 있고 실질적으로 동시에 수행될 수도 있으며 반대의 순서대로 수행될 수도 있다.Also, in performing a method or an operation method, each of the processes constituting the method may take place differently from the stated order unless clearly specified in the context. That is, each process may occur in the same order as described, may be performed substantially concurrently, or may be performed in the opposite order.
먼저 최대영역집계 질의에 대해 간략하게 설명한다. First, the maximum region aggregation query will be briefly described.
가중된 점들과 클라이언트가 정의한 질의 사각형 r이 있을 때 최대영역집계 질의 목표는 r 안에 있는 모든 점들의 총 가중치가 가장 큰 r의 최적 위치를 구하는 것이다. 이하 r은 네트워크 반경이라고 명명한다. When there are weighted points and a query rectangle r defined by the client, the maximum region aggregation query goal is to find the optimal position of r with the largest total weight of all points in r. Here r is the network radius.
도 1은 최대영역집계 질의의 예를 도시한다. 도 1(a)는 사각형 질의의 예로 도시한다. 사각형 질의 r의 면적은 a*b이고 모든 포인터는 가중치가 모두 1로 같다고 가정한다. 도 1(b)는 도 1(a)의 사각형 질의를 사용하여 사각형 중간점의 최적 위치를 찾는 예이다. 도 1(b)에서 실선으로 테두리 친 사각형의 중간점이 r의 최적 위치이다. 그 이유는 실선으로 그려진 사각형이 가장 많은 점(3개)을 포함하였기 때문이다.Figure 1 shows an example of a maximum area aggregation query. Fig. 1 (a) shows an example of a quadrangular query. It is assumed that the area of the quadratic query r is a * b and that all pointers have a weight equal to one. Fig. 1 (b) is an example of finding an optimal position of a quadrangle midpoint using the quadrangle query of Fig. 1 (a). In Fig. 1 (b), the midpoint of the rectangle with the solid line is the optimal position of r. This is because the solid rectangles contain the most points (three).
종래 연구들은 사각형 질의 면적의 위치를 결정하면서, 사각형에 포함되는 점까지의 거리를 직선 거리로 가정하였다. 그러나 클라이언트의 움직임은 도로 네트워크상에서 일정한 길로만 이동이 가능하다. 관광 서비스 시나리오로 클라이언트인 관광객이 많은 반경 1.5km 내 많은 관광지를 포함하고 있으며 가까운 호텔을 찾으려고 하는 상황에 최대영역집계 질의를 고려할 수 있다. 그러나 종래의 최대영역집계 질의 처리 방법으로는 이 시나리오에 적용하기 어렵다. 호텔과 여러 관광지들 사이 실제 이동 거리가 유클리디안 거리와는 다르기 때문이다.Conventional studies have assumed the position of the square query area and assumed the straight line distance to the point included in the rectangle. However, the movement of the client can only be moved by a certain distance on the road network. Tourist service scenarios include many tourists within a radius of 1.5 km, where clients are tourists, and you can consider querying the maximum area count when you are trying to find a nearby hotel. However, the conventional maximum area aggregation query processing method is difficult to apply to this scenario. The actual distance traveled between hotels and other attractions is different from Euclidian streets.
도 2는 도로 네트워크와 타겟 지점을 도시한 예이다. 도로 네트워크에서 정점은 도로가 만나는 교차로와 같은 지점을 나타낸다. 타겟 지점은 전술한 관광 서비스 시나리오에서의 관광지에 해당한다. 즉, 타겟 지점은 최적 위치를 찾기 위한 기준이 된다. 도 2(a)는 도로 네트워크에서 정점(v)과 타겟 지점(f)을 도시한다. 괄호안의 좌표는 각 지점의 2차원 좌표로서 위치를 나타낸다. 타겟 지점의 가중치는 1이라고 가정한다. 예컨대, 1.5km 범위 내에서(즉 r = 1.5km) 최적인 위치를 선정하고자 하는 경우라고 가정한다. 도 2(b)는 f1, f2 및 f3에 대하여 r = 1.5km 인 최적 위치를 결정한 예에 해당한다. 도 2(b)에서 s로 표시한 구역이 f1, f2 및 f3에 대하여 조건을 만족하는 구간에 해당한다. 따라서 사용자는 도 2(b)에서 s라고 표시한 구간에서 숙박시설을 결정할 수 있다. s와 같이 사용자가 찾고자 하는 구간을 목표 구간이라고 명명한다.2 is an example showing a road network and a target point. In a road network, vertices represent points such as intersections where roads meet. The target point corresponds to a tourist spot in the tourism service scenario described above. That is, the target point is a reference for finding the optimum position. Figure 2 (a) shows the vertex (v) and the target point (f) in the road network. Coordinates in parentheses indicate positions as two-dimensional coordinates of each point. It is assumed that the weight of the target point is 1. For example, it is assumed that the optimum position is selected within a range of 1.5 km (i.e., r = 1.5 km). Fig. 2 (b) corresponds to an example of determining an optimum position r = 1.5 km for f 1 , f 2 and f 3 . In FIG. 2 (b), the zone indicated by s corresponds to a section satisfying the condition for f 1 , f 2, and f 3 . Therefore, the user can determine the accommodation in the section indicated by s in Fig. 2 (b). s is called a target section.
이하 도로 네트워크 상황을 고려한 최대영역집계 질의에 대해 구체적으로 설명하도록 한다. 이하 설명하는 기술은 복수의 타겟 지점을 고려하여 적어도 하나 이상의 목표 구간을 찾는다.Hereinafter, the maximum area aggregation query considering the road network situation will be described in detail. The technique described below finds at least one target section in consideration of a plurality of target points.
도로 네트워크는 그래프 형태의 G = (V, E) 로 나타낸다. V는 노드(node)를 의미하는 꼭지점의 집합, E는 에지(edge)의 집합이다. 도로 상에 위치하는 특정한 타겟 지점의 집합을 F라고 한다. f는 어떤 타겟 지점을 말한다(f∈F). f는 E의 선에 위치한다. 또한 f는 가중치 w(f)를 가질 수 있다.The road network is represented by the graphical form G = (V, E). V is a set of vertices representing a node, and E is a set of edges. A set of specific target points located on the road is referred to as F. f is a certain target point (fεF). f is located on the line of E. Also, f may have a weight w (f).
도로 네트워크 G에서 양(positive)의 가중치를 갖는 타겟 지점들(F)가 있다. 네트워크 반경은 r이다. p(r)은 도로 네트워크에서 지점 p로 구성된 네트워크 구간이다. 네트워크 구간 p(r)은 도로 네트워크에서 r보다 같거나 작은 크기를 갖는 점 p로 구성된 구간을 의미한다. Fp(r)은 p(r)에 포함되는 타겟 지점의 집합을 의미한다. 결국 최대영역집계(maximizing range sum) 질의는 도로 네트워크에서 아래의 수학식 1을 만족하는 모든 지점 p를 찾는 것이다.There are target points F with a positive weight in the road network G. The network radius is r. p (r) is a network segment composed of points p in the road network. The network interval p (r) means a section composed of a point p having a size equal to or smaller than r in the road network. F p (r) denotes a set of target points included in p (r). Finally, the maximizing range sum query is to find all the points p in the road
도 3은 도로 네트워크에서 타겟 지점을 기준으로 세그먼트를 생성하는 예를 도시한다. 도 3은 2개의 에지(<v1, v2>, <v2, v3>)과 두 개의 시설<f1, f2>로 구성된 단순한 도로 네트워크를 도시한다. 도 3에서 각 타겟 지점의 가중치를 1이라 두고 네트워크 반경(r)을 1이라고 가정한다. 도 3에서 회색 실선 세그먼트(segment)는 시설 f1의 네트워크 범위 f1(r)를 나타내고, 회색 점선으로 된 세그먼트는 f2 시설의 네트워크 범위 f2(r)를 나타낸다.3 shows an example of generating a segment with respect to a target point in the road network. 3 shows a simple road network consisting of two edges (<v1, v2>, <v2, v3>) and two facilities <f1, f2>. In FIG. 3, a weight of each target point is assumed to be 1, and a network radius r is assumed to be 1. In Fig. 3, a gray solid line segment represents the network range f1 (r) of the facility f1, and a gray dotted line segment represents the network range f2 (r) of the f2 facility.
간단하게 설명하면 타겟 지점을 기준으로 세그먼트를 결정하고, 최대한 많은 세그먼트가 중복되는 구간을 찾는다. 가장 많이 세그먼트가 중복되는 구간이 목표 구간에 해당한다. In short, it determines the segment based on the target point and finds the segment where as many segments as possible overlap. The segment with the most overlapping segment corresponds to the target segment.
도로 네트워크에서 모든 시설의 네트워크 범위로 나타내는 모든 세그먼트의 집합을 S하고 한다. 도로 네트워크에서 어떤 지점을 p라고 하면, S에 관하여 p를 포함하는 세그먼트는 p의 가중치와 같은 값을 갖는다. 설명의 편의를 위해 각 타겟 지점의 가중치를 1이라고 하였지만, 타겟 지점별로 가중치가 다를 수 있다. 이 경우 세그먼트가 중복되는 구간 중 가장 가중치가 높은 구간이 목표 구간이 된다. 따라서 목표 구간은 다른 말로 하면 도 3에서 표시한 것과 같이 최대 세그먼트(max segment)라고 할 수도 있다. 최대 세그먼트 M은 세그먼트 집합 S에서 가장 가중치가 큰 세그먼트에 해당한다.A set of all segments that represent the network coverage of all facilities in the road network shall be S and. Let p be a point in the road network. A segment containing p with respect to S has a value equal to the weight of p. For convenience of explanation, the weight of each target point is 1. However, the weight of each target point may be different. In this case, the segment having the highest weight among the overlapping segments is the target segment. Therefore, the target segment may be referred to as a max segment as shown in FIG. The maximum segment M corresponds to the segment having the largest weight in the segment set S.
이하 설명하는 도로 네트워크에 대한 최대영역집계 질의 방법은 크게 3가지 과정을 갖는다. 도로 네트워크에 대한 최대영역집계 질의 방법은 최종적으로 최대 세그먼트(max segment)를 찾는 것이 목적이다. 이하 설명하는 도로 네트워크에 대한 최대영역집계 질의 방법은 컴퓨터 장치에서 입력된 데이터를 바탕으로 일정한 알고리즘을 통해 수행된다.The maximum area aggregation query method for the road network described below has three processes. The maximum area aggregation query method for the road network is to finally find the maximum segment (max segment). A maximum area aggregation query method for a road network described below is performed through a predetermined algorithm based on data input from a computer device.
(1) 먼저 결정하고자 하는 도로 네트워크 상에서 타겟 지점별로 세그먼트를 생성한다. 여기서 타겟 지점은 도 1 내지 도 2에서 도시한 특정 시설에 해당한다. 타겟 지점은 전술한 바와 같이 일정한 가중치를 가질 수 있다. 다만 설명의 편의를 위해 일단 모든 타겟 지점에 대한 가중치는 1이라고 가정한다. (2) 동일한 에지에서 복수의 세그먼트가 생성될 수 있다. 하나의 에지에서 세그먼트가 중복되는지, 어떤 구간이 중복되는지를 확인하기 위해 생성한 세그먼트를 일정하게 정리 내지 가공하는 과정이 필요할 수 있다. (3) 마지막으로 정리된 세그먼트를 이용하여 최대 세그먼트를 찾는다. 이하 각 과정에 대해 설명한다.(1) First, a segment is generated for each target point on the road network to be determined. Here, the target point corresponds to the specific facility shown in Figs. The target point may have a constant weight as described above. However, for convenience of explanation, it is assumed that the weight for all target points is 1 at a time. (2) a plurality of segments may be generated at the same edge. It may be necessary to arrange or process the generated segments in order to check whether the segments are overlapped or overlapped at one edge. (3) Find the maximum segment using the last sorted segment. Each process will be described below.
컴퓨터 장치는 사전에 도로 네트워크에 대한 정보를 입력받아야 한다. 필요한 정보는 도로 네트워크를 나타내는 정점, 에지 및 에지에 위치하는 타겟 지점에 대한 위치 정보 등을 포함한다. 위치 정보를 기반으로 에지의 길이, 특정 정점에서 타겟 지점까지의 거리를 연산할 수도 있고, 사전에 길이에 대한 정보도 입력받을 수 있다.The computer device must receive information about the road network in advance. The necessary information includes vertex, edge representing the road network, and positional information on the target point located at the edge. Based on the position information, the length of the edge, the distance from the specific vertex to the target point can be calculated, and the information about the length can be inputted in advance.
(1) 세그먼트 생성(1) Create Segment
이 과정은 도로 네트워크에 있는 모든 타겟 지점에 대한 세그먼트를 생성하는 과정이다. 모든 타겟 지점 f에 대해 네트워크 구간 f(r)을 생성한다. This is the process of creating segments for all target points in the road network. Generate network interval f (r) for all target points f.
먼저 타겟 지점 f를 포함하는 에지, 시작 노드 및 종료 노드에 대한 정보를 획득하거나 생성한다. 시작 노드는 에지를 이동하는 경우 시작점이 되는 노드를 의미하고, 종료 노드는 종료점이 되는 노드를 의미한다.First, information about the edge, the start node, and the end node including the target point f is obtained or generated. The start node means a node that becomes a start point when moving an edge, and the end node means a node that becomes an end point.
타겟 지점(f)은 시작 노드(startN) 및 종료 노드(endN) 사이에 위치한다. 먼저 두 개의 노드 중 하나인 시작 노드와 타겟 지점 사이의 세그먼트 생성을 설명한다.The target point f is located between the start node startN and the end node endN. First, segment creation between the starting node and the target point, one of the two nodes, is described.
도 4는 타겟 지점이 위치하는 에지에서 타겟 지점과 하나의 노드 사이에 세그먼트를 생성하는 과정(100)에 대한 순서도의 예이다.4 is an example of a flowchart for a
먼저 컴퓨터 장치는 타겟 지점(f), 타겟 지점이 위치하는 에지에 대한 정보를 획득한다(110). 에지에 대한 정보는 에지의 길이, 에지를 구성하는 시작 노드(startN) 및 종료 노드(endN)에 대한 정보를 포함한다. 타겟 지점(f)에 대한 정보는 에지에서의 위치 정보를 포함한다. 따라서 컴퓨터 장치는 시작 노드(startN) 또는 종료 노드(endN)로부터 타겟 지점(f) 사이의 길이를 획득한다.First, the computer device obtains information about the target point f, the edge at which the target point is located (110). The information on the edge includes information on the length of the edge, the start node (startN) and the end node (endN) constituting the edge. The information about the target point f includes position information at the edge. Thus, the computing device obtains the length between the start node (startN) or the end node (endN) to the target point (f).
먼저 시작 노드를 중심으로 세그먼트 생성을 설명한다. 컴퓨터 장치는 시작 노드와 타겟 지점 사이의 거리가 r이상인지 여부를 확인한다(120). r은 최대영역집계 질의를 위해 주어진 기준 거리에 해당한다. First, segment creation is described centering on the starting node. The computer device checks whether the distance between the starting node and the target point is equal to or greater than r (120). r corresponds to the given reference distance for the maximum area aggregation query.
시작 노드(startN)와 타겟 지점(f) 사이의 거리가 네트워크 반경 r 이상인 경우(120의 Yes), 시작 노드(startN)와 타겟 지점(f) 사이에 새로운 노드(nN)를 생성한다. 타겟 지점(f)과 새로운 노드(nN) 사이의 구간을 새로운 세그먼트로 생성한다. 타겟 지점(f)과 새로운 노드(nN) 사이의 거리는 r이다. 다른 말로 하면 타겟 지점에서 시작 노드 방향으로 길이가 r인 세그먼트를 생성한다(130).A new node nN is created between the start node startN and the target point f when the distance between the start node startN and the target point f is equal to or greater than the network radius r. A segment between the target point (f) and the new node (nN) is created as a new segment. The distance between the target point f and the new node nN is r. In other words, a segment having a length r from the target point toward the starting node is generated (130).
시작 노드(startN)와 타겟 지점(f) 사이의 거리가 네트워크 반경 r 미만인 경우(120의 No), 타겟 지점(f)와 시작 노드(startN) 사이의 구간을 새로운 세그먼트로 생성한다(140). 이때 타겟 지점(f)와 시작 노드(startN) 사이의 길이를 l이라고 한다.If the distance between the start node (startN) and the target point (f) is less than the network radius r (No in 120), a segment between the target point (f) and the start node (startN) is created as a new segment (140). Here, the length between the target point f and the start node startN is denoted by l.
이후 시작 노드(startN)에서 다른 노드(neighN)에 이르는 에지가 존재하는 경우(150의 Yes), 시작 노드(startN)에서 다른 노드 방향(neighN)으로 거리가 r-l인 세그먼트를 생성한다. 만약 시작 노드(startN)에서 다른 노드(neighN)까지의 거리가 r-l보다 작은 경우, 시작 노드(startN)에서 다른 노드(neighN)까지를 하나의 세그먼트로 생성한다. 시작 노드(startN)에서 다른 노드(neighN)까지의 길이를 m이라고 한다. 이후 다른 노드(neighN)에서 또 다른 노드에 이르는 에지가 존재하는 경우, 다른 노드(neighN)에서 또 다른 노드 방향으로 길이가 r-l-m인 세그먼트를 생성한다. 정리하면 계속해서 새로운 에지가 있다면, 시작 노드(startN)부터 시작하여 전체 길이의 합이 r-l인 세그먼트를 생성하게 된다. 더 이상 주변에 새로운 노드가 없다면, 세그먼트 생성을 종료한다.Then, if there is an edge from the start node startN to another node neighN (Yes in 150), a segment with a distance r-l from the start node startN to another node direction neighN is generated. If the distance from the start node (startN) to the other node (neighN) is smaller than r-l, a segment from the start node (startN) to another node (neighN) is generated as one segment. Let m be the length from the start node (startN) to the other node (neighN). Then, if there is an edge from another node (neighN) to another node, a segment with a length of r-1-m from another node (neighN) to another node is generated. In summary, if there is a new edge continuously, the segment starting from the start node (startN) and having the sum of the total length r-l is generated. If there are no more new nodes in the vicinity, terminate segment creation.
다른 노드(neighN)가 복수 개인 경우 각각에 대해 세그먼트를 생성한다. 시작 노드(startN)에서 다른 노드(neighN)에 이르는 에지가 없는 경우(150의 No) 종료된다.If there are a plurality of other nodes (neighN), a segment is generated for each of them. If there is no edge from the start node (startN) to another node (neighN) (No in 150), the process ends.
이후 컴퓨터 장치는 종료 노드(endN)에 대해 시작 노드와 동일한 과정으로 세그먼트를 생성한다. 이 과정이 종료되면 현재 타겟 지점(f)에 대한 세그먼트 생성은 완료된다.The computer device then generates a segment for the end node (endN) in the same process as the start node. At the end of this process, segment creation for the current target point f is completed.
도 5는 도 2(a)의 도로 네트워크에 대해 타겟 지점 f1에 대한 세그먼트를 생성하는 과정에 대한 예이다. 도 5에서 r = 1.5이다. 도 5에서 세그먼트는 점선으로 표시하였다. 도 5에서 세그먼트 옆에 표시된 숫자(1 ~ 7)은 세그먼트가 생성된 순서를 의미한다. 5 is an example of a process of generating a segment of the target point f 1 for the road network of Figure 2 (a). In Fig. 5, r = 1.5. In Fig. 5, segments are indicated by dotted lines. In FIG. 5, the numbers (1 to 7) shown next to the segments indicate the order in which the segments are generated.
타겟 지점 f1이 위치하는 에지는 <v2, v3>이다. v2를 시작 노드라고 가정한다. f1에서 v2에 이르는 거리가 1이다. f1에서 v2에 이르는 거리가 r보다 작기 때문에 가장 먼저 <f1,v2> 세그먼트를 생성한다(①). 이후 v2에서 다른 노드에 이르는 에지가 있기 때문에 추가적인 세그먼트를 생성한다. <v2,v1>에서 v2로부터 시작하는 0.5 길이의 세그먼트를 생성하고(②), <v2,v4> 에서 v2로부터 시작하는 0.5 길이의 세그먼트를 생성한다(③).The edge at which the target point f 1 is located is < v 2 , v 3 >. Let v 2 be the starting node. The distance from f 1 to v 2 is one. Because the distance from f 1 to v 2 is less than r, we first generate the <f 1 , v 2 > segment (1). Since there are edges from v 2 to other nodes, an additional segment is created. generates a segment of length 0.5, starting from <v 2, v 1> v generated in a segment of length 0.5, starting from the second and (②), <v 2,
이제 종료 노드 v3 와 타겟 지점 f1사이에 세그먼트를 생성한다. f1에서 v3에 이르는 거리가 0.803이다. f1에서 v3에 이르는 거리가 r보다 작기 때문에 <f1,v3> 세그먼트를 생성한다(④). 이후 v3에서 다른 노드에 이르는 에지가 있기 때문에 추가적인 세그먼트를 생성한다. <v3,v1>에서 v3로부터 시작하는 0.697 길이의 세그먼트를 생성하고(⑤), <v3,v4> 에서 v3로부터 시작하는 0.697 길이의 세그먼트를 생성하고(⑥), <v3,v5> 에서 v3로부터 시작하는 0.697 길이의 세그먼트를 생성한다(⑦).Now we create a segment between end node v 3 and target point f 1 . The distance from f 1 to v 3 is 0.803. Since the distance from f 1 to v 3 is less than r, the <f 1 , v 3 > segment is generated (④). Since there are edges from v 3 to other nodes, we create additional segments. (6) generates a segment of 0.697 length starting from v 3 in (v 3 , v 1 ) (⑤), creates a segment of 0.697 in length starting from v 3 in (v 3 , v 4 ) 3 , v 5 > to produce a segment of 0.697 length starting from v 3 (⑦).
컴퓨터 장치는 도로 네트워크에 존재하는 나머지 타겟 지점 f2 ~ f4에 대하여도 f1과 동일하게 세그먼트를 생성한다. The computer device generates a segment for the remaining target points f 2 to f 4 existing in the road network in the same manner as f 1 .
(2) 세그먼트 정리 내지 병합(2) Organizing and merging segments
컴퓨터 장치는 도로 네트워크에 존재하는 모든 타겟 지점에 대한 세그먼트를 생성한다. 컴퓨터 장치는 세그먼트를 결정하면 세그먼트에 대한 정보를 저장 장치에 저장한다. The computer device creates segments for all target points present in the road network. When the computer device determines a segment, it stores information about the segment in the storage device.
동일한 에지에 복수의 세그먼트가 생성될 수 있다. 이 경우 컴퓨터 장치는 하나의 에지에 위치하는 세그먼트를 하나의 그룹으로 병합할 수 있다. 예컨대, <edge, (segment1, segment2,...)>와 같은 형태로 세그먼트 정보를 에지별로 정리할 수 있다. A plurality of segments can be generated on the same edge. In this case, the computer device can merge the segments located at one edge into one group. For example, segment information can be organized by edges such as <edge, (segment1, segment2, ...)>.
컴퓨터 장치는 에지 별로 세그먼트 정보를 불러온다. 하나의 에지에 동일한 타겟 지점에 대한 세그먼트가 2개 이상 존재하는 경우, 컴퓨터 장치는 동일한 타겟 지점에 대한 세그먼트를 병합할 수 있다. 병합 과정은 동일한 타겟 지점에 대한 복수의 세그먼트들에 대해서만 수행한다. The computer device loads segment information by edge. If there are two or more segments for the same target point on one edge, the computing device may merge the segments for the same target point. The merging process is performed only for a plurality of segments for the same target point.
도 6은 하나의 에지에 존재하는 동일한 타겟 지점에 대한 세그먼트의 예를 도시한다. 도 6(a) 내지 도 6(c)와 같이 세그먼트 1(Seg1)과 세그먼트 2(Seg2)가 중첩되거나 연결된 경우, 컴퓨터 장치는 해당 에지에서 세그먼트 1(Seg1)과 세그먼트 2(Seg2)를 하나의 세그먼트로 병합한다. 다만 도 6(d)와 같이 하나의 에지에 세그먼트가 두 개 존재하더라도, 두 개의 세그먼트가 일정한 간격을 갖는 경우 하나의 세그먼트로 병합할 수 없다.Figure 6 shows an example of a segment for the same target point present on one edge. When a segment 1 (Seg1) and a segment 2 (Seg2) are overlapped or connected as shown in Figs. 6 (a) to 6 (c), the computer device displays segment 1 (Seg1) and segment 2 (Seg2) Merge into segments. However, even if there are two segments at one edge as shown in FIG. 6 (d), the two segments can not be merged into one segment if they have a certain interval.
도 7은 도로 네트워크에서 에지별로 세그먼트를 병합하고, 정리한 결과를 도시한 예이다. 도 7에서 타겟 지점 f1에 대한 세그먼트는 회색 점선으로 표시하였고, 타겟 지점 f2에 대한 세그먼트는 회색 실선으로 표시하였고, 타겟 지점 f3에 대한 세그먼트는 검정색 실선으로 표시하였고, 타겟 지점 f4에 대한 세그먼트는 회색 점선으로 표시하였다. 몇 개만 예로 설명하면 <v1, v2> 에지는 타겟 지점 f1에 대한 세그먼트만 포함한다. <v2, v4> 에지는 타겟 지점 f1 및 f4에 대한 세그먼트만 포함한다. <v3, v5> 에지는 타겟 지점 f1, f2 및 타겟 지점 f3에 대한 세그먼트만 포함한다. <v4, v5> 에지는 타겟 지점 f2, f3 및 타겟 지점 f4에 대한 세그먼트만 포함한다. FIG. 7 is an example showing segments obtained by merging segments according to edges in a road network. In Figure 7 the segment of the target point, f 1 were shown in gray dotted line, a segment of the target point f 2 were shown in gray solid line, a segment of the target point f 3 was represented by a black solid line, the target point f 4 The segments are marked with gray dotted lines. By way of example only, the <v 1 , v 2 > edge contains only segments for target point f 1 . The < v 2 , v 4 > edges include only segments for target points f 1 and f 4 . The < v 3 , v 5 > edges include only segments for target points f 1 , f 2 and target point f 3 . The < v 4 , v 5 > edges include only segments for target points f 2 , f 3 and target point f 4 .
(3) 최대 세그먼트 결정(3) Determining the maximum segment
이제 컴퓨터 장치는 각 도로 네트워크에서 가장 세그먼트가 중복된 구간을 찾는다. 타겟 지점이 모두 가중치가 동일하다면, 단순하게 세그먼트가 가장 많이 중복된 구간이 목표 구간(max segment)에 해당한다. 전술한 바와 같이 타겟 지점마다 가중치가 다를 수 있다. 전술한 바와 같이 세그먼트는 해당 타겟 지점과 동일한 가중치를 갖는다고 가정한다. 이 경우 도로 네트워크에서 가장 가중치가 높은 구간을 목표 구간(max segment)로 결정한다. 목표 구간에 두 개 이상의 세그먼트가 중복되는 경우 모든 세그먼트의 가중치를 합산한 값이 해당 구간에 대한 가중치가 된다.Now the computer device finds the segment with the most overlapping segment in each road network. If all of the target points have the same weight, then the segment with the largest overlap of segments is the max segment. The weights may be different for each target point as described above. As described above, it is assumed that the segment has the same weight as the target point. In this case, the highest weighted section in the road network is determined as a max segment. If two or more segments overlap in the target segment, the sum of the weights of all segments becomes a weight for the segment.
도 8은 도 2(a)의 도로 네트워크에 대해 최대 세그먼트를 결정한 예를 도시한다. 도 8은 도 2(a)의 도로 네트워크에서 타겟 지점에 대한 세그먼트를 모두 결정한 예를 도시한다. 타겟 지점에 대해 가중치가 동일하다고 가정한다. 이 경우 목표 구간인 최대 세그먼트는 가장 세그먼트가 중복된 구간이 된다. 타겟 지점에 대한 가중치가 1이라면, 3개의 세그먼트가 중복된 구간인 d1 및 d2가 가중치 3을 갖는 최대 세그먼트가 된다. Fig. 8 shows an example of determining the maximum segment for the road network of Fig. 2 (a). Fig. 8 shows an example in which all the segments for the target point in the road network of Fig. 2 (a) are determined. Assume that the weights are the same for the target point. In this case, the maximum segment, which is the target segment, is the segment in which the segment is the most overlapped. If the weight for the target point is 1, the overlapping periods of the three segments, d 1 and d 2, are the largest segments with
예컨대, 도 8의 도로 네트워크가 관광지인 타겟 지점들과 가장 가까운 숙박시설을 찾는 문제에 관한 것이라면, 사용자는 최대 세그먼트에 위치한 숙박 시설을 찾아야 한다. For example, if the road network of Figure 8 is about the problem of finding the closest accommodation to the target locations, which are sightseeing destinations, the user should look for accommodations located in the maximum segment.
전술한 도로 네트워크에서의 최대영역집계 질의 방법은 컴퓨터 장치를 통해 수행된다. 예컨대, 사용자의 스마트폰이 도로 네트워크에 대한 정보를 수신하고, 이를 기반으로 최적 위치를 결정할 수 있다. 나아가 사용자 단말과 네트워크로 연결된 외부 서버가 도로 네트워크에 대한 정보를 수신하여 최적 위치를 결정할 수도 있다.The maximum area aggregation query method in the road network described above is performed through a computer device. For example, the smartphone of the user can receive information about the road network and determine the optimum location based on the received information. Furthermore, an external server connected to the user terminal via the network may receive the information about the road network and determine the optimal location.
본 실시예 및 본 명세서에 첨부된 도면은 전술한 기술에 포함되는 기술적 사상의 일부를 명확하게 나타내고 있는 것에 불과하며, 전술한 기술의 명세서 및 도면에 포함된 기술적 사상의 범위 내에서 당업자가 용이하게 유추할 수 있는 변형 예와 구체적인 실시예는 모두 전술한 기술의 권리범위에 포함되는 것이 자명하다고 할 것이다.It should be noted that the present embodiment and the drawings attached hereto are only a part of the technical idea included in the above-described technology, and those skilled in the art will readily understand the technical ideas included in the above- It is to be understood that both variations and specific embodiments which can be deduced are included in the scope of the above-mentioned technical scope.
Claims (12)
상기 컴퓨터 장치가 상기 적어도 하나의 타겟 지점 각각에 대해 상기 기준 거리를 이용하여 상기 에지 상에 상기 타겟 지점으로부터 시작하는 후보 구간을 생성하는 단계; 및
상기 컴퓨터 장치가 상기 후보 구간이 가장 많이 중첩되는 영역을 목표 구간으로 결정하는 단계를 포함하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.Wherein the computer device comprises a plurality of vertex identifiers constituting a road network, a length for a plurality of edges constituting the road network, at least one target point located at the edge, position information for the at least one target point, ;
The computer device generating a candidate interval starting from the target point on the edge using the reference distance for each of the at least one target point; And
And determining that the computer device has a region in which the candidate region is most overlapped as a target region based on the maximum region aggregation query.
상기 후보 구간을 생성하는 단계는
상기 타겟 지점이 위치하는 에지에서 상기 타겟 지점부터 하나의 정점까지의 거리가 상기 기준 거리 이상인 경우, 상기 타겟 지점부터 상기 하나의 정점 방향으로 상기 기준 거리의 길이를 갖는 후보 구간을 생성하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.The method according to claim 1,
The step of generating the candidate section
And a maximum area counting unit that generates a candidate interval having the length of the reference distance from the target point to the one vertex when the distance from the target point to one vertex is equal to or greater than the reference distance at an edge where the target point is located, A method for determining an optimal location in a road network based on a query.
상기 후보 구간을 생성하는 단계는
상기 타겟 지점이 위치하는 에지에서 상기 타겟 지점부터 하나의 정점까지의 거리가 상기 기준 거리 미만인 경우, 상기 타겟 지점부터 상기 하나 정점까지의 구간을 후보 구간으로 생성하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.The method according to claim 1,
The step of generating the candidate section
Wherein when a distance from the target point to one vertex at an edge where the target point is located is less than the reference distance, a section from the target point to the one vertex is created as a candidate section, A method for determining an optimal position.
상기 후보 구간을 생성하는 단계는
상기 하나의 정점에서 상기 에지가 아닌 다른 에지를 구성하는 다른 정점 방향으로 이동이 가능한 경우, 이동 경로 상에 있는 에지에 상기 다른 정점부터 시작하여 전체 상기 기준 거리에서 상기 타겟 지점부터 상기 하나 정점까지의 길이를 차감한 길이를 갖는 후보 구간을 생성하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.The method of claim 3,
The step of generating the candidate section
Wherein when the vertex is movable from one vertex to another vertex constituting an edge other than the edge, an edge on the movement path starts from the other vertex and extends from the target point to the one vertex A method for determining an optimal location in a road network based on a maximum area aggregation query that generates a candidate section having a length less than the length.
상기 다른 정점 방향으로 이동하면서 더 이상 이동할 수 있는 경로가 없고, 상기 다른 정점부터 시작하여 생성한 후보 구간이 상기 차감한 길이보다 작은 경우 더 이상 후보 구간을 생성하지 않고 종료하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.5. The method of claim 4,
Based on a maximum area aggregation query in which there is no path that can move further while moving in the other vertex direction and ends without generating a candidate section when the candidate section generated from the other vertex is smaller than the subtracted length A method for determining an optimal location in a road network.
상기 컴퓨터 장치가 상기 도로 네트워크에 위치하는 모든 타겟 지점에 대한 후보 구간을 생성한 후 상기 도로 네트워크를 구성하는 에지별로 하나의 에지에 동일한 타겟 지점에 대한 복수의 후보 구간이 존재하고, 상기 복수의 후보 구간이 단절없이 연결가능한 경우 하나의 후보 구간으로 병합하는 단계를 더 포함하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.The method according to claim 1,
Wherein the computer apparatus generates a candidate section for all the target points located in the road network, there is a plurality of candidate sections for the same target point on one edge for each of the edges constituting the road network, And merging the segments into one candidate interval if the segments can be connected without a disconnection.
상기 컴퓨터 장치가 상기 적어도 하나의 타겟 지점 각각에 대해 상기 기준 거리를 이용하여 상기 에지 상에 상기 타겟 지점으로부터 시작하는 후보 구간을 생성하는 단계; 및
상기 컴퓨터 장치가 상기 후보 구간 중 가중치가 가장 높은 구간을 목표 구간으로 결정하는 단계를 포함하되,
상기 후보 구간은 상기 후보 구간에 포함되는 상기 타겟 지점의 가중치를 갖고, 복수의 후보 구간이 중첩되는 구간은 각 후보 구간의 가중치를 합산한 가중치를 갖는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.A computer apparatus comprising: a plurality of vertex identifiers constituting a road network; a length for a plurality of edges constituting the road network; at least one target point located at the edge; position information for the at least one target point; Obtaining a weight and a reference distance for the point;
The computer device generating a candidate interval starting from the target point on the edge using the reference distance for each of the at least one target point; And
Wherein the computer device determines the highest weighted section of the candidate section as the target section,
Wherein the candidate section has a weight of the target point included in the candidate section and a section in which a plurality of candidate sections are overlapped includes an optimum position in a road network based on a maximum area aggregation query having a weight obtained by summing weights of the candidate sections Method for determining.
상기 후보 구간을 생성하는 단계는
상기 타겟 지점이 위치하는 에지에서 상기 타겟 지점부터 하나의 정점까지의 거리가 상기 기준 거리 이상인 경우, 상기 타겟 지점부터 상기 하나의 정점 방향으로 상기 기준 거리의 길이를 갖는 후보 구간을 생성하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.8. The method of claim 7,
The step of generating the candidate section
And a maximum area counting unit that generates a candidate interval having the length of the reference distance from the target point to the one vertex when the distance from the target point to one vertex is equal to or greater than the reference distance at an edge where the target point is located, A method for determining an optimal location in a road network based on a query.
상기 후보 구간을 생성하는 단계는
상기 타겟 지점이 위치하는 에지에서 상기 타겟 지점부터 하나의 정점까지의 거리가 상기 기준 거리 미만인 경우, 상기 타겟 지점부터 상기 하나 정점까지의 구간을 후보 구간으로 생성하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.8. The method of claim 7,
The step of generating the candidate section
Wherein when a distance from the target point to one vertex at an edge where the target point is located is less than the reference distance, a section from the target point to the one vertex is created as a candidate section, A method for determining an optimal position.
상기 후보 구간을 생성하는 단계는
상기 하나의 정점에서 상기 에지가 아닌 다른 에지를 구성하는 다른 정점 방향으로 이동이 가능한 경우, 이동 경로 상에 있는 에지에 상기 다른 정점부터 시작하여 전체 상기 기준 거리에서 상기 타겟 지점부터 상기 하나 정점까지의 길이를 차감한 길이를 갖는 후보 구간을 생성하는10. The method of claim 9,
The step of generating the candidate section
Wherein when the vertex is movable from one vertex to another vertex constituting an edge other than the edge, an edge on the movement path starts from the other vertex and extends from the target point to the one vertex A candidate section having a length obtained by subtracting the length is generated
상기 다른 정점 방향으로 이동하면서 더 이상 이동할 수 있는 경로가 없고, 상기 다른 정점부터 시작하여 생성한 후보 구간이 상기 차감한 길이보다 작은 경우 더 이상 후보 구간을 생성하지 않고 종료하는11. The method of claim 10,
If there is no path that can be moved while moving in the other vertex direction and the candidate section generated starting from the other vertex is smaller than the subtracted length,
상기 컴퓨터 장치가 상기 도로 네트워크에 위치하는 모든 타겟 지점에 대한 후보 구간을 생성한 후 상기 도로 네트워크를 구성하는 에지별로 하나의 에지에 동일한 타겟 지점에 대한 복수의 후보 구간이 존재하고, 상기 복수의 후보 구간이 단절없이 연결가능한 경우 하나의 후보 구간으로 병합하는 단계를 더 포함하는 최대영역집계 질의에 기반한 도로 네트워크에서 최적 위치를 결정하기 위한 방법.8. The method of claim 7,
Wherein the computer apparatus generates a candidate section for all the target points located in the road network, there is a plurality of candidate sections for the same target point on one edge for each of the edges constituting the road network, And merging the segments into one candidate interval if the segments can be connected without a disconnection.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020150104872A KR101707742B1 (en) | 2015-07-24 | 2015-07-24 | Optimal location determination method based on maximizing range sum on road network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020150104872A KR101707742B1 (en) | 2015-07-24 | 2015-07-24 | Optimal location determination method based on maximizing range sum on road network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20170011722A true KR20170011722A (en) | 2017-02-02 |
| KR101707742B1 KR101707742B1 (en) | 2017-02-17 |
Family
ID=58154177
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020150104872A KR101707742B1 (en) | 2015-07-24 | 2015-07-24 | Optimal location determination method based on maximizing range sum on road network |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR101707742B1 (en) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20190055432A (en) * | 2017-11-15 | 2019-05-23 | 김완중 | Apparatus of job recruiting for foreigner and method of the same |
| CN111133785A (en) * | 2017-09-27 | 2020-05-08 | 三星电子株式会社 | Analysis method and apparatus for network design in wireless communication system |
| CN111199301A (en) * | 2018-11-16 | 2020-05-26 | 顺丰科技有限公司 | Method, device and equipment for selecting distributed centers and storage medium |
| CN113393343A (en) * | 2020-03-13 | 2021-09-14 | 百度在线网络技术（北京）有限公司 | Scenic spot explanation method and device, electronic equipment and medium |
| CN114459494A (en) * | 2021-12-31 | 2022-05-10 | 北京百度网讯科技有限公司 | Reachable area acquisition method and device, electronic equipment and storage medium |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108667926B (en) * | 2018-05-07 | 2021-01-01 | 浙江工业大学 | Real-time privacy security margin approximate query method |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20070046384A (en) * | 2005-10-31 | 2007-05-03 | 한국과학기술원 | Method for finding nearest neighbors on a path |
| KR20080113953A (en) * | 2007-06-26 | 2008-12-31 | 전북대학교산학협력단 | Method and system for finding nearest neighbors based on vboronoi diagram |
| KR20140028935A (en) * | 2012-08-31 | 2014-03-10 | 전북대학교산학협력단 | K-nearest neighbour query processing method and system |
-
2015
- 2015-07-24 KR KR1020150104872A patent/KR101707742B1/en active IP Right Grant
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20070046384A (en) * | 2005-10-31 | 2007-05-03 | 한국과학기술원 | Method for finding nearest neighbors on a path |
| KR20080113953A (en) * | 2007-06-26 | 2008-12-31 | 전북대학교산학협력단 | Method and system for finding nearest neighbors based on vboronoi diagram |
| KR20140028935A (en) * | 2012-08-31 | 2014-03-10 | 전북대학교산학협력단 | K-nearest neighbour query processing method and system |
Non-Patent Citations (2)
| Title |
|---|
| D.W. Choi, C. W. Chung, and Y. Tao, "A scalable algorithm for maximizing range sum in spatial databases," Proceedings of the VLDB Endowment, vol. 5, no. 11, pp. 1088-1099, 2012. |
| 선휘준. 객체의 순환적 위치속성을 고려한 최대근접질의의 처리방법. 한국공간정보정보시스템학회논문지 제11권 제2호, 2009.06., pp.85-88. * |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111133785A (en) * | 2017-09-27 | 2020-05-08 | 三星电子株式会社 | Analysis method and apparatus for network design in wireless communication system |
| CN111133785B (en) * | 2017-09-27 | 2023-09-26 | 三星电子株式会社 | Analysis method and device for network design in wireless communication system |
| KR20190055432A (en) * | 2017-11-15 | 2019-05-23 | 김완중 | Apparatus of job recruiting for foreigner and method of the same |
| CN111199301A (en) * | 2018-11-16 | 2020-05-26 | 顺丰科技有限公司 | Method, device and equipment for selecting distributed centers and storage medium |
| CN111199301B (en) * | 2018-11-16 | 2024-02-27 | 顺丰科技有限公司 | Method, device, equipment and storage medium for selecting distributed center |
| CN113393343A (en) * | 2020-03-13 | 2021-09-14 | 百度在线网络技术（北京）有限公司 | Scenic spot explanation method and device, electronic equipment and medium |
| CN113393343B (en) * | 2020-03-13 | 2024-04-26 | 百度在线网络技术（北京）有限公司 | Scenic spot explaining method and device, electronic equipment and medium |
| CN114459494A (en) * | 2021-12-31 | 2022-05-10 | 北京百度网讯科技有限公司 | Reachable area acquisition method and device, electronic equipment and storage medium |
| CN114459494B (en) * | 2021-12-31 | 2024-03-26 | 北京百度网讯科技有限公司 | Method and device for acquiring reachable area, electronic equipment and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| KR101707742B1 (en) | 2017-02-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR101707742B1 (en) | Optimal location determination method based on maximizing range sum on road network | |
| US10169403B2 (en) | Geographic space management | |
| US9857196B2 (en) | Geographic space management | |
| US9792288B2 (en) | Geographic space management | |
| US10119826B2 (en) | System and method for accelerating route search | |
| US9778048B2 (en) | Method and apparatus for determining reachable area based on road network | |
| KR20190086573A (en) | A graphical user interface that displays commonly categorized entities | |
| US9696174B2 (en) | System and method for providing surrounding area search result | |
| US20140358603A1 (en) | Iterative public transit scoring | |
| US20130325553A1 (en) | Apparatus, system and method for generating and converting sales opportunities | |
| US20130166204A1 (en) | Generating Travel Time Data | |
| JP2016048238A (en) | Navigation system, navigation method, and program | |
| CN104636457A (en) | Method and device for location search cognition | |
| US20100036608A1 (en) | Geoboundaries using rectangular fencing and coupling of gps/lbs systems | |
| CN110087185A (en) | Commercial circle fence generation method, device, equipment and computer readable storage medium | |
| US9212929B2 (en) | Routing service for computation of a cross-street associated with a geographic location | |
| CN108121725A (en) | A kind of searching method and device | |
| US10694335B2 (en) | Location based services using location and motion information | |
| CN108898862A (en) | The determination method, apparatus and electronic equipment of traffic light intersection | |
| JP2022068292A (en) | Public traffic route determination method and device | |
| US20150277719A1 (en) | System and method for providing simplified path and points of interest user interfaces | |
| KR102136213B1 (en) | Method and system for associating maps having different attribute for provding different services | |
| US20220381574A1 (en) | Multipath generation method, apparatus, device and storage medium | |
| KR102029171B1 (en) | Map display system and method using landmark and direction of that | |
| JP6168844B2 (en) | Information processing apparatus, information processing method, and program |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| E902 | Notification of reason for refusal | ||
| E701 | Decision to grant or registration of patent right | ||
| GRNT | Written decision to grant | ||
| FPAY | Annual fee payment |
Payment date: 20200203 Year of fee payment: 4 |