KR102185334B1 - PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS - Google Patents
PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS Download PDFInfo
- Publication number
- KR102185334B1 KR102185334B1 KR1020190002841A KR20190002841A KR102185334B1 KR 102185334 B1 KR102185334 B1 KR 102185334B1 KR 1020190002841 A KR1020190002841 A KR 1020190002841A KR 20190002841 A KR20190002841 A KR 20190002841A KR 102185334 B1 KR102185334 B1 KR 102185334B1
- Authority
- KR
- South Korea
- Prior art keywords
- data
- distance
- join query
- segment
- node
- Prior art date
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/907—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F16/909—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using geographical or spatial information, e.g. location
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/95—Retrieval from the web
- G06F16/953—Querying, e.g. by the use of web search engines
- G06F16/9537—Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computational Linguistics (AREA)
- Software Systems (AREA)
- Library & Information Science (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치가 개시된다. 상기 장치는, 클라이언트 단말로부터 적어도 하나 이상의 객체에 대한 ε-거리 조인 질의 요청을 수신하는 수신부; 상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 연산하는 질의 결과 연산부; 및 상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 상기 단말로 전송하는 전송부; 를 포함하고 상기 질의 결과 연산부는 제1데이터 집합 R에 포함된 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 집합 S에 포함된 제2데이터 객체들을 제2데이터 세그먼트로 정의하고, 상기 제1데이터 세그먼트 내에 포함된 2개의 제1데이터 객체에 대해 ε-거리 조인 질의를 수행하고, 상기 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 ε-거리 조인 질의와 다른 방법으로 일정 거리 ε 안에 위치하는 객체를 도출할 수 있다. An apparatus for processing ε-distance join queries on a road network is disclosed. The apparatus may include: a receiver configured to receive an ε-distance join query request for at least one object from a client terminal; In response to the request, a query result calculator for calculating an ε-distance join query processing result based on the location of the terminal; And a transmission unit for transmitting a result of processing an ε-distance join query based on the location of the terminal to the terminal in response to the request. The query result operator defines first data objects included in the first data set R as a first data segment, and defines second data objects included in the second data set S as a second data segment, Performs an ε-distance join query for the two first data objects included in the first data segment, and schedules a schedule differently from the ε-distance join query for the remaining first data objects included in the first data segment. Objects located within the distance ε can be derived.
Description
본 발명은 도로 네트워크에서 ε-거리 조인 질의를 처리하는 방법에 관한 발명이다. 보다 구체적으로는, 도로 네트워크에서 ε-거리 조인 질의 처리 시간을 줄일 수 있는 방법에 관한 발명이다.The present invention relates to a method of processing an ε-distance join query in a road network. More specifically, the present invention relates to a method for reducing the processing time of an ε-distance join query in a road network.
이동 통신망, GPS 등과 같은 위치 탐색 및 서비스 기술이 발전함에 따라, 최근에는 이동 객체의 위치 기반 서비스를 지원하는 응용 분야에 대한 관심이 높아지고 있다.With the development of location search and service technologies such as mobile communication networks and GPS, in recent years, interest in an application field supporting a location-based service of a moving object is increasing.
도로 네트워크 정보, 이동 객체의 정보, 정적 객체 정보 등이 저장된 데이터베이스를 도로 네트워크 데이터베이스(road network databases)라 하며, 도로 네트워크 데이터베이스에서 도로 네트워크는 방향성을 가진 그래프로 모델링 된다. 하나의 도로 세그먼트(road segment)는 그래프의 간선에 해당되며, 서로 다른 두 도로 세그먼트가 만나는 지점이 그래프의 노드에 해당된다. 또한, 도로 네트워크 위에 정류소, 학교, 호텔 등과 같은 시설물들은 정적 객체로 모델링 되며, 자동차, 사람과 같은 이동성을 가지고 있는 객체는 이동 객체로 모델링 된다.Databases in which road network information, moving object information, and static object information are stored are called road network databases, and in the road network database, the road network is modeled as a graph with directionality. One road segment corresponds to the edge of the graph, and the point where two different road segments meet corresponds to the node of the graph. In addition, facilities such as stops, schools, and hotels on the road network are modeled as static objects, and objects with mobility such as cars and people are modeled as moving objects.
ε-거리 조인 질의 알고리즘은, 2개의 집합 R과 S과 주어져 있을 때, R과 S의 ε-거리 조인 질의는 집합 R에 있는 각각의 객체 r에 대하여, r로부터 일정한 거리 ε안에 도달할 수 있는 객체를 집합 S에 있는 원소들로부터 찾는 알고리즘이다. 기존 방법들은 유클리디언 거리를 사용하여 일정한 거리 ε안에 객체를 검색하는 방법을 사용하였다. 그러나 이러한 방법은 도로 네트워크에서는 사용될 수 없는 문제점이 있었다. 또한, 동적인 도로망 네트워크에서는 두 지점 사이의 거리가 도로 상황에 따라 수시로 변하기 때문에, 움직이는 객체 사이에서의 정확한 거리를 실시간으로 반영하기에 어려운 문제점이 존재하였다.The ε-distance join query algorithm, given the two sets R and S, the ε-distance join query of R and S can reach a certain distance ε from r for each object r in the set R. It is an algorithm that finds an object from the elements in set S. Existing methods used the Euclidean distance to search for an object within a certain distance ε. However, this method has a problem that cannot be used in a road network. In addition, in a dynamic road network network, since the distance between two points changes from time to time according to road conditions, it is difficult to reflect the exact distance between moving objects in real time.
본 발명에서는, 도로 네트워크 상에서 실행되는 ε-거리 조인 질의를 효율적으로 처리하고자 한다.In the present invention, an ε-distance join query executed on a road network is to be efficiently processed.
또한 본 발명에서는, 도로 네트워크 상에서 실행되는 ε-거리 조인 질의의 처리 시간을 감소시키고자 한다.In addition, in the present invention, it is intended to reduce the processing time of an ε-distance join query executed on a road network.
ε-거리 조인 질의 처리 방법이 개시된다. A method for processing an ε-distance join query is disclosed.
본 발명의 일 예에 의하면, 도로 네트워크 상의 제1데이터 집합 R, 제2데이터 집합 S 중 하나의 데이터 집합에 포함된 객체로부터 일정 거리 ε 안에 위치하는 객체를 다른 데이터 집합에 있는 객체에서 선택하는 ε-거리 조인 질의 처리 방법은, 제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 또는 제2데이터 세그먼트의 집합으로 정의하는 단계; 상기 정의된 제1데이터 세그먼트 내에 포함된 일부의 제1데이터 객체들에 대해 ε-거리 조인 질의를 수행하는 단계; 상기 정의된 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 ε-거리 조인 질의와 다른 방법으로 일정 거리 ε 안에 위치하는 객체를 도출하는 단계;를 포함할 수 있다. According to an example of the present invention, an object located within a predetermined distance ε from an object included in one of the first data set R and the second data set S on the road network is selected from objects in another data set. -The distance join query processing method includes the first data objects included in the first data set R or the second data objects included in the second data set S, respectively, as a set of first data segments or a set of second data segments. Defining; Performing an ε-distance join query for some of the first data objects included in the defined first data segment; And deriving an object located within a predetermined distance ε by a method different from the ε-distance join query for the remaining first data objects included in the defined first data segment.
제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 또는 제2데이터 세그먼트의 집합으로 정의하는 단계는, 상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 단계; 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제1데이터 객체들을 잇는 시퀀스를 제1데이터 세그먼트로 정의하는 단계; 및 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들을 잇는 시퀀스를 제2데이터 세그먼트로 정의하는 단계;를 포함할 수 있다.Defining the first data objects included in the first data set R or the second data objects included in the second data set S as a set of first data segments or a set of second data segments, respectively, comprises: the road network Determining the number of road segments intersecting based on the node on the image; Defining, as a first data segment, a sequence of first data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node; And defining, as a second data segment, a sequence of second data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node as a second data segment. .
상기 제1데이터 세그먼트에 포함되는 제1데이터 객체의 개수가 1개 혹은 2개일 경우, 각각의 제1데이터 객체에 대한 ε-거리 조인 질의 처리를 수행할 수 있다.When the number of first data objects included in the first data segment is one or two, ε-distance join query processing for each first data object may be performed.
상기 제1데이터 세그먼트에 포함되는 제1데이터 객체의 개수가 3개 이상일 경우, 상기 제1데이터 세그먼트의 양 끝단에 위치하는 2개의 제1데이터 객체에 대한 ε-거리 조인 질의 처리를 수행하는 단계; 및 상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 제1데이터 세그먼트의 내부에 포함된 나머지 제1데이터 객체들에 대해 거리 계산을 수행하는 단계; 를 포함할 수 있다.If the number of first data objects included in the first data segment is three or more, performing an ε-distance join query processing for two first data objects located at both ends of the first data segment; And performing distance calculation on the remaining first data objects included in the first data segment excluding the first data objects located at both ends of the first data segment. It may include.
상기 거리 계산을 수행하는 단계는, 상기 제1데이터 세그먼트 내부에 포함된 제2데이터 객체들을 추출하는 단계; 상기 제1데이터 세그먼트의 양 끝단에 위치하는 2개의 제1데이터 객체들에 대한 ε-거리 조인 질의 처리로 도출된 거리 ε 이내의 제2데이터 객체들을 추출하는 단계; 상기 추출된 제2데이터 객체들의 집합을 정의하는 단계; 상기 내부에 포함된 나머지 제1데이터 객체들에 대해, 상기 정의된 제2데이터 객체들의 집합에 포함된 제2데이터 객체들을 대상으로 거리를 측정하여 상기 내부에 포함된 나머지 제1데이터 객체들과 거리 ε 이내에 위치하는 제2데이터 객체를 추출하는 단계;를 포함할 수 있다.The performing of the distance calculation may include extracting second data objects included in the first data segment; Extracting second data objects within a distance ε derived by processing an ε-distance join query for two first data objects located at both ends of the first data segment; Defining a set of the extracted second data objects; With respect to the remaining first data objects included in the interior, a distance is measured with respect to the second data objects included in the defined set of second data objects, and a distance from the remaining first data objects included in the interior It may include; extracting the second data object located within ε.
본 발명의 다른 일 예에 따르면, 도로 네트워크 상의 제1데이터 집합 R, 제2데이터 집합 S 중 하나의 데이터 집합에 포함된 객체로부터 일정 거리 ε 안에 위치하는 객체를 다른 데이터 집합에 있는 객체에서 선택하는 ε-거리 조인 질의 처리 방법으로써, 제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 및 제2데이터 세그먼트의 집합으로 정의하는 단계; 상기 도로 네트워크 상의 임의의 한 노드에 근접한 제1데이터 세그먼트들을 추출하는 단계; 제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 및 제2데이터 세그먼트의 집합으로 정의하는 단계는, 상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 단계; 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제1데이터 객체들을 잇는 시퀀스를 제1데이터 세그먼트로 정의하는 단계; 및 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들을 잇는 시퀀스를 제2데이터 세그먼트로 정의하는 단계;를 포함하고, 상기 노드에 근접한 제1데이터 세그먼트의 개수가 2개 이상일 경우 상기 노드를 기준으로 ε-거리 조인 질의 처리를 수행하는 단계;를 포함할 수 있다.According to another example of the present invention, an object located within a certain distance ε from an object included in one of the first data set R and the second data set S on the road network is selected from objects in another data set. As an ε-distance join query processing method, the first data objects included in the first data set R or the second data objects included in the second data set S are respectively a set of first data segments and a set of second data segments. Defining as; Extracting first data segments adjacent to any one node on the road network; Defining the first data objects included in the first data set R or the second data objects included in the second data set S as a set of first data segments and a set of second data segments, respectively, comprises: Determining the number of road segments intersecting based on the node on the image; Defining, as a first data segment, a sequence of first data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node; And defining, as a second data segment, a sequence of second data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node, as a second data segment. If the number of the first data segments adjacent to the node is two or more, performing ε-distance join query processing based on the node.
상기 임의의 한 노드는 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 3개 이상인 노드일 수 있다.The arbitrary node may be a node in which the number of road segments intersecting with respect to the node is 3 or more.
상기 임의의 한 노드에 근접한 제1데이터 세그먼트에 대한 ε-거리 조인 질의 처리 방법은, 상기 노드를 기준으로 ε-거리 조인 질의 처리를 수행하여 도출된 제2데이터 객체와, 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들의 집합을 도출하여, 상기 도로 세그먼트 상에 포함되는 제1데이터 세그먼트 내의 제1데이터 객체와 상기 제2데이터 객체들의 집합에 포함된 객체들과의 거리를 계산하여 거리 ε 내에 위치하는 제2데이터 객체를 추출할 수 있다.The ε-distance join query processing method for a first data segment close to one node is a second data object derived by performing an ε-distance join query processing based on the node, and the intersection based on the node. By deriving a set of second data objects included on a road segment connected by nodes having one or three or more road segments, the first data object and the first data object in the first data segment included on the road segment are derived. The second data object located within the distance ε may be extracted by calculating the distance to the objects included in the set of 2 data objects.
상기 제1데이터 세그먼트의 개수는, 제2데이터 세그먼트의 개수보다 적을 수 있다.The number of first data segments may be smaller than the number of second data segments.
상기 ε-거리 조인 질의 처리 방법을 실행하기 위한 프로그램이 기록되어 있는 것을 특징으로 하는 컴퓨터에서 판독 가능한 기록 매체가 제공될 수 있다.A computer-readable recording medium may be provided, wherein a program for executing the ?-distance join query processing method is recorded.
본 발명의 다른 측면에 따르면, 클라이언트 단말로부터 적어도 하나 이상의 객체에 대한 ε-거리 조인 질의 요청을 수신하는 수신부; 상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 연산하는 질의 결과 연산부; 및 상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 상기 단말로 전송하는 전송부; 를 포함하고 상기 질의 결과 연산부는 제1데이터 집합 R에 포함된 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 집합 S에 포함된 제2데이터 객체들을 제2데이터 세그먼트로 정의하고, 상기 제1데이터 세그먼트 내에 포함된 2개의 제1데이터 객체에 대해 ε-거리 조인 질의를 수행하고, 상기 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 ε-거리 조인 질의와 다른 방법으로 일정 거리 ε 안에 위치하는 객체를 도출하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치가 제공될 수 있다. According to another aspect of the present invention, there is provided a receiver for receiving an ε-distance join query request for at least one object from a client terminal; In response to the request, a query result calculator for calculating an ε-distance join query processing result based on the location of the terminal; And a transmission unit for transmitting a result of processing an ε-distance join query based on the location of the terminal to the terminal in response to the request. The query result operator defines first data objects included in the first data set R as a first data segment, and defines second data objects included in the second data set S as a second data segment, Performs an ε-distance join query for the two first data objects included in the first data segment, and schedules a schedule differently from the ε-distance join query for the remaining first data objects included in the first data segment. An apparatus for processing an ε-distance join query on a road network that derives an object located within a distance ε may be provided.
상기 질의 결과 연산부는, 상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 노드 결정 모듈; 상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체 및 제2데이터 객체를 검색하는 데이터 객체 검색 모듈; 상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 객체들은 제2데이터 세그먼트로 정의하는 그룹화 모듈; 상기 그룹화 모듈에서 생성된 제1데이터 세그먼트에 대해 ε-거리 조인 질의 처리를 수행하는 질의 결과 처리 모듈;을 포함할 수 있다. The query result calculating unit may include a node determination module for determining the number of road segments crossing the node on the road network; A data object search module for searching for a first data object and a second data object located on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node determined in the node determination module; First data objects located on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node determined in the node determination module are defined as a first data segment, and the second data objects are A grouping module defining a second data segment; And a query result processing module that performs ε-distance join query processing on the first data segment generated by the grouping module.
상기 질의 결과 처리 모듈은,The query result processing module,
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체에 대한 연산을 진행하는 제1 ε-거리 조인 질의 처리 모듈; 상기 제1 ε-거리 조인 질의 처리 모듈의 처리 결과에 따른 거리 ε 이내에 위치하는 제2데이터 객체들을 저장하는 제1 저장 모듈; 및 상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체에 대해 거리 계산을 수행하는 거리 계산 모듈;을 포함할 수 있다. A first ε-distance join query processing module that performs an operation on a first data object located at both ends of the first data segment; A first storage module for storing second data objects located within a distance ε according to a processing result of the first ε-distance join query processing module; And a distance calculation module that calculates a distance for a first data object included therein excluding a first data object positioned at both ends of the first data segment.
제1데이터 세그먼트에 포함된 제2데이터 객체들을 저장하는 제2 저장 모듈;을 더 포함할 수 있다. It may further include a second storage module for storing second data objects included in the first data segment.
상기 거리 계산 모듈;은The distance calculation module;
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체에 대해 상기 제1 저장 모듈 및 제2 저장 모듈에 저장된 제2데이터 객체들과의 거리를 계산할 수 있다. The distance between the first data objects stored in the first storage module and the second storage module can be calculated for the first data objects included inside excluding the first data objects located at both ends of the first data segment. have.
상기 질의 결과 처리 모듈은, 상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 3개 이상인 노드를 기준으로 인접하는 제1데이터 세그먼트의 개수가 2개 이상인 경우, 해당 노드에 대해 ε-거리 조인 질의를 수행하고, 그 결과로 나타나는 제2데이터 객체와, 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들과 제1데이터 객체와의 거리를 계산하여 거리 ε 이내에 위치하는 데이터 객체를 추출하는 제2 ε-거리 조인 질의 처리 모듈;을 더 포함할 수 있다. The query result processing module, when the number of adjacent first data segments is 2 or more based on a node whose number of road segments crossing based on the node determined in the node determination module is 3 or more, ε for the corresponding node. -A distance join query is executed, and the resultant second data object and second data objects included on the road segment connected by nodes with one or three or more road segments crossing the node And a second ε-distance join query processing module for extracting a data object located within the distance ε by calculating a distance between the and the first data object.
본 발명에서는, 도로 네트워크 상에서 실행되는 ε-거리 조인 질의를 효율적으로 처리할 수 있다.In the present invention, it is possible to efficiently process an ε-distance join query executed on a road network.
또한 본 발명에서는, 도로 네트워크 상에서 실행되는 ε-거리 조인 질의의 처리 시간을 감소시킬 수 있다. In addition, in the present invention, it is possible to reduce the processing time of an ε-distance join query executed on a road network.
본 발명에서는 두 지점을 연결하는 최단 경로 거리를 사용하고, 동적인 도로망을 고려하기 때문에, 실시간으로 변하는 교통 상황을 반영할 수 있다.In the present invention, since the shortest route distance connecting two points is used and a dynamic road network is considered, traffic conditions that change in real time can be reflected.
도 1은 도로 네트워크의 일 예를 나타내는 도면이다.
도 2는 본 발명에 따른 ε-거리 조인 질의 처리 장치의 주요 구성을 나타낸 블록도이다.
도 3은 본 발명에 따른 ε-거리 조인 질의 처리 장치가 포함하는 질의 결과 연산부의 주요 구성을 나타낸 블록도이다.
도 4는 본 발명에 따른 ε-거리 조인 질의 처리 장치가 포함하는 질의 결과 처리 모듈의 주요 구성을 나타낸 블록도이다.
도 5는 도로 네트워크 상에서 ε-거리 조인 질의 처리를 설명하기 위해 예시로 제시된 도로 네트워크이다.
도 6(a) 및 도 6(b)는 도 5에서 제1데이터 세그먼트와 제2데이터 세그먼트를 정의하는 것을 설명하기 위한 도면이다.
도 7 내지 도 8은 본 발명의 일 실시예에 필요한 전제를 증명하는 것을 설명하기 위한 도면이다.
도 9는 본 발명의 일 실시예에 있어서 거리를 계산하는 것을 설명하기 위한 도면이다.
도 10 내지 도 11은 본 발명의 다른 실시예에 따른 e-거리 조인 질의를 설명하기 위한 도면이다.
도 12 내지 도 14는 기존의 e-거리 조인 질의 처리 방법 및 본 발명에 따른 e-거리 조인 질의 처리 방법을 사용했을 때의 처리 결과를 나타내는 그래프들이다. 1 is a diagram illustrating an example of a road network.
2 is a block diagram showing the main configuration of an ε-distance join query processing apparatus according to the present invention.
3 is a block diagram showing a main configuration of a query result operation unit included in the ε-distance join query processing apparatus according to the present invention.
4 is a block diagram showing a main configuration of a query result processing module included in the ε-distance join query processing apparatus according to the present invention.
5 is a road network presented as an example to explain processing of an ε-distance join query on a road network.
6(a) and 6(b) are diagrams for explaining defining the first data segment and the second data segment in FIG. 5.
7 to 8 are diagrams for explaining proving a premise necessary for an embodiment of the present invention.
9 is a diagram for explaining calculating a distance according to an embodiment of the present invention.
10 to 11 are diagrams for explaining an e-distance join query according to another embodiment of the present invention.
12 to 14 are graphs showing processing results when the existing e-distance join query processing method and the e-distance join query processing method according to the present invention are used.
아래에서는 첨부한 도면을 참고로 하여 본 발명의 실시 예에 대하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시 예에 한정되지 않는다. 또한, 본 발명의 바람직한 실시예를 상세하게 설명함에 있어, 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략한다. 또한, 유사한 기능 및 작용을 하는 부분에 대해서는 도면 전체에 걸쳐 동일한 부호를 사용한다.Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those of ordinary skill in the art may easily implement the present invention. However, the present invention may be implemented in various forms and is not limited to the embodiments described herein. In addition, in describing a preferred embodiment of the present invention in detail, when it is determined that a detailed description of a related known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted. In addition, the same reference numerals are used throughout the drawings for portions having similar functions and functions.
어떤 구성요소를 '포함'한다는 것은, 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있다는 것을 의미한다. 구체적으로, "포함하다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다."Including" a certain component means that other components may be further included, rather than excluding other components unless specifically stated to the contrary. Specifically, terms such as "comprises" or "have" are intended to designate the presence of features, numbers, steps, actions, components, parts, or combinations thereof described in the specification, but one or more other features or It is to be understood that the presence or addition of numbers, steps, actions, components, parts or combinations thereof does not preclude the possibility of preliminary exclusion.
제1, 제2 등의 용어는 다양한 구성 요소들을 설명하는데 사용될 수 있지만, 상기 구성 요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다.Terms such as first and second may be used to describe various components, but the components should not be limited by the terms. These terms are used only for the purpose of distinguishing one component from another component. For example, without departing from the scope of the present invention, a first element may be referred to as a second element, and similarly, a second element may be referred to as a first element.
단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 또한 도면에서 요소들의 형상 및 크기 등은 보다 명확한 설명을 위해 과장될 수 있다.Singular expressions include plural expressions unless the context clearly indicates otherwise. In addition, shapes and sizes of elements in the drawings may be exaggerated for clearer explanation.
본 명세서 전체에서 사용되는 '~부' 및 '~모듈' 은 적어도 하나의 기능이나 동작을 처리하는 단위로서, 예를 들어 소프트웨어, FPGA 또는 ASIC과 같은 하드웨어 구성요소를 의미할 수 있다. 그렇지만 '~부' 및 '~모듈'이 소프트웨어 또는 하드웨어에 한정되는 의미는 아니다. '~부' 및 '~모듈'은 어드레싱할 수 있는 저장 매체에 있도록 구성될 수도 있고 하나 또는 그 이상의 프로세서들을 재생시키도록 구성될 수도 있다.The'~ unit' and'~ module' used throughout this specification are units that process at least one function or operation, and may mean hardware components such as software, FPGA, or ASIC. However,'~ unit' and'~ module' are not meant to be limited to software or hardware. The'~ unit' and the'~ module' may be configured to be in an addressable storage medium, or may be configured to reproduce one or more processors.
일 예로서 '~부' 및 '~모듈'은 소프트웨어 구성요소들, 객체지향 소프트웨어 구성요소들, 클래스 구성요소들 및 태스크 구성요소들과 같은 구성요소들과, 프로세스들, 함수들, 속성들, 프로시저들, 서브루틴들, 프로그램 코드의 세그먼트들, 드라이버들, 펌웨어, 마이크로 코드, 회로, 데이터, 데이터베이스, 데이터 구조들, 테이블들, 어레이들 및 변수들을 포함할 수 있다. 구성요소와 '~부' 및 '~모듈'에서 제공하는 기능은 복수의 구성요소 및 '~부' 및 '~모듈'들에 의해 분리되어 수행될 수도 있고, 다른 추가적인 구성요소와 통합될 수도 있다.As an example,'~ unit' and'~ module' are components such as software components, object-oriented software components, class components and task components, processes, functions, properties, Procedures, subroutines, segments of program code, drivers, firmware, microcode, circuits, data, databases, data structures, tables, arrays, and variables. Components and functions provided by'~ unit' and'~ module' may be performed separately by a plurality of elements and'~ unit' and'~ module', or may be integrated with other additional components. .
본 발명에서는 동적인 도로 네트워크에서 ε-거리 조인 질의 처리 방법을 이용하는 방법에 있어서, 처리 시간을 효과적으로 줄일 수 있는 방법에 대해 제시한다. 본 발명에 따른 ε-거리 조인 질의 처리 방식을 사용하는 경우, 동적인 도로망 네트워크에서 수시로 변하는 도로 상황을 반영한 ε-거리 조인 질의 처리가 가능하며, 실시간 처리가 가능한 효과가 있다. In the present invention, in a method of using an ε-distance join query processing method in a dynamic road network, a method for effectively reducing processing time is proposed. When the ε-distance join query processing method according to the present invention is used, it is possible to process an ε-distance join query that reflects frequently changing road conditions in a dynamic road network network, and it is possible to perform real-time processing.
이하에서는 첨부된 도면을 참조하여 본 발명의 일 실시예를 상세하게 설명한다.Hereinafter, an embodiment of the present invention will be described in detail with reference to the accompanying drawings.
도 1은 일반적인 도로 네트워크 상에 위치한 각각의 객체들을 표현하는 도면이다. 도 1(a) 및 도 1(b)에서는, 사각형으로 표시한 택시 승객과, 삼각형으로 표시된 택시들이 도로 네트워크 상에 배치되어 있다. 실제 도로 네트워크는 도 1과 같이 복잡하게 도로가 얽혀져 있으며, 얽힌 도로 상에서 택시들은 동적으로 움직이며, 택시에 탑승하고자 하는 승객들도 동적으로 도로 네트워크 상에서 움직이게 된다. 도로 네트워크 상에서는 도로의 길을 고려하여 최단거리를 설정해야 하기 때문에, 유클리드 최단 거리를 사용할 수 없다. 택시에 탑승하고자 하는 승객들이 자기의 현재 위치와 가장 가깝게 위치하는 택시를 알아보고자 할 때, 모든 택시에 대하여 도로 네트워크 상의 거리를 고려하여 승객과 가장 가까운 택시들을 찾아야 한다. 그러나, 동적으로 움직이는 거리 상에서 일일이 거리를 계산하기에는 굉장히 많은 시간이 소요되며, 도로 네트워크가 복잡하게 얽혀 있고 택시의 개수가 많은 경우 연산 시간이 훨씬 길어지게 되어, 효율적인 처리가 어려운 문제점이 발생하며 빠르게 연산을 수행하여 결과를 도출하여야 하는 시스템에서는 적합하지 아니한 문제점이 있었다. 또한 도 1(b)에 따르면, 교통 체증이 증가하는 시간대에서는 택시의 위치가 도 1(a)와 동일한 장소에 위치하더라도 동일한 승객의 위치로부터 가장 가까운 택시가 변경될 수 있다. 이는 동적 시스템에서 나타나는 문제점에 해당한다.1 is a diagram representing respective objects located on a general road network. In Figs. 1(a) and 1(b), taxi passengers indicated by squares and taxis indicated by triangles are arranged on a road network. In the actual road network, roads are complicatedly entangled as shown in FIG. 1, taxis move dynamically on the entangled roads, and passengers who want to board taxis also move dynamically on the road network. Since the shortest distance must be set in consideration of the road on the road network, the Euclidean shortest distance cannot be used. When a passenger who wants to board a taxi wants to find a taxi that is closest to their current location, they must find the taxi closest to the passenger by considering the distance on the road network for all taxis. However, it takes a very long time to calculate the distance on a dynamically moving distance, and when the road network is complicated and the number of taxis is large, the calculation time becomes much longer, which makes it difficult to efficiently process and calculates quickly. There was a problem that was not suitable for a system in which the results were to be derived by performing. In addition, according to FIG. 1(b), even if the location of the taxi is located in the same place as that of FIG. 1(a) in a time period when traffic congestion increases, the nearest taxi may be changed from the location of the same passenger. This is a problem that appears in dynamic systems.
이하에서는 도 1과 같은 도로 네트워크 상에서 ε-거리 조인 질의를 효율적으로 처리하는 방법에 대해 자세히 설명한다.Hereinafter, a method of efficiently processing an ε-distance join query on a road network as shown in FIG. 1 will be described in detail.
도 2는 본 발명에 따른 ε-거리 조인 질의 처리 장치(100)의 주요 구성을 나타낸 블록도이다. ε-거리 조인 질의 처리 장치(100)는 수신부(110)와, 전송부(130) 및 질의 결과 연산부(120)를 포함할 수 있다.2 is a block diagram showing the main configuration of the ε-distance join
수신부(110)는, 클라이언트 단말(미도시)로부터의 질의 요청정보를 수신할 수 있다. 상기 클라이언트 단말에서의 질의 요청정보는, 질의 요구조건에 부합되는 객체로서, 질의하는 클라이언트 단말의 위치를 기준으로, 거리 ε 이내에 위치하는 제2데이터 객체 정보이다. 상기 거리는 클라이언트가 클라이언트 단말에서 원하는 거리만큼의 숫자를 입력할 수 있다. 상기 숫자는 정수일 수 있다. 상기 거리는 km 단위일 수 있다. 클라이언트 단말에서는, 질의하는 클라이언트 단말의 위치를 기준으로, 일정 거리 이내의 제2데이터 객체뿐만 아니라 일정 시간 내에 도달할 수 있는 제2데이터 객체 정보를 요구할 수도 있다. 상기 일정 시간은 거리를 고려하여 설정될 수 있다. 상기 시간은 동적 도로 네트워크를 고려하여 도출되는 시간일 수 있다. 이하에서는, 설명을 위해 ε를 거리로 가정하고 설명하나, ε는 시간일 수 있다.The
질의 결과 연산부(120)는, 수신부(110)에서 수신된 질의 요청정보에 응답하되, 제1데이터 집합에 포함된 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 집합에 포함된 제2데이터 객체들을 제2데이터 세그먼트로 정의하고, 상기 제1데이터 세그먼트 내에 포함된 2개의 제1데이터 객체에 대해 ε-거리 이웃 조인 질의를 수행하고, 상기 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 ε-거리 이웃 조인 질의와 다른 방법으로 일정 거리 ε 안에 위치하는 제2데이터 객체를 도출할 수 있다. 상기 질의 결과 연산부의 주요 구성은 도 3에서 설명된다.The query result
전송부(130)는, 상기 질의 결과 연산부(120)에서 연산된 질의하는 클라이언트 단말의 위치를 기준으로 거리 ε 이내에 존재하는 제2데이터 객체 정보를 클라이언트 단말로 전송할 수 있다.The
도 3은 본 발명에 따른 ε-거리 조인 질의 처리 장치(100)가 포함하는 질의 결과 연산부(120)의 주요 구성을 나타낸 블록도이다.3 is a block diagram showing a main configuration of a query
상기 질의 결과 연산부(120)는 노드 결정 모듈(121), 데이터 객체 검색 모듈(122), 그룹화 모듈(123), 질의 결과 처리 모듈(124)을 포함할 수 있다.The query result
노드 결정 모듈(121)은 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별할 수 있다. 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개일 경우, 2개일 경우 및 3개 이상일 경우로 노드를 분류하여 결정할 수 있다. 자세한 노드 분류 방법은 후술한다.The
데이터 객체 검색 모듈(122)은, 상기 노드 결정 모듈(121)에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체 및 제2데이터 객체를 검색할 수 있다. 데이터 객체 검색 모듈(122)을 통해, 후술할 제1데이터 세그먼트를 정의하는 데 필요한 제1데이터 객체를 추출할 수 있으며, 후술할 제2데이터 세그먼트를 정의하는 데 필요한 제2데이터 객체를 추출할 수도 있으며, 후술할 제1데이터 세그먼트 상에 위치하는 제2데이터 객체를 추출할 수도 있다. 데이터 객체 검색 모듈(122)에서는, 도로 네트워크 상에 존재하는 제1데이터 객체 및 제2데이터 객체를 검색할 수 있다.The data object
그룹화 모듈(123)은, 상기 노드 결정 모듈(121)에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체들을 제1데이터 세그먼트로 정의할 수 있다. 그룹화 모듈(123)은, 상기 노드 결정 모듈(121)에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제2데이터 객체들을 제2데이터 세그먼트로 정의할 수 있다. 그룹화 모듈(123)에서 제1데이터 세그먼트와 제2데이터 세그먼트를 정의하는 방법은 후술한다.The
질의 결과 처리 모듈(124)은 상기 그룹화 모듈(123)에서 생성된 제1데이터 세그먼트에 대한 ε-거리 조인 질의 처리를 수행할 수 있다. 질의 결과 처리 모듈(124)은 제1 ε-거리 조인 질의 처리 모듈(1241)과 제2 ε-거리 조인 질의 처리 모듈(1242)을 포함하여, 두 가지 방법으로 ε-거리 조인 질의를 수행할 수 있다. 질의 결과 처리 모듈(124)의 주요 구성은 도 4에서 설명된다.The query
도 4는, 본 발명에 따른 ε-거리 조인 질의 처리 장치(100)가 포함하는 질의 결과 처리 모듈(124)의 주요 구성을 나타낸 블록도이다.4 is a block diagram showing the main configuration of a query
질의 결과 처리 모듈(124)은 제1 ε-거리 조인 질의 처리 모듈(1241)과 제2 ε-거리 조인 질의 처리 모듈(1242), 제1 저장 모듈(1243), 제2 저장 모듈(1244) 및 거리 계산 모듈(1245)을 포함할 수 있다.The query
제1 ε-거리 조인 질의 처리 모듈(1241)에서는, 상기 그룹화 모듈(123)에서 정의된 제1데이터 세그먼트를 일정 기준으로 분류한다. 상기 제1데이터 세그먼트를 분류하는 기준은, 상기 제1데이터 세그먼트 상에 포함되어 있는 제1데이터 객체의 개수를 기준으로 할 수 있다. 제1데이터 세그먼트 상에 포함되어 있는 제1데이터 객체의 개수가 1개인 경우, 2개인 경우 및 3개 이상인 경우를 기준으로 하여 분류할 수 있다.The first ε-distance join
제1 ε-거리 조인 질의 처리 모듈(1241)에서는 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체에 대한 ε-거리 조인 질의를 수행한다. 상기 분류 기준에 의해 분류된 제1데이터 세그먼트 상에 포함되어 있는 제1데이터 객체의 개수가 1개일 경우에는, 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체가 없이 1개의 객체만 존재하는 것이므로, 1개의 제1데이터 객체에 대해 ε-거리 조인 질의 처리를 수행한다. 제1데이터 세그먼트 상에 포함되어 있는 제1데이터 객체의 개수가 2개일 경우에는, 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체가 2개의 제1데이터 객체에 해당할 것이므로, 2개의 제1데이터 객체에 대해 ε-거리 조인 질의 처리를 수행한다.The first ε-distance join
제1데이터 세그먼트 상에 포함되어 있는 제1데이터 객체의 개수가 3개 이상일 경우에는, 제1데이터 세그먼트의 양 끝단에 위치하는 2개의 제1데이터 객체에 대해 ε-거리 조인 질의 처리를 수행하고, 상기 양 끝단에 위치하지 않은 나머지 제1데이터 객체에 대해서는 거리 계산 모듈(1245)을 통해 거리 계산을 수행하게 된다. 상세한 내용은 후술한다.When the number of first data objects included in the first data segment is three or more, ε-distance join query processing is performed on two first data objects located at both ends of the first data segment, For the remaining first data objects not located at both ends, distance calculation is performed through the
제1 저장 모듈(1243)은, 제1 ε-거리 조인 질의 처리 모듈(1241)에서 수행된 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체에 대해 ε-거리 조인 질의를 수행한 결과로 나타난 상기 양 끝단에 위치하는 제1데이터 객체 각각으로부터 거리 ε 이내에 위치하는 제2데이터 객체들을 저장할 수 있다. 제1 저장 모듈(1243)은 제1 ε-거리 조인 질의 처리 모듈(1241)에서 수행된 결과 데이터를 저장할 수 있다.The
제2 저장 모듈(1244)은, 상기 그룹화 모듈(123)에서 정의된 제1데이터 세그먼트 상에 포함되어 있는 제2데이터 객체들을 저장할 수 있다.The
거리 계산 모듈(1245)은 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체에 대해 거리 계산을 수행할 수 있다. 거리 계산 모듈(1245)은 제1 ε-거리 조인 질의 처리 모듈(1241)에서 ε-거리 조인 질의 처리가 수행되지 않은 제1데이터 객체에 대해 거리 계산을 수행할 수 있다.The
거리 계산 모듈(1245)은 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체와 상기 제1 저장 모듈(1243) 및 제2 저장 모듈(1244)에 저장된 제2데이터 객체들과의 거리를 계산할 수 있다. 거리 계산 모듈(1245)은 제1 ε-거리 조인 질의 처리 모듈(1241)에서 ε-거리 조인 질의가 수행되지 않은 제1데이터 객체에 대해 제1 저장 모듈(1243) 및 제2 저장 모듈(1244)에 저장된 제2데이터 객체와의 거리를 계산하여, 거리 ε 이내에 위치하는 제2데이터 객체를 추출할 수 있다.The
제2 ε-거리 조인 질의 처리 모듈(1242)은, 제1 ε-거리 조인 질의 처리 모듈(1241)과 선택적으로 처리될 수 있다. 그러나 일정한 조건에 따라 동시에 처리되어 수행될 수도 있다. 제2 ε-거리 조인 질의 처리 모듈(1242)은, 제1 ε-거리 조인 질의 처리 모듈(1241)과 같이 제1데이터 세그먼트의 양 끝단의 제1데이터 객체에 대해 ε-거리 조인 질의를 처리하는 것이 아니라, 일정한 기준을 만족시킨 노드에 대해서 ε-거리 조인 질의 처리를 수행한다. 상세한 내용은 이하에서 도면과 함께 설명한다.The second ε-distance join
이하에서는 도 2 내지 도 4에서 설명한 ε-거리 조인 질의 처리 장치(100)의 구성요소를 이용하여, ε-거리 이웃 조인 질의를 수행하는 방법에 대해 도면을 이용하여 구체적으로 설명한다.Hereinafter, a method of performing an ε-distance neighbor join query using the components of the ε-distance join
도 5는 도로 네트워크 상에서 ε-거리 조인 질의 처리를 설명하기 위해 예시로 제시된 도로 네트워크이다.5 is a road network presented as an example to explain processing of an ε-distance join query on a road network.
ε-거리 조인 질의 처리를 수행하는 방법을 설명하기 이전에, 도면에 표시된 기호들과, 본 명세서에서 쓰여질 기호들 및 용어에 대해 간단히 설명한다.Before describing a method of performing the ε-distance join query processing, the symbols shown in the drawings and the symbols and terms to be used in the present specification will be briefly described.
r1 내지 r5는 제1데이터 객체를 나타낸다. 즉, r은 제1데이터 객체의 집합 R이 포함하는 제1데이터 객체들을 의미한다. 도면에서는 사각형으로 표시된다. s1 내지 s6은 제2데이터 객체를 나타낸다. 즉, s는 제2데이터 객체의 집합 S가 포함하는 제2데이터 객체를 의미한다. 도면에서는 삼각형으로 표시된다. 도로 세그먼트 상에 표시된 숫자(number)는 두 지점간의 거리를 의미하며 노드
이하에서는 후술할 명세서 및 알고리즘에서 쓰이는 기호에 대해 설명한다.
상기 용어들을 바탕으로 하여 ε-거리 조인 질의를 수행하는 방법에 대해 설명한다.A method of performing an ε-distance join query based on the above terms will be described.
도 6(a)는 ε-거리 조인 질의 처리 장치에서, 제1데이터 세그먼트를 정의하는 방법을 설명하기 위한 도면이다. 도 6(b)는 ε-거리 조인 질의 처리 장치에서, 제2데이터 세그먼트를 정의하는 방법을 설명하기 위한 도면이다.6(a) is a diagram for explaining a method of defining a first data segment in an ε-distance join query processing apparatus. 6(b) is a diagram for explaining a method of defining a second data segment in the ?-distance join query processing apparatus.
노드 결정 모듈(121)에서는, 전술한 바와 같이 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하여, 노드를 분류하고 결정할 수 있다.As described above, the
도 6을 참조하면, 노드는 도로 네트워크에서의 도로 세그먼트가 각각 교차하는 교차점 또는 경계점을 의미하므로, 도 6에 나타난 도로 네트워크 상에는 노드로 표시된
노드 결정 모듈(121)에서는 일정한 기준에 따라, 노드를 3종류로 분류할 수 있다. 도로 네트워크에서의 노드를 기준으로, 인접하는 도로 세그먼트가 3개 이상일 경우에는 인터섹션(intersection) 노드로 정의한다. 도로 네트워크에서의 노드를 기준으로, 인접하는 도로 세그먼트가 2개일 경우에는 인터메디에잇(intermediate) 노드로 정의한다. 도로 네트워크에서의 노드를 기준으로, 인접하는 도로 세그먼트가 1개일 경우에는 터미널(terminal) 노드로 정의한다.The
도 6을 참조하면, 노드
상기 노드 결정 모듈(121)에서 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하고 노드를 분류하면, 그를 이용하여 그룹화 모듈(123)은 제1데이터 세그먼트를 정의할 수 있다. 상기 노드 결정 모듈(121)에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체들을 제1데이터 세그먼트로 정의할 수 있다.When the
상기 노드 결정 모듈(121)에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트를 설명을 위해, "노드 시퀀스"로 본 명세서에서 정의한다.For the purpose of describing a road segment connected by nodes having one or three or more road segments intersecting with respect to the node determined in the
이하에서는 상기 정의된 노드들을 이용하여 노드 시퀀스를 형성하는 방법에 대해 설명한다. 노드 시퀀스는 두 노드 간의 경로일 수 있다. 이 때 노드 시퀀스의 양 끝단을 이루는 노드로는 인터섹션(intersection) 노드 혹은 터미널(terminal) 노드가 될 수 있다. 또한 노드 시퀀스의 양 끝단을 제외한 내부에 포함되는 노드는 인터메디에잇(intermediate) 노드가 될 수 있다.Hereinafter, a method of forming a node sequence using the defined nodes will be described. The node sequence may be a path between two nodes. At this time, nodes forming both ends of the node sequence may be an intersection node or a terminal node. In addition, nodes included inside except for both ends of the node sequence may be intermediate nodes.
즉, 노드 시퀀스를 형성하는 방법은 터미널(terminal) 노드 혹은 인터섹션(intersection) 노드를 노드 시퀀스의 시작점으로 설정한다. 그 후, 다른 터미널(terminal) 노드 혹은 다른 인터섹션(intersection) 노드까지 경로를 이동한다. 그 때, 노드 시퀀스의 양 끝단을 제외한 내부 세그먼트에 포함되는 노드는 인터메디에잇(intermediate) 노드일 수 있다.That is, a method of forming a node sequence is to set a terminal node or an intersection node as the starting point of the node sequence. After that, it moves the path to another terminal node or another intersection node. In this case, nodes included in the inner segment excluding both ends of the node sequence may be intermediate nodes.
상기 노드 시퀀스를 설정하는 방법을 도 6을 참고하여 설명하면 다음과 같다. 인터섹션(intersection) 노드인
이하에서는, 상기 설정된 노드 시퀀스를 이용하여 제1데이터 세그먼트 및 제2데이터 세그먼트를 정의하는 방법을 설명한다. 제1데이터 세그먼트는 상기 설정된 노드 시퀀스에 포함된 제1데이터 객체들의 집합을 이용하여 설정될 수 있다.Hereinafter, a method of defining a first data segment and a second data segment using the set node sequence will be described. The first data segment may be set using a set of first data objects included in the set node sequence.
데이터 객체 검색 모듈(122)은, 상기 설정된 노드 시퀀스 상에 위치하는 제1데이터 객체 및 제2데이터 객체를 검색할 수 있다. 데이터 객체 검색 모듈(122)은 상기 노드 시퀀스 상에 위치하는 제1데이터 객체를 검색하여, 그룹화 모듈(123)에서 제1데이터 세그먼트를 정의할 수 있다. 제1데이터 세그먼트를 정의하는 방법을 이하에서 도면을 이용하여 설명한다.The data object
도 5 내지 도 6을 참고하여, 상기 노드 시퀀스인
제1데이터 세그먼트는, 상기 각각의 노드 시퀀스 상에 포함된 제1데이터 객체들을 그룹화한 것을 의미한다. 즉 노드 시퀀스
제2데이터 세그먼트 역시 같은 맥락으로 결정될 수 있다. 노드 시퀀스
즉 제1데이터 세그먼트를 정의하는 방법은, 데이터 객체 검색 모듈(122)을 이용하여 상기 노드 시퀀스 상에 포함된 제1데이터 객체를 검색한 후에, 상기 노드 시퀀스의 한 끝단의 노드에서 가장 가까운 제1데이터 객체를 시작점으로 하고, 상기 노드 시퀀스의 나머지 끝단의 노드에서 가장 가까운 제1데이터 객체를 끝지점으로 하여 상기 노드 시퀀스 상에 포함된 제1데이터 객체를 모두 포함하도록 이어진 도로 세그먼트의 일부분을 제1데이터 세그먼트로 정의할 수 있다. 제2데이터 세그먼트의 정의 방법도 동일하다.That is, the method of defining the first data segment is, after searching for the first data object included in the node sequence using the data object
상기와 같이 제1데이터 세그먼트
기준으로 한다는 것의 의미는 해당 데이터 객체로부터 거리 ε 이내인 다른 집합의 데이터 객체를 도출할 때, 해당 데이터 객체를 기준점으로 정하고, 기준점으로 정한 데이터 객체로부터 거리 ε 이내인 다른 집합의 데이터 객체를 찾는다는 것을 의미한다. 따라서 제1데이터 집합과 제2데이터 집합이 있을 때, 제1데이터 집합을 기준으로 할 경우 제1데이터 집합으로부터 거리 ε 이내의 데이터 객체들은 제2데이터 집합으로부터 찾고, 제2데이터 집합을 기준으로 할 경우 제2데이터 집합으로부터 거리 ε 이내의 데이터 객체들은 제1데이터 집합으로부터 찾을 수 있다.By reference means that when deriving another set of data objects within the distance ε from the data object, the data object is set as the reference point, and another set of data objects within the distance ε from the data object set as the reference point is searched. Means that. Therefore, when there is a first data set and a second data set, when based on the first data set, data objects within a distance ε from the first data set are found from the second data set, and when based on the second data set Data objects within a distance ε from the second data set can be found from the first data set.
즉, 본 발명에서는 제1데이터 객체와 제2데이터 객체에 대해 각각 제1데이터 세그먼트와 제2데이터 세그먼트를 정의하여, 데이터 세그먼트의 개수가 적은 데이터 세그먼트를 기준으로 하여 ε-거리 조인 질의를 수행할 수 있다. 본 발명에서는 교환법칙이 성립되어, 기준을 어떤 데이터 세그먼트로 잡더라도 결과는 동일하나, 처리 시간에서는 차이가 있을 수 있다.That is, in the present invention, a first data segment and a second data segment are defined for the first data object and the second data object, respectively, and the ε-distance join query is performed based on the data segment with a small number of data segments. I can. In the present invention, the commutation law is established, so that no matter which data segment the criterion is used, the result is the same, but there may be a difference in processing time.
이하에서는, 제1데이터 세그먼트가 기준이 되는 데이터 집합 R로 설정된 경우로 가정하여 설명한다. 즉, 제1데이터 집합 R을 기준으로 하여, 제1데이터 집합 R에 포함된 제1데이터 객체로부터 거리 ε 이내에 위치하는 제2데이터 객체를 제2데이터 집합 S로부터 찾는다는 것을 가정하고 설명한다.Hereinafter, it is assumed that the first data segment is set as the reference data set R. That is, based on the first data set R, it is assumed that a second data object located within a distance ε from the first data object included in the first data set R is found from the second data set S.
상기 정의된 제1데이터 세그먼트에 대해 ε-거리 조인 질의를 수행하게 된다. 이를 수행하는 자세한 메커니즘은 이하에서 설명한다.An ε-distance join query is performed on the first data segment defined above. A detailed mechanism for performing this will be described below.
제1 ε-거리 조인 질의 처리 모듈(1241)에서는, 상기 정의된 제1데이터 세그먼트에 포함된 제1데이터 객체의 개수들을 추출한다. 도 6을 예로 들면, 제1데이터 세그먼트
이 때, 제1데이터 세그먼트에 포함된 제1데이터 객체의 개수가 1개 혹은 2개일 경우에는, 제1 ε-거리 조인 질의 처리 모듈(1241)은 해당 데이터 세그먼트에 포함된 모든 제1데이터 객체에 대하여 ε-거리 조인 질의를 수행한다.In this case, if the number of first data objects included in the first data segment is one or two, the first ε-distance join
제1데이터 세그먼트에 포함된 제1데이터 객체의 개수가 3개 이상일 경우에는 이하와 같이 처리된다.When the number of first data objects included in the first data segment is three or more, processing is performed as follows.
제1 ε-거리 조인 질의 처리 모듈(1241)은 제1데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체들을 추출한다. 제1데이터 세그먼트
제1데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체를 제외한 내부에 포함된 나머지 제1데이터 객체(도 6에서는 r5)에 대해서는 거리 계산 모듈(1245)을 이용하여 거리 계산이 수행된다. 이 때, 거리 계산이 진행되는 제2데이터 객체의 집합은 제1 저장 모듈(1243)에 저장되는 상기 제1 데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체들에 대한 ε-거리 조인 질의 결과와, 제2 저장 모듈(1244)에 저장되는 제1데이터 세그먼트 내부에 포함된 제2데이터 객체를 합친 것의 집합일 수 있다.A distance calculation is performed using the
즉, 상기 알고리즘이 가능하기 위해서는 제1데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체를 제외한 내부에 포함되는 제1데이터 객체에 대한 ε-거리 조인 질의 결과가, 제1데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체들로부터 거리 ε 이내의 제2데이터 객체 및 제1데이터 세그먼트에 포함된 제2데이터 객체를 합친 집합 중에 포함되어야 함이 전제되어야 한다.That is, in order to enable the above algorithm, the result of the ε-distance join query result for the first data object included inside excluding the first data object included at both ends of the first data segment is at both ends of the first data segment. It should be premised that the second data object within a distance ε from the included first data objects and the second data object included in the first data segment must be included in the combined set.
이를 도 7을 이용하여, 간단한 증명으로써 입증한다.This is verified by a simple proof using FIG. 7.
증명하고자 하는 명제는 다음과 같다.The proposition to be proved is as follows.
모든 제1데이터 객체
즉, 상기 수식이 의미하는 바는 제1데이터 세그먼트 내부에 포함된 제1데이터 객체로부터 거리 ε 이내에 위치하는 제2데이터 객체는, 제1데이터 세그먼트의 양 끝단에 위치한 각 제1데이터 객체로부터 거리 ε 이내에 위치하는 제2데이터 객체들의 집합과 제1데이터 세그먼트 상에 위치한 제2데이터 객체들의 집합을 합친 것 중에 존재한다는 것이다.That is, what the formula means is that a second data object located within a distance ε from a first data object included in the first data segment is a distance ε from each first data object located at both ends of the first data segment. It is present in the sum of the set of second data objects positioned within and the set of second data objects positioned on the first data segment.
증명 방법으로는, 상기 수식이 반대됨을 전제로 하여, 반대되는 명제가 참이 아님을 증명한다. 즉,
그러나 상기와 같이
도 8은 본 발명에 따른 거리 계산을 설명하기 위한 도면이다. 8 is a diagram for describing distance calculation according to the present invention.
도 8(a)에 따르면, 제2데이터 객체 s가 제1데이터 세그먼트 상에 포함되지 않은 경우 dist(r,s)는
즉 상기 증명에 따르면, 제1데이터 세그먼트의 양 끝단에 포함된 제1데이터 객체를 제외하고, 내부에 포함된 제1데이터 객체에 대해서 ε-거리 조인 질의를 처리할 필요 없이, 이미 처리된 제2데이터 객체의 집합 내에서 간단한 연산을 통해 거리만을 계산함으로써 ε-거리 조인 질의를 하는 것과 같은 결과를 얻을 수 있는 것으로써, 모든 제1데이터 객체에 대해 ε-거리 조인 질의를 수행하는 것보다 시간 측면이나 효율 측면에서 훨씬 효과적으로 수행이 가능하게 된다. That is, according to the above proof, it is not necessary to process the ε-distance join query for the first data object included therein, excluding the first data object included at both ends of the first data segment. By calculating only the distance through a simple operation within a set of data objects, the same result can be obtained as performing an ε-distance join query. It is more time-wise than performing an ε-distance join query for all the first data objects. However, it becomes possible to perform much more effectively in terms of efficiency.
상기 설명한 ε-조인 질의 처리 및 거리 계산을 수행하는 알고리즘은 다음과 같이 표현될 수 있다.The algorithm for performing the ε-join query processing and distance calculation described above can be expressed as follows.
이하 알고리즘 1은 상기 위에서 전술한 제1데이터 세그먼트와 제2데이터 세그먼트의 그룹화 과정과 제1데이터 세그먼트 내에 포함된 제1데이터 객체의 개수에 따라 ε-거리 조인 질의 처리를 수행하는 내용을 알고리즘으로 나타낸 것이다.
상기 알고리즘 1에 따르면, 제1데이터 세그먼트 내에 포함된 제1데이터 객체의 개수가 2개 이상인 경우 내부에 포함된 제1데이터 객체에 대해서는 이하의 알고리즘 3에 나타난 거리 계산 수식을 통해 도출이 가능하다.According to
알고리즘 3에 있어서, 거리 판단의 대상이 되는 제2데이터 객체 s가 어떠한 집합 안에 포함되는지 여부에 따라, 7가지의 알고리즘을 통해 제1데이터 객체와 제2데이터 객체 간의 거리를 계산할 수 있다. 제2데이터 객체의 포함 조건에 따른 거리 계산을 나타내는 표는 아래와 같이 표현할 수 있다. In
상기 설명한 알고리즘 1과 알고리즘 3 및 설명한 ε-거리 조인 질의 방법에 의해, 도 6의 도로 네트워크 상에서 각각의 제1데이터 객체로부터 거리 ε 이내에 존재하는 제2데이터 객체를 찾는 방법에 대해서 설명한다.A method of finding a second data object within a distance ε from each first data object on the road network of FIG. 6 will be described by using the
제1데이터 객체의 집합은 r1 내지 r5에 해당하고, 제2데이터 객체의 집합은 s1 내지 s6가 된다. 본 실시예에서 거리 ε는 5로 설정한다.The set of first data objects corresponds to r1 to r5, and the set of second data objects is s1 to s6. In this embodiment, the distance ε is set to 5.
상기에서 설명한 바와 같이, 도 6의 도로 네트워크에서의 제1데이터 세그먼트는
2개의 제1데이터 객체를 포함하는 제1데이터 세그먼트
3개 이상의 제1데이터 객체를 포함하는 제1데이터 세그먼트인
구체적으로, 제1데이터 객체 r5에 있어서, r5와 거리 ε 이내에 있을 수 있는 제2데이터 객체의 집합에는 {
제2데이터 객체
제2데이터 객체
제2데이터 객체
즉 r5로부터 거리 5 이내에 있는 제2데이터 객체는 s2인 것을 알 수 있다.That is, it can be seen that the second data object within the distance 5 from r5 is s2.
따라서 r5에 대해서는 ε-거리 조인 질의를 수행하지 아니하고 거리 ε 내에 위치하는 제2데이터 객체를 도출해 낼 수 있다. Therefore, for r5, the second data object located within the distance ε can be derived without performing the ε-distance join query.
본 발명의 다른 실시예에 따르면, 상기 전술한 방법을 이용한 ε-거리 조인 질의 방법보다 처리를 더 효율적으로 진행할 수 있는 방법을 제안한다.According to another embodiment of the present invention, a method capable of performing processing more efficiently than the ε-distance join query method using the above-described method is proposed.
본 발명의 다른 실시예에서는, 질의 결과 처리 모듈(124)의 제2 ε-거리 조인 질의 처리 모듈(1242)을 이용하여 ε-거리 조인 질의를 수행할 수 있다.In another embodiment of the present invention, an ε-distance join query may be performed using the second ε-distance join
상기 방법은 도로 네트워크 상에 노드로부터 노드 시퀀스를 설정하고, 상기 노드 시퀀스 내부에 포함된 제1데이터 세그먼트 및 제2데이터 세그먼트를 정의하는 방법까지는 전술한 바와 동일하므로 생략한다.In the above method, a node sequence is set from a node on a road network, and a method of defining a first data segment and a second data segment included in the node sequence is the same as described above, and thus is omitted.
전술한 제1 ε-거리 조인 질의 처리 모듈(1241)을 이용한 ε-거리 조인 질의 처리 방법의 실시예에서는, 제1데이터 세그먼트 내에 포함된 제1데이터 객체의 개수가 3개 이상일 경우 내부에 포함된 제1데이터 객체에 대해서는 거리 계산 모듈(1245)을 이용한 거리 계산을 이용하였다면, 본 실시예에서는 특정 노드를 기준으로 한 제1데이터 세그먼트의 개수가 2개 이상일 경우에 전술한 바와 다른 방법을 이용하여 제2 ε-거리 조인 질의 처리 모듈(1242)을 이용하여 ε-거리 조인 질의를 수행한다.In an embodiment of the ε-distance join query processing method using the first ε-distance join
제2 ε-거리 조인 질의 처리 모듈(1242)에서의 처리 방법은 이하와 같다.The processing method in the second ε-distance join
상기와 같이 제1데이터 세그먼트를 정의한 경우, 인터섹션 노드를 기준으로 교차하는 인접한 도로 세그먼트에 포함되는 제1데이터 세그먼트의 개수를 추출한다. 이 때, 추출한 노드와 인접한 도로 세그먼트에 포함된 제1데이터 세그먼트가 2개 이상일 경우에는, 상기 추출한 노드에 대한 ε-거리 조인 질의를 수행한다.When the first data segment is defined as described above, the number of first data segments included in adjacent road segments crossing the intersection node is extracted. In this case, when there are two or more first data segments included in the extracted node and the adjacent road segment, an ε-distance join query for the extracted node is performed.
추출한 노드와 인접한 도로 세그먼트에 포함된 제1데이터 세그먼트가 2개 이상일 경우를 도 10을 이용하여 설명한다. 이를 설명하기 전에 새로운 문자를 정의한다.
도 10은 도로 네트워크들의 일 예를 나타낸 도면이다. 도면에서 굵은 부분으로 표시한 것은 제1데이터 세그먼트를 나타낸다.10 is a diagram illustrating an example of road networks. In the drawings, bold portions indicate the first data segment.
도 10(a)에서는 도로 네트워크 상에 제1데이터 세그먼트가 존재하지 아니한다. 이 경우, ε-거리 조인 질의는 수행되지 아니한다.In FIG. 10A, the first data segment does not exist on the road network. In this case, the ε-distance join query is not executed.
도 10(b)에서는 도로 네트워크 상에 제1데이터 세그먼트
도 10(c)에서는 도로 네트워크 상에, 제1데이터 세그먼트
노드를 기준으로 ε-거리 조인 질의 처리를 수행하는 것은 이하와 같이 설명할 수 있다.
도 11은 제2 ε-거리 조인 질의 모듈에서, 대상이 되는 노드가 인터섹션 노드가 되어야 하는 근거를 설명한다. 도 11에 따르면, 하나의 인터섹션 노드
이 때, 도 11에 따른 로드 네트워크에서, 제1 ε-거리 조인 질의 처리 모듈을 이용하여 질의를 수행할 경우,
이하에서는, 상기 제2 ε-거리 조인 질의 처리 모듈(1242)을 이용하여 도 5 내지 도 6에서의 ε-거리 조인 질의를 처리하는 방법에 대해 설명한다. Hereinafter, a method of processing the ε-distance join query in FIGS. 5 to 6 using the second ε-distance join
전술한 바와 같이, 제1 ε-거리 조인 질의 처리 모듈(1241)을 이용하여 ε-거리 조인 질의를 수행할 때에는 제1데이터 객체 r1, r2, r3, r4에 대해서 ε-거리 조인 질의를 수행하였다. 즉 총 4번의 ε-거리 조인 질의를 수행하였다. 그러나, 제2 ε-거리 조인 질의 처리 모듈(1242)을 이용하여 ε-거리 조인 질의를 수행할 경우, 인터섹션 노드인
이하의 알고리즘 2는 상기 전술한 제1데이터 세그먼트와 제2데이터 세그먼트의 그룹화 과정과, 노드를 기준으로 하여 ε-거리 조인 질의 처리를 수행하는 내용을 알고리즘으로 나타낸 것이다.
상기 알고리즘 2는, 제2 ε-거리 조인 질의 처리 모듈에 의해 ε-거리 조인 질의 처리를 수행하는 프로그래밍 코드를 나타낸다. 상기 알고리즘 2에 따르면, 알고리즘 1과 동일하게 제1데이터 세그먼트와 제2데이터 세그먼트의 그룹화 과정이 수행되고, 각각의 인터섹션 노드
도 6에서, 제2 ε-거리 조인 질의 처리 모듈(1242)을 이용하여 처리한 결과를 설명하면 이하와 같다.In FIG. 6, a result of processing using the second ε-distance join
상기 표에 의하면, 제1데이터 세그먼트는
즉 인터섹션 노드인
따라서 상기 수식 결과,
즉
따라서 노드
상기와 같이 각 노드에 대한 ε-거리 조인 질의가 수행된 이후에는, 해당 질의 결과로 얻어진 제2데이터 객체들과, 알고자 하는 제1데이터 세그먼트가 포함되는 노드 시퀀스 상에 위치하는 제2데이터 객체들의 집합이 거리 계산을 하는 대상 객체가 된다.After the ε-distance join query for each node is performed as described above, the second data objects obtained as a result of the query and the second data objects located on the node sequence containing the first data segment to be known are The set of objects becomes the target object for distance calculation.
따라서 상기 표와 같이 제1데이터 세그먼트
마찬가지로, 또다른 제1데이터 세그먼트
상기 제2데이터 객체의 포함 조건에 따른 거리 계산을 나타내는 표에 의하여 거리 계산을 수행함으로써, 제1 데이터 객체와 특정 거리 ε 안에 위치하는 제2 데이터 객체들을 도출할 수 있다.By performing distance calculation according to a table representing distance calculation according to the inclusion condition of the second data object, second data objects located within a specific distance ε from the first data object may be derived.
따라서, 본 발명에 따른 ε-거리 조인 질의를 처리하는 프로그램 혹은 장치의 사용 방법은 이하와 같이 설명할 수 있다. 사용자는 특정 거리 혹은 특정 시간 이내로 사용자에게 도달할 수 있는 서비스 대상 객체를 어플리케이션이나 장치 등에 입력한다. 상기 장치 내에 포함된 질의 결과 연산부에서는 해당 장치 내에 포함된 도로 네트워크를 기반으로 하여 노드를 결정하며, 해당 노드 위에 위치한 데이터 객체들을 검색하고, 상기 기준에 따른 각 데이터 객체들의 세그먼트화를 수행한다. 그 후, 해당 세그먼트들을 기준으로 기준이 되는 세그먼트를 설정하고, 제1 ε-거리 조인 질의 처리 모듈 혹은 제2 ε-거리 조인 질의 처리 모듈을 이용함으로써, 기존에 비해 신속하며 동적인 도로 네트워크 상황을 반영한 실시간 정보 처리가 가능한 효과가 있다. Accordingly, a method of using a program or apparatus for processing an ε-distance join query according to the present invention can be described as follows. The user inputs a service target object that can reach the user within a specific distance or within a specific time in an application or device. The query result calculation unit included in the device determines a node based on the road network included in the device, searches for data objects located on the node, and performs segmentation of each data object according to the criteria. After that, by setting a segment as a reference based on the segments, and using the first ε-distance join query processing module or the second ε-distance join query processing module, the road network situation is faster and more dynamic than before. It has the effect of real-time information processing.
본 기술은, 서비스 매칭 시스템에서 활용될 수 있다. 구체적으로, 어떤 서비스를 제공하고자 할 때, 특정 거리 이내의 서비스를 매칭하는 경우나, 특정 시간 이내로 서비스를 제공받고자 하는 경우에서 용이하게 활용할 수 있다. 보다 구체적으로는, 택시 탑승 시스템 등에서 활용할 수 있다. The present technology can be utilized in a service matching system. Specifically, it can be easily utilized when providing a certain service, matching a service within a specific distance, or receiving a service within a specific time. More specifically, it can be utilized in a taxi boarding system or the like.
도 12 내지 14는 본 발명의 ε-거리 조인 질의 처리 방법을 이용하여 실제 도로 맵 상에서 ε-거리 조인 질의를 수행한 것을 나타내는 그래프이다. 도 12는 캘리포니아(California and Nevada), 도 13은 플로리다(Florida), 도 14는 콜로라도(Colorado)의 로드맵을 이용하여 ε-거리 조인 질의를 수행하였다. 상기 도 12, 도 13, 도 14에서의 도로 네트워크에서 포함되는 노드 시퀀스의 개수는 각각 1794708, 1100675, 374355개에 달한다.12 to 14 are graphs showing the execution of an ε-distance join query on an actual road map using the ε-distance join query processing method of the present invention. 12 is a California (California and Nevada), Figure 13 is Florida (Florida), Figure 14 is performed using the road map of Colorado (Colorado) ε-distance join query. 12, 13, and 14, the number of node sequences included in the road network reaches 1794708, 1100675, and 374355, respectively.
실제 도로 네트워크 상에서의 제1데이터 객체 및 제2데이터 객체의 위치는 중심 또는 균일한 분포를 따른다. 도 12 내지 도 14에서의 (a)는 거리 ε 값을 변화시키는 것에 따른 처리 시간을 나타내는 그래프이며, (b)와 (c)는 제1데이터 세그먼트 및 제2데이터 세그먼트의 개수 변화에 따른 처리 시간을 나타내는 그래프이다. (d)는 객체의 분포를 다양화한 것에 따른 처리 시간을 나타내는 그래프에 해당한다.The positions of the first data object and the second data object on the actual road network follow a center or a uniform distribution. 12 to 14, (a) is a graph showing the processing time according to changing the distance ε value, and (b) and (c) are the processing time according to the change in the number of first and second data segments. It is a graph showing (d) corresponds to a graph showing the processing time according to the diversification of the distribution of objects.
도 12 내지 도 14를 살펴보면, 전체적인 그래프의 경향성이 유사하게 나타나는 것을 확인할 수 있다. 상기 그래프들에 따르면, ε-거리 조인 질의를 모든 제1데이터 객체에 대해 수행했을 경우와, 제1 ε-거리 조인 질의 처리 모듈에 의해 수행된 경우 및 제2 ε-거리 조인 질의 처리 모듈에 의해 수행된 경우의 세 가지 방법으로 수행한 결과 그래프를 비교하고 있다. 그래프들에 따르면, ε-거리 조인 질의를 수행하는 처리 시간이 모든 제1데이터 객체에 대해 수행했을 경우가 가장 오랜 시간이 걸리며, 그 다음이 제1 ε-거리 조인 질의 처리에 의해 수행된 경우이며, 처리 시간이 가장 적게 걸리는 방법은 제2 ε-거리 조인 질의 처리에 의해 수행된 경우임을 확인할 수 있다. 즉, 상기 그래프를 통해 본 발명에서 제시하고 있는 ε-거리 조인 질의 처리 방법이 기존의 방법에 비해 처리 시간의 측면에서 효율적임을 확인할 수 있다.12 to 14, it can be seen that the trend of the overall graph is similar. According to the graphs, when an ε-distance join query is performed for all first data objects, a case performed by the first ε-distance join query processing module, and a second ε-distance join query processing module, The graphs of the results performed by the three methods in the case of performed are compared. According to the graphs, the longest processing time for executing an ε-distance join query is performed for all the first data objects, followed by the first ε-distance join query processing time. , It can be seen that the method that takes the least processing time is the case performed by the second ε-distance join query processing. That is, through the graph, it can be seen that the ε-distance join query processing method proposed in the present invention is more efficient in terms of processing time than the conventional method.
본 발명의 일 실시예에 따른 최단 경로 탐색 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical mεdia), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 본 발명의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.The shortest path search method according to an embodiment of the present invention may be implemented in the form of a program command that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like alone or in combination. The program instructions recorded on the medium may be specially designed and configured for the present invention, or may be known and usable to those skilled in computer software. Examples of computer-readable recording media include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical media such as CD-ROMs and DVDs, and magnetic media such as floptical disks. -An optical medium (magneto-optical mεdia), and a hardware device specially configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of the program instructions include not only machine language codes such as those produced by a compiler, but also high-level language codes that can be executed by a computer using an interpreter or the like. The above-described hardware device may be configured to operate as one or more software modules to perform the operation of the present invention, and vice versa.
이상의 실시예들은 본 발명의 이해를 돕기 위하여 제시된 것으로, 본 발명의 범위를 제한하지 않으며, 이로부터 다양한 변형 가능한 실시예들도 본 발명의 범위에 속하는 것임을 이해하여야 한다. 본 발명의 기술적 보호범위는 특허청구범위의 기술적 사상에 의해 정해져야 할 것이며, 본 발명의 기술적 보호범위는 특허청구범위의 문언적 기재 그 자체로 한정되는 것이 아니라 실질적으로는 기술적 가치가 균등한 범주의 발명까지 미치는 것임을 이해하여야 한다.It should be understood that the above embodiments have been presented to aid the understanding of the present invention, and do not limit the scope of the present invention, and various deformable embodiments are also within the scope of the present invention. The technical protection scope of the present invention should be determined by the technical idea of the claims, and the technical protection scope of the present invention is not limited to the literal description of the claims itself, but a scope that has substantially equal technical value. It should be understood that it extends to the invention of.
100 : ε-거리 조인 질의 처리 장치
110 : 수신부
120 : 질의 결과 연산부
121 : 노드 결정 모듈
122 : 데이터 객체 검색 모듈
123 : 그룹화 모듈
124 : 질의 결과 처리 모듈
130 : 전송부
1241 : 제1 ε-거리 조인 질의 처리 모듈
1242 : 제2 ε-거리 조인 질의 처리 모듈
1243 : 제1 저장 모듈
1244 : 제2 저장 모듈
1245 : 거리 계산 모듈100: ε-distance join query processing unit
110: receiver
120: query result operator
121: node determination module
122: data object search module
123: grouping module
124: Query result processing module
130: transmission unit
1241: First ε-distance join query processing module
1242: The second ε-distance join query processing module
1243: first storage module
1244: second storage module
1245: distance calculation module
Claims (16)
제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 또는 제2데이터 세그먼트의 집합으로 정의하는 단계;
상기 정의된 제1데이터 세그먼트 내에 포함된 일부의 제1데이터 객체들에 대해 ε-거리 조인 질의를 수행하는 단계;
상기 정의된 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 상기 ε-거리 조인 질의와 상이한 거리 계산 방법을 이용하여 일정 거리 ε 안에 위치하는 객체를 도출하는 단계;를 포함하는 ε-거리 조인 질의 처리 방법.
In a device that processes an ε-distance join query on a road network, an object located within a certain distance ε from an object included in one of the first data set R and the second data set S on the road network is transferred to another data set. As a method of processing an ε-distance join query selected from an existing object,
Defining first data objects included in the first data set R or second data objects included in the second data set S as a set of first data segments or a set of second data segments, respectively;
Performing an ε-distance join query for some of the first data objects included in the defined first data segment;
Deriving an object located within a predetermined distance ε using a distance calculation method different from the ε-distance join query for the remaining first data objects included in the defined first data segment; ε-distance join including How to process queries.
제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 및 제2데이터 세그먼트의 집합으로 정의하는 단계는,
상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 단계;
상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제1데이터 객체들을 잇는 시퀀스를 제1데이터 세그먼트로 정의하는 단계; 및
상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들을 잇는 시퀀스를 제2데이터 세그먼트로 정의하는 단계;를 포함하는 ε-거리 조인 질의 처리 방법.
The method of claim 1,
Defining the first data objects included in the first data set R or the second data objects included in the second data set S as a set of first data segments and a set of second data segments, respectively,
Determining the number of road segments intersecting based on the nodes on the road network;
Defining, as a first data segment, a sequence of first data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node; And
Ε-distance including: defining a sequence of second data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node as a second data segment; How to handle join queries.
상기 제1데이터 세그먼트에 포함되는 제1데이터 객체의 개수가 1개 혹은 2개일 경우,
각각의 제1데이터 객체에 대한 ε-거리 조인 질의 처리를 수행하는 ε-거리 조인 질의 처리 방법.
The method of claim 2,
When the number of first data objects included in the first data segment is 1 or 2,
An ε-distance join query processing method that performs ε-distance join query processing for each first data object.
상기 제1데이터 세그먼트에 포함되는 제1데이터 객체의 개수가 3개 이상일 경우,
상기 제1데이터 세그먼트의 양 끝단에 위치하는 2개의 제1데이터 객체에 대한 ε-거리 조인 질의 처리를 수행하는 단계; 및
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 제1데이터 세그먼트의 내부에 포함된 나머지 제1데이터 객체들에 대해 거리 계산을 수행하는 단계; 를 포함하는 ε-거리 조인 질의 처리 방법.
The method of claim 2,
When the number of first data objects included in the first data segment is 3 or more,
Performing ε-distance join query processing for two first data objects located at both ends of the first data segment; And
Performing a distance calculation on the remaining first data objects included in the first data segment excluding the first data objects positioned at both ends of the first data segment; Ε-distance join query processing method comprising a.
상기 거리 계산을 수행하는 단계는,
상기 제1데이터 세그먼트 내부에 포함된 제2데이터 객체들을 추출하는 단계;
상기 제1데이터 세그먼트의 양 끝단에 위치하는 2개의 제1데이터 객체들에 대한 ε-거리 조인 질의 처리로 도출된 거리 ε 이내의 제2데이터 객체들을 추출하는 단계;
상기 추출된 제2데이터 객체들의 집합을 정의하는 단계;
상기 내부에 포함된 나머지 제1데이터 객체들에 대해, 상기 정의된 제2데이터 객체들의 집합에 포함된 제2데이터 객체들을 대상으로 거리를 측정하여 상기 내부에 포함된 나머지 제1데이터 객체들과 거리 ε 이내에 위치하는 제2데이터 객체를 추출하는 단계; 를 포함하는 ε-거리 조인 질의 처리 방법.
The method of claim 4,
The step of performing the distance calculation,
Extracting second data objects included in the first data segment;
Extracting second data objects within a distance ε derived by processing an ε-distance join query for two first data objects located at both ends of the first data segment;
Defining a set of the extracted second data objects;
With respect to the remaining first data objects included in the interior, a distance is measured with respect to the second data objects included in the defined set of second data objects, and a distance from the remaining first data objects included in the interior extracting a second data object located within ε; Ε-distance join query processing method comprising a.
제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 및 제2데이터 세그먼트의 집합으로 정의하는 단계;
상기 도로 네트워크 상의 임의의 한 노드에 근접한 제1데이터 세그먼트들을 추출하는 단계;
제1데이터 집합 R에 포함된 제1데이터 객체들 또는 제2데이터 집합 S에 포함된 제2데이터 객체들을 각각 제1데이터 세그먼트의 집합 및 제2데이터 세그먼트의 집합으로 정의하는 단계는,
상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 단계;
상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제1데이터 객체들을 잇는 시퀀스를 제1데이터 세그먼트로 정의하는 단계; 및
상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들을 잇는 시퀀스를 제2데이터 세그먼트로 정의하는 단계;를 포함하고,
상기 노드에 근접한 제1데이터 세그먼트의 개수가 2개 이상일 경우 상기 노드를 기준으로 ε-거리 조인 질의 처리를 수행하는 단계;를 포함하는 ε-거리 조인 질의 처리 방법.
In a device that processes an ε-distance join query on a road network, an object located within a certain distance ε from an object included in one of the first data set R and the second data set S on the road network is transferred to another data set. As a method of processing an ε-distance join query selected from an existing object,
Defining first data objects included in the first data set R or second data objects included in the second data set S as a set of first data segments and a set of second data segments, respectively;
Extracting first data segments adjacent to any one node on the road network;
Defining the first data objects included in the first data set R or the second data objects included in the second data set S as a set of first data segments and a set of second data segments, respectively,
Determining the number of road segments intersecting based on the nodes on the road network;
Defining, as a first data segment, a sequence of first data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node; And
Including, as a second data segment, a sequence of connecting second data objects included on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node, as a second data segment,
Ε-distance join query processing method comprising; if the number of first data segments adjacent to the node is two or more, performing ε-distance join query processing based on the node.
상기 임의의 한 노드는 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 3개 이상인 노드인 것을 특징으로 하는 ε-거리 조인 질의 처리 방법.
The method of claim 6,
The arbitrary node is an ε-distance join query processing method, characterized in that the number of road segments intersecting with respect to the node is three or more.
상기 임의의 한 노드에 근접한 제1데이터 세그먼트에 대한 ε-거리 조인 질의 처리 방법은,
상기 노드를 기준으로 ε-거리 조인 질의 처리를 수행하여 도출된 제2데이터 객체와, 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들의 집합을 도출하여,
상기 도로 세그먼트 상에 포함되는 제1데이터 세그먼트 내의 제1데이터 객체와 상기 제2데이터 객체들의 집합에 포함된 객체들과의 거리를 계산하여 거리 ε 내에 위치하는 제2데이터 객체를 추출하는 ε-거리 조인 질의 처리 방법.
The method of claim 7,
The ε-distance join query processing method for a first data segment close to one node
A second data object derived by performing ε-distance join query processing based on the node, and a second data object included on the road segment connected by nodes having one or three or more road segments crossing the node 2 Derive a set of data objects,
Ε-distance for extracting a second data object located within a distance ε by calculating the distance between the first data object in the first data segment included on the road segment and the objects included in the set of second data objects How to handle join queries.
상기 제1데이터 세그먼트의 개수는, 제2데이터 세그먼트의 개수보다 적은 것을 특징으로 하는 ε-거리 조인 질의 처리 방법.
The method according to any one of claims 1 to 8,
The number of the first data segment is less than the number of the second data segment ε-distance join query processing method.
상기 ε-거리 조인 질의 처리 방법을 실행하기 위한 프로그램이 기록되어 있는 것을 특징으로 하는 컴퓨터에서 판독 가능한 기록 매체.
The method of claim 9,
A computer-readable recording medium, wherein a program for executing the ?-distance join query processing method is recorded.
상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 연산하는 질의 결과 연산부; 및
상기 요청에 응답하여, 상기 단말의 위치를 기준으로 하는 ε-거리 조인 질의 처리 결과를 상기 단말로 전송하는 전송부; 를 포함하고
상기 질의 결과 연산부는 제1데이터 집합 R에 포함된 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 집합 S에 포함된 제2데이터 객체들을 제2데이터 세그먼트로 정의하고, 상기 제1데이터 세그먼트 내에 포함된 2개의 제1데이터 객체에 대해 ε-거리 조인 질의를 수행하고, 상기 제1데이터 세그먼트 내에 포함된 나머지 제1데이터 객체에 대해 상기 ε-거리 조인 질의와 상이한 거리 계산 방법을 이용하여 일정 거리 ε 안에 위치하는 객체를 도출하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
A receiving unit for receiving an ε-distance join query request for at least one object from a client terminal;
In response to the request, a query result calculator for calculating an ε-distance join query processing result based on the location of the terminal; And
In response to the request, a transmission unit for transmitting a result of processing an ε-distance join query based on the location of the terminal to the terminal; Including
The query result operator defines first data objects included in the first data set R as a first data segment, and defines second data objects included in the second data set S as a second data segment, and Performs an ε-distance join query on two first data objects included in a data segment, and uses a distance calculation method different from the ε-distance join query for the remaining first data objects included in the first data segment. A device that processes an ε-distance join query on a road network that derives an object located within a certain distance ε.
상기 질의 결과 연산부는,
상기 도로 네트워크 상의 노드를 기준으로 교차하는 도로 세그먼트의 개수를 판별하는 노드 결정 모듈;
상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체 및 제2데이터 객체를 검색하는 데이터 객체 검색 모듈;
상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 위치하는 제1데이터 객체들을 제1데이터 세그먼트로 정의하고, 제2데이터 객체들은 제2데이터 세그먼트로 정의하는 그룹화 모듈;
상기 그룹화 모듈에서 생성된 제1데이터 세그먼트에 대해 ε-거리 조인 질의 처리를 수행하는 질의 결과 처리 모듈;을 포함하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
The method of claim 11,
The query result operation unit,
A node determination module for determining the number of road segments intersecting based on the nodes on the road network;
A data object search module for searching for a first data object and a second data object located on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node determined in the node determination module;
First data objects located on a road segment connected by nodes having one or three or more road segments intersecting with respect to the node determined in the node determination module are defined as a first data segment, and the second data objects are A grouping module defining a second data segment;
A query result processing module that performs ε-distance join query processing on the first data segment generated by the grouping module; and an apparatus for processing ε-distance join query on a road network.
상기 질의 결과 처리 모듈은,
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체에 대한 연산을 진행하는 제1 ε-거리 조인 질의 처리 모듈;
상기 제1 ε-거리 조인 질의 처리 모듈의 처리 결과에 따른 거리 ε 이내에 위치하는 제2데이터 객체들을 저장하는 제1 저장 모듈; 및
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체에 대해 거리 계산을 수행하는 거리 계산 모듈;을 포함하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
The method of claim 12,
The query result processing module,
A first ε-distance join query processing module that performs an operation on a first data object located at both ends of the first data segment;
A first storage module for storing second data objects located within a distance ε according to a processing result of the first ε-distance join query processing module; And
A distance calculation module that calculates a distance on a first data object included inside excluding a first data object located at both ends of the first data segment; and processes an ε-distance join query on a road network including: Device.
제1데이터 세그먼트에 포함된 제2데이터 객체들을 저장하는 제2 저장 모듈;을 더 포함하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
The method of claim 13,
A second storage module for storing second data objects included in the first data segment; and an apparatus for processing an ε-distance join query on a road network.
상기 거리 계산 모듈;은
상기 제1데이터 세그먼트의 양 끝단에 위치하는 제1데이터 객체를 제외한 내부에 포함된 제1데이터 객체에 대해 상기 제1 저장 모듈 및 제2 저장 모듈에 저장된 제2데이터 객체들과의 거리를 계산하는 것을 특징으로 하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
The method of claim 14,
The distance calculation module;
Calculating a distance between the first data objects included in the first data object excluding the first data objects located at both ends of the first data segment and the second data objects stored in the first storage module and the second storage module An apparatus for processing an ε-distance join query on a road network, characterized in that.
상기 질의 결과 처리 모듈은,
상기 노드 결정 모듈에서 결정된 노드를 기준으로 교차하는 도로 세그먼트의 개수가 3개 이상인 노드를 기준으로 인접하는 제1데이터 세그먼트의 개수가 2개 이상인 경우, 해당 노드에 대해 ε-거리 조인 질의를 수행하고, 그 결과로 나타나는 제2데이터 객체와, 상기 노드를 기준으로 교차하는 도로 세그먼트의 개수가 1개 혹은 3개 이상인 노드끼리 이어진 도로 세그먼트 상에 포함된 제2데이터 객체들과 제1데이터 객체와의 거리를 계산하여 거리 ε 이내에 위치하는 데이터 객체를 추출하는 제2 ε-거리 조인 질의 처리 모듈;을 더 포함하는 도로 네트워크 상에서 ε-거리 조인 질의를 처리하는 장치.
The method of claim 15,
The query result processing module,
If the number of adjacent first data segments is 2 or more based on a node whose number of road segments crossing based on the node determined in the node determination module is 3 or more, an ε-distance join query is performed for the node. , The resulting second data object and the first data object and second data objects included on the road segment connected by nodes having one or three or more road segments crossing the node A second ε-distance join query processing module that calculates the distance and extracts data objects located within the distance ε. The apparatus further comprises an ε-distance join query on a road network.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020190002841A KR102185334B1 (en) | 2019-01-09 | 2019-01-09 | PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020190002841A KR102185334B1 (en) | 2019-01-09 | 2019-01-09 | PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20200086529A KR20200086529A (en) | 2020-07-17 |
| KR102185334B1 true KR102185334B1 (en) | 2020-12-01 |
Family
ID=71832334
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020190002841A KR102185334B1 (en) | 2019-01-09 | 2019-01-09 | PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR102185334B1 (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR102416960B1 (en) * | 2020-10-30 | 2022-07-05 | 경북대학교 산학협력단 | Group processing method of multiple k-farthest neighbor queries in road networks and device that group processes multiple k-farthest neighbor queries in road networks |
| WO2022149625A1 (en) * | 2021-01-06 | 2022-07-14 | 주식회사 플럭시티 | Method, device, and computer-readable recording medium for configuring and utilizing space information of three-dimensional modeling data |
| KR102688112B1 (en) * | 2021-03-29 | 2024-07-25 | 주식회사 씨엠월드 | Method for clustering objects for geospatial information modeling and apparatus therefor |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100736225B1 (en) * | 2005-10-31 | 2007-07-06 | 한국과학기술원 | Method for finding nearest neighbors on a path |
| KR101025360B1 (en) * | 2009-04-22 | 2011-03-28 | 제주대학교 산학협력단 | Method and apparatus for finding shortest path for k-nearest neighbor searching in road network databases |
| KR101423031B1 (en) * | 2012-08-22 | 2014-08-14 | 아주대학교산학협력단 | A method for computing safe exit points of moving k-nearest neighbor queries in road networks |
| KR20140028935A (en) * | 2012-08-31 | 2014-03-10 | 전북대학교산학협력단 | K-nearest neighbour query processing method and system |
-
2019
- 2019-01-09 KR KR1020190002841A patent/KR102185334B1/en active IP Right Grant
Also Published As
| Publication number | Publication date |
|---|---|
| KR20200086529A (en) | 2020-07-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10520326B2 (en) | Driving route matching method and apparatus, and storage medium | |
| CN110008413B (en) | Traffic travel problem query method and device | |
| KR102185334B1 (en) | PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS | |
| CN110516702B (en) | Discrete path planning method based on streaming data | |
| KR101896993B1 (en) | Method and Apparatus for deciding path of vehicle | |
| CN108827335B (en) | Shortest path planning method based on one-way search model | |
| TW201342850A (en) | Path searching method and path search device | |
| CN108091134B (en) | Universal data set generation method based on mobile phone signaling position track data | |
| CN107917716B (en) | Fixed line navigation method, device, terminal and computer readable storage medium | |
| CN110750853B (en) | Road network continuous K neighbor query method based on direction constraint | |
| US9752888B2 (en) | Method and apparatus of computing location of safe exit for moving range query in road network | |
| CN112213113A (en) | Method for selecting and planning real road test scene of intelligent driving mobile device | |
| KR102127769B1 (en) | Processing method of k-nearest neighbor join queries in road networks and device that processes k-nearest neighbor join queries in road networks | |
| KR101025360B1 (en) | Method and apparatus for finding shortest path for k-nearest neighbor searching in road network databases | |
| EP4089371A1 (en) | Navigation system with personal preference analysis mechanism and method of operation thereof | |
| CN109974732B (en) | Top-k multi-request path planning method based on semantic perception | |
| CN114253975A (en) | Load-aware road network shortest path distance calculation method and device | |
| He et al. | Exploring public transport transfer opportunities for pareto search of multicriteria journeys | |
| CN108280548A (en) | Intelligent processing method based on network transmission | |
| Miao et al. | On efficiently monitoring continuous aggregate k nearest neighbors in road networks | |
| US20160091326A1 (en) | Analysis method and analyzing device | |
| CN114245329B (en) | Traffic mode identification method, device, equipment and storage medium | |
| Khan et al. | Roadcrowd: an approach to road traffic forecasting at junctions using crowd-sourcing and Bayesian model | |
| KR102416960B1 (en) | Group processing method of multiple k-farthest neighbor queries in road networks and device that group processes multiple k-farthest neighbor queries in road networks | |
| KR102347617B1 (en) | Method of providing traffic information service and system performing the same |
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 |