1 |
1
예측 질의 처리 시스템이 사용자에 의해 요청된 예측 질의를 처리하는 방법으로서,사용자가 경로를 탐색하기 위해 예측 질의를 수행한 질의 위치, 목적지 정점 위치, 상기 예측 질의를 수행한 경로 탐색 시간 및 타임 슬롯을 수신하는 단계,상기 타임 슬롯을 토대로 상기 경로 탐색 시간의 타임 구간을 확인하는 단계,상기 질의 위치에서 목적지 정점 위치까지의 복수의 경로 각각에 대해, 상기 확인한 타임 구간과 미리 저장되어 있는 상기 사용자의 선호도 정보를 토대로 경로 비용을 계산하는 단계, 그리고복수의 경로 각각에 대해 계산된 경로 비용들 중 가장 작은 경로 비용으로 계산된 경로를 상기 사용자에게 반환하는 단계를 포함하는 예측 질의 처리 방법
|
2 |
2
제1항에 있어서,상기 경로 비용을 계산하는 단계는,상기 질의 위치의 정점 비용과, 상기 질의 위치에서 목적지 정점 사이에 존재하는 복수의 정점들 각각의 정점 비용을 미리 설정한 규칙에 따라 초기화하는 단계를 포함하는 예측 질의 처리 방법
|
3 |
3
제2항에 있어서,상기 경로 비용을 계산하는 단계는,상기 질의 위치에서 상기 복수의 정점들 각각까지의 경로 비용을 상기 타임 슬롯에 의해 형성되는 시간 구간대마다 계산하는 예측 질의 처리 방법
|
4 |
4
제3항에 있어서,상기 경로 비용을 계산하는 단계는,상기 복수의 정점들 중 제1 정점에 도착한 시간이 제1 시간인 경우의 제1 경로 비용을 계산하여 제1 점수 리스트에 포함시키는 단계,제2 정점에서 제2 시간에 출발해 상기 제1 정점에 제1 시간 구간에 이동 객체가 도착한 경우의 경로 비용을 계산하는 단계,상기 제2 정점에 상기 제2 시간에 도착한 경우의 제2 경로 비용을 계산하여 제2 점수 리스트에 포함시키는 단계를 포함하고,상기 제1 시간 구간은 상기 제1 시간이 타임 슬롯에 의해 형성되는 시간 구간대 중 상기 제1 시간에 대응하는 시간 구간인 예측 질의 처리 방법
|
5 |
5
제4항에 있어서,상기 제1 정점에 도착하는 제1 시간대의 점수 리스트의 비용이 상기 경로 비용과 제2 시간대의 점수 리스트의 비용 합보다 작으면, 상기 제1 정점에 도착하는 제1 시간대의 점수 리스트의 비용이 상기 경로 비용과 제2 시간대의 점수 리스트의 비용 합으로 갱신하는 예측 질의 처리 방법
|
6 |
6
예측 질의 처리 시스템이 사용자에 의해 요청된 예측 질의를 처리하는 방법으로서,사용자 또는 복수의 이동 객체가 위치할 수 있는 복수의 정점들, 상기 복수의 정점들 각각에 대해 두 정점을 연결하는 간선들로 구성된 도로 교통망 그래프로부터, 정점의 수가 미리 설정한 개수 이하가 되도록 복수의 서브 그래프들을 구성하는 단계,사용자가 경로를 탐색하기 위해 예측 질의를 수행한 질의 위치, 목적지 정점 위치, 상기 예측 질의를 수행한 경로 탐색 시간 및 타임 슬롯을 수신하는 단계,상기 복수의 서브 그래프들 각각에 대하여 상기 질의 위치와 목적지 정점 위치를 토대로 하한 비용을 계산하는 단계, 그리고상기 계산한 하한 비용 중 최저 하한 비용이 계산된 경로를 최적 경로로 제공하는 단계를 포함하는 예측 질의 처리 방법
|
7 |
7
제6항에 있어서,상기 서브 그래프들을 구성하는 단계는,상기 복수의 서브 그래프들에 속한 간선의 속성 중 상기 타임 슬롯에 의해 형성된 시간 구간에서 가장 작은 속성 값을 찾아 상기 서브 그래프 각각의 속성 리스트로 저장하는 예측 질의 처리 방법
|
8 |
8
제6항에 있어서,상기 하한 비용을 계산하는 단계는,상기 질의 위치와 목적지 정점의 공통 조상 정점을 검색하는 단계, 그리고상기 공통 조상 정점을 검색하는 과정에서 확인된 적어도 하나의 정점들 각각에 대한 서브 그래프를 서브 그래프로 이루어진 경로로 정의하는 단계를 더 포함하는 예측 질의 처리 방법
|
9 |
9
예측 질의를 처리하는 시스템으로서,사용자 또는 복수의 이동 객체가 위치할 수 있는 복수의 정점들, 두 정점 사이의 도로 구간을 의미하며 상기 두 정점을 연결하는 간선들로 구성된 도로 교통망에서, 상기 복수의 정점 중 어느 하나의 정점에서 상기 사용자가 질의하면, 상기 어느 하나의 정점의 위치를 질의 위치로 하고, 목적지 정점, 질의 시간 그리고 타임 슬롯을 입력 정보로 수신하는 정보 수신부,상기 도로 교통망 정보와 사용자 선호도 정보를 저장하는 정보 저장부, 그리고상기 질의 시간과 타임 슬롯으로부터 확인된 시간 구간에 대하여 상기 정보 저장부에 저장된 사용자 선호도 정보를 확인하고, 상기 질의 위치에서 목적지 정점까지의 복수의 경로들 각각에 대하여 상기 사용자 선호도 정보가 반영되도록 경로 비용을 각각 계산하고, 가장 작은 경로 비용으로 계산된 경로를 추천 경로로서 상기 사용자에게 제공하는 경로 비용 계산부를 포함하는 예측 질의 처리 시스템
|
10 |
10
제9항에 있어서,상기 정보 저장부에 저장된 도로 교통망 정보를 이용하여 정점의 수가 미리 설정한 수 이하로 포함되도록 복수의 서브 그래프를 생성하는 지트리 생성부를 더 포함하는 예측 질의 처리 시스템
|
11 |
11
제10항에 있어서,상기 지트리 생성부는,상기 복수의 서브 그래프들에 속한 간선의 속성 중 상기 타임 슬롯에 의해 형성된 시간 구간에서 가장 작은 속성 값을 찾아 상기 서브 그래프 각각의 속성 리스트로 저장하는 예측 질의 처리 시스템
|