본 발명 은 네비 게이 션 을 비롯 한 다양 한 차량 텔레매틱스 용 위치 기반 서비스 시스템 에서 기본 적 으로 사용 되 는 맵 매칭 의 효율 화 를 기하 기 위하 여 로드 네트워크 에서 필수 적 인 부분 만 을 추출 한 후 메모리 에 저장 함 으로써 디스크 연산 을 제거 하 는 방법 에 관한 것 이 다 . 로드 네트워크 는 교차로 를 표시 하 는 노드 , 교차로 간 연결 성 을 나타내 는 링크 로 구성 이 되 며 한 링크 는 양 끝 노드 와 링크 의 형태 를 나타내 기 위한 버텍스 들 로 구성 된다 . 맵 매칭 을 위해서 는 버텍스 들 의 좌표 를 모두 필요 로 하 지만 공간 요구량 이 많 아지므로 디스크 에 저장 을 하 여야 한다 . 따라서 맵 매칭 은 많 은 디스크 연산 을 초래 하 게 되 어 성능 저하 의 요인 이 된다 . 맵 매칭 을 위한 자료 구조 가 메인 메모리 에 적재 될 수 있 다면 맵 매칭 과 위치 기반 서비스 의 속도 성능 이 향상 될 수 있 을 것 이 며 이 를 위해 버텍스 들 중 일부 만 을 선택 하 여 가상 링크 의 형태 로 메모리 에 저장 하 는 것 이 바람직 하 다 . 이 과정 은 도로 네트워크 에 변경 이 발생 할 때 마다 수행 되 어 온라인 맵 매칭 부 에 이용 된다 . 주어진 도로 네트워크 에 있 어서 노드 와 링크 만 가진 네트워크 로 초기 화 한 후 각 링크 의 세그먼트 마다 10 개 의 10 분점 들 에 대해 맵 매칭 을 수행 하 여 만약 원래 속한 링크 와 다른 링크 가 계산 된 경우 이 점 이 속한 세그먼트 를 가상 링크 로 등록 한다 . 이 가상 링크 는 원래 자신 이 속한 링크 로 자동 매핑 된다 . 결국 , 본 발명 은 네 비게 이 션 시스템 을 이용한 이동경 로 서비스 방법 에 있 어서 필요 메모리 를 최소 화 하 기 위해 가상 링크 기반 으로 도로 네트워크 를 단순 화 하 는 과정 , 단순 화 에 있 어서 필수 가상 링크 를 선택 하 는 과정 , 상기 가 상 링크 정보 를 탐색 하 여 맵 매칭 을 수행 하 는 과정 등 으로 구성 된다 .