1 |
1
정해진 경로 상의 임의의 지점에서 가장 가까운 소정 개수의 객체를 검색하는 최근접 객체 검색 방법에 있어서, 도로 네트워크에 대한 객체정보 데이터베이스 및 경로 상의 적어도 3점 이상이 만나는 교차점에 대한 소정 개수의 최근접 객체정보와 해당 최근접 객체의 거리 정보를 갖는 최근접 객체정보 데이터베이스를 구축하는 제 1 과정; 및 사용자로부터 소정 개수의 최근접 객체정보를 요청하는 질의 경로를 입력받아 상기 질의 경로를 복수 개의 서브 경로로 분할하고, 분할된 서브 경로의 유효 구간에 대한 최근접 객체정보를 상기 객체정보 데이터베이스 및 최근접 객체정보 데이터베이스로부터 검색하여 사용자에게 제공하는 제 2 과정; 을 포함하여 이루어지는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
2 |
2
제 1 항에 있어서, 상기 제 2 과정은 사용자로부터의 질의 경로를 복수 개의 서브 경로로 분할하는 제 1 단계; 상기 분할된 각 서브 경로에 대하여 유효 구간을 결정하여 해당 유효 구간에 대하여, 사용자의 질의에 따른 소정 개수의 최근접 객체를 찾아 이로부터 해당 서브 경로에 대한 사용자의 질의에 대응하는 최근접 객체정보를 얻는 제 2 단계; 및 상기 제 1 단계에서 분할된 각 서브 경로에 대하여 상기 제 2 단계에서 얻어진 질의 결과를 통합하여 사용자가 요청한 질의 경로에 대한 최근접 객체 정보를 제공하는 제 3 단계; 를 포함하는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
3 |
3
제 2 항에 있어서, 상기 제 1 단계에서는 교차점을 기준으로 상기 질의 경로를 서브 경로 분할하는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
4 |
4
제 2 항에 있어서, 상기 제 2 단계에서 상기 서브 경로의 시작점(Ssp)에서 k번째 최근접 객체(Ok)와 k+1번째 최근접 객체(Ok+1), 서브 경로의 길이(Lsp)에 대하여, 상기 시작점으로부터 k+1번째 최근접 객체까지의 거리로부터 상기 시작점으로부터 k번째 최근접 객체까지의 거리의 감산 결과가 상기 서브 경로 길이의 2배 이상(d(Ssp, Ok+1) - d(Ssp, Ok) ≥2Lsp)이면 해당 서브 경로가 하나의 유효 구간을 가지는 것으로 판단하는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
5 |
5
제 2 항에 있어서, 상기 제 2 단계에서 하나의 서브 경로에 대한 유효 구간의 결정은 해당 서브 경로를 검색하면서 서브 경로 상에 있는 객체를 식별하는 제 1 단계; 상기 서브 경로의 시작점과 끝점에서 최근접 객체를 검색하는 제 2 단계; 소정의 커버 관계를 이용하여 결과에 영향을 주지 않는 투플들을 제거하는 제 3 단계; 및 상기 서브 경로에서 직선의 방정식을 이용하여 유효 구간을 결정하는 제 4 단계; 를 수행함에 의해 이루어지는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
6 |
6
제 5 항에 있어서, 상기 제 3 단계에서 같은 객체(obj)에 대한 정보를 가지고 있는 2개의 투플(t1 = {(obj,x1,y1)}, t2 = {(obj,x2,y2)}에 대하여 y2 ≥│x2 -x1│ + y1 이면 상기 투플(t1)이 투플(t2)을 커버하므로 상기 투플(t2)을 제거하여 불필요한 투플을 제거하는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
7 |
7
제 5 항에 있어서, 상기 제 4 단계에서의 직선의 방정식에 의해 투플들에 의해 형성되는 직선들의 교차점을 구하고, 인접한 교차점들로 이루어진 유효 구간에서 사용자의 질의를 만족하는 소정 개수의 가장 작은 거리를 갖는 객체들을 찾는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|
8 |
8
제 1 항에 있어서, 상기 제 1 과정은 상기 3점 이상이 만나는 교차점 중 팬 아웃이 적어도 4개 이상이 되는 교차점에 대하여 해당 최근접 객체정보와 해당 최근접 객체의 거리 정보를 상기 최근접 객체정보 데이터베이스로 구축하는 것을 특징으로 하는 경로 상의 최근접 객체 검색 방법
|