영역 탐색 알고리즘에 대한 질문입니다.
글쓴이: superkkt / 작성시간: 수, 2008/07/16 - 11:07오후
안녕하세요.
영역 탐색에 대해서 질문을 하려고 합니다. 그런데 제가 생각하는 부분이 영역 탐색이라고 말하는게 맞는지 잘 모르겠네요.
제가 만드려는 프로그램은 우선 실수형 데이터들을 DB로 구축합니다. 그리고 찾으려는 실수값을 주면 해당 값에서 미리 정해진 문턱값을 +-한 범위에 속하는 모든 실수형 데이터를 빠르게 찾아내야 합니다.
예를 들어 0.05라는 값이 쿼리되었을 때, 문턱값이 0.005라면 0.045 ~ 0.055에 해당하는 실수형 데이터들을 DB에서 찾아내야 합니다.
정확히 일치하는 값을 찾는게 아니라 일정 범위 안의 값을 찾아내는 프로그램은 처음 접해보는 것이라서 어떤 방법으로 DB를 구축해야 할지 감이 잘 안잡히네요.
일단 Inverted Index나 Inverted List를 사용해서 실수를 미리 여러 개의 영역으로 나눠놓고, 쿼리된 실수가 속하는 영역과 그 앞, 뒤 영역을 모두 검색해서 보여줄까 생각을 하고 있는데, 별로 좋은 방법이 아니라는 생각이 자꾸 드네요.
이럴 땐 어떤 알고리즘을 사용하는것이 좋은지 조언 부탁 드립니다.
Forums:
inverted index 보다는..
B+ tree index를 만드시고, range scan을 하시는게 좋을것 같습니다.
만일 A라는 값과 threshold t가 있을때, A-t <= x <= A+t 인 값을 찾아야 하는데,
B+ tree를 사용해 A-t 값으로 일단 검색합니다. leaf 까지 내려 가면
A-t값과 같거나 A-t가 없는 경우 A-t보다 큰 값 중 가장 작은 값을 가진 leaf를 찾을 수 있습니다.
그런후 해당 leaf를 따라가며 A+t보다 큰 값이 나올때 까지 range scan을 하면 될것 같습니다.
R+ 트리는 어떨까요?
보통 지도에서 해당영역에 포함된 데이타가 어떤것이 있는지
(예를들어 여의도에는 어떤데이타가 있는지와 같은)
의 질의를 할때 사용한다고 알고 있습니다. 직접 구현은 안해봤지만
학교수업시간에 배웠는데 기억이 가물가물.
데이타를 R+ 트리에 삽입하시고 영역질의를 이용하시면 될것 같구요.
윗분 말씀처럼 B+ 트리를 이용하신다면 찾고자 하는 데이타의 미니멈 데이타를
리프노드까지 찾아내려간다음 거기서 순차검색으로 맥시멈 데이타가 나올때까지
원하는 데이타를 찾으시는 방법도 한가지 방법이 될 것 같습니다
댓글 달기