| 1 |
1
예측 질의 처리 시스템이 사용자에 의해 요청된 예측 질의를 처리하는 방법으로서,임의의 정점에 위치하며 상기 예측 질의를 수행한 상기 사용자의 질의 위치와, 상기 정점을 포함하여 복수의 정점들, 상기 복수의 정점들 중 두 정점을 연결하는 간선들로 구성된 도로 교통망 그래프를 토대로 도로 교통망에 위치한 복수의 이동 객체 각각의 위치와 속력 정보를 수신하는 단계,상기 질의 위치와 복수의 정점들을 포함하는 질의 큐를 생성하는 단계,상기 큐를 토대로 복수의 이동 객체 각각에 대하여 상기 질의 위치로부터 이웃 정점으로 사용자가 이동하는데 걸리는 시간 동안 상기 복수의 이동 객체가 상기 질의 위치로 도달할 시간을 기초로 상기 복수의 이동 객체 각각에 대한 이동 객체 점수를 계산하는 단계, 그리고상기 이동 객체 점수가 높은 적어도 하나의 이동 객체들의 정보를 질의 결과 리스트로 생성하여 상기 사용자에게 반환하는 단계를 포함하는 예측 질의 처리 방법
|
| 2 |
2
제1항에 있어서,상기 질의 큐를 생성하는 단계는,상기 사용자의 질의 위치를 큐에 삽입하는 단계, 그리고상기 질의 위치에 해당하는 정점에서 거리가 가까운 인접 정점들 순서로 상기 큐에 삽입하여 상기 질의 큐로 생성하는 단계를 포함하는 예측 질의 처리 방법
|
| 3 |
3
제2항에 있어서,상기 이동 객체 점수를 계산하는 단계는,상기 복수의 이동 객체 각각의 위치에서 상기 질의 위치로 도달하는 최단 경로를 확인하는 단계,상기 복수의 이동 객체 각각에 대해, 상기 사용자가 상기 질의 위치에서 인접한 정점으로 이동할 경우 상기 복수의 이동 객체들과 만나게 되는 적어도 하나의 후보 정점들을 확인하는 단계, 그리고상기 적어도 하나의 후보 정점들 각각에 대하여 상기 사용자가 상기 후보 정점들로 이동하는데 걸리는 시간과, 상기 후보 정점들에서 상기 복수의 이동 객체들을 만나기 위해 대기하는 시간을 토대로 이동 객체 점수를 계산하는 단계를 포함하는 예측 질의 처리 방법
|
| 4 |
4
제3항에 있어서,상기 사용자에게 반환하는 단계는,상기 질의 결과 리스트에 포함된 적어도 하나의 이동 객체들에 대하여, 현재 이동 객체의 위치에 대응하는 정점과 상기 사용자의 질의 위치 사이의 네트워크 거리를 이동 객체들에 대한 상계 점수로 계산하는 단계를 포함하는 예측 질의 처리 방법
|
| 5 |
5
제4항에 있어서,상기 상계 점수가 상기 질의 결과 리스트에 포함된 이동 객체들의 이동 객체 점수보다 낮으면, 상기 현재 이동 객체의 위치에 대응하는 정점에 대한 위치 확장을 중단하는 예측 질의 처리 방법
|
| 6 |
6
예측 질의 처리 시스템이 사용자에 의해 요청된 예측 질의를 처리하는 방법으로서,사용자 또는 복수의 이동 객체가 위치할 수 있는 복수의 정점들, 상기 복수의 정점들 각각에 대해 두 정점을 연결하는 간선들로 구성된 도로 교통망 그래프로부터, 정점의 수가 미리 설정한 개수 이하가 되도록 복수의 서브 그래프들을 구성하는 단계,상기 복수의 서브 그래프 중 하나인 제1 서브 그래프와 제2 서브 그래프를 연결할 수 있는 경계점을 확인하고, 상기 경계점에 대한 최단 경로를 계산하는 단계,상기 복수의 정점들 중 임의의 정점에 위치한 사용자가 예측 질의를 수행하면, 상기 임의의 정점을 포함하는 서브 그래프 내에 이동 객체가 존재하는지 확인하는 단계,상기 이동 객체가 존재하면 이동 객체에 대한 이동 객체 점수를 계산하여 질의 결과 리스트로 생성하여 상기 사용자에게 반환하는 단계를 포함하는 예측 질의 처리 방법
|
| 7 |
7
제6항에 있어서,상기 경계점은 상기 제1 서브 그래프에 포함된 정점들 중 상기 제2 서브 그래프에 포함된 어느 하나의 정점과 연결되는 간선을 가지는 정점을 경계점으로 하는 예측 질의 처리 방법
|
| 8 |
8
제6항에 있어서,상기 이동 객체가 존재하는지 확인하는 단계는,상기 이동 객체가 상기 서브 그래프에 존재하지 않으면, 이웃한 복수의 후보 서브 프레임들 각각의 상계 점수를 계산하는 단계를 포함하는 예측 질의 처리 방법
|
| 9 |
9
제8항에 있어서,상기 상계 점수를 계산하는 단계는,상기 후보 서브 프레임들의 경계점 집합을 확인하는 단계,경계점 집합에 존재하는 적어도 하나의 정점들 중 어느 하나의 정점에 각각 위치한 이동 객체들의 속력을 토대로 가장 빠른 대상 이동 객체를 확인하는 단계, 그리고상기 경계점 집합에 포함된 모든 정점들에 대해 상기 대상 이동 객체의 상계 점수를 후보 서브 프레임의 상계 점수로 선택하는 단계를 포함하는 예측 질의 처리 방법
|
| 10 |
10
예측 질의를 처리하는 시스템으로서,사용자 또는 복수의 이동 객체가 위치할 수 있는 복수의 정점들, 두 정점 사이의 도로 구간을 의미하며 상기 두 정점을 연결하는 간선들로 구성된 도로 교통망 그래프를 저장하고, 상기 복수의 이동 객체의 위치와 속도 정보를 수집하는 도로 교통망 그래프 저장부,상기 복수의 정점 중 어느 하나의 정점에서 상기 사용자가 질의하면, 상기 어느 하나의 정점의 위치를 질의 위치로 수신하는 도로 교통망 그래프의 질의 위치 수신부,상기 질의 위치를 임의의 큐에 삽입하고, 상기 질의 위치로부터 거리가 가까운 정점 순서대로 큐에 삽입하여, 상기 복수의 정점들에 대한 정점 큐를 생성하는 정점 큐 생성부,상기 질의 위치로부터 이웃 정점으로 사용자가 이동하는데 걸리는 시간 동안 상기 복수의 이동 객체가 상기 질의 위치로 도달할 시간을 토대로 이동 객체 점수를 계산하는 이동 객체 점수 계산부, 그리고이동 객체 점수가 높은 적어도 하나의 이동 객체들을 포함하는 질의 결과 리스트를 생성하고, 생성한 질의 결과 리스트를 상기 사용자에게 질의 결과로 반환하는 질의 결과 반환부를 포함하는 예측 질의 처리 시스템
|
| 11 |
11
제10항에 있어서,상기 이동 객체 점수 계산부는,상기 사용자가 복수의 이동 객체 중 하나인 제1 이동 객체를 이용하기 위하여, 상기 복수의 정점 중 어느 하나의 정점까지 이동하는데 걸리는 시간과, 상기 어느 하나의 정점에서 상기 제1 이동 객체를 만나기 위해 대기하는 시간을 토대로 상기 제1 이동 객체의 이동 객체 점수를 계산하는 예측 질의 처리 시스템
|
| 12 |
12
제11항에 있어서,상기 이동 객체 점수 계산부는,상기 제1 이동 객체가 초기 위치에서 상기 어느 하나의 정점에 도달할 확률을 계산하는 예측 질의 처리 시스템
|
| 13 |
13
제12항에 있어서,상기 확률은 상기 어느 하나의 정점과 연결된 적어도 하나의 정점들 중, 상기 제1 이동 객체가 방문하지 않은 정점의 수로 계산되고,상기 계산된 확률이 미리 설정한 임계값 보다 낮은지 판단하여 상기 제1 이동 객체에 대한 이동 범위를 확장하는 예측 질의 처리 시스템
|
| 14 |
14
제13항에 있어서,상기 이동 객체 점수 계산부는,상기 질의 결과 리스트에 포함되어 있는 적어도 하나의 이동 객체들에 대하여, 유클리드 거리 계산 방법으로 상계 점수를 계산하는 예측 질의 처리 시스템
|
| 15 |
15
제10항에 있어서,상기 도로 교통망 그래프 저장부는 상기 도로 교통망 그래프를 복수의 서브 그래프로 구성하고, 상기 복수의 서브 그래프 중 제1 서브 그래프에서 제2 서브 그래프 각각에 포함된 경계점들 및 상기 경계점들 각각에 대한 최단 경로를 계산하는 예측 질의 처리 시스템
|
| 16 |
16
제15항에 있어서,상기 경계점은 상기 제1 서브 그래프에 포함된 정점 중 상기 제2 서브 그래프에 포함된 정점과 연결되는 간선을 가지는 정점인 예측 질의 처리 시스템
|
