Search Results
'PHP'에 해당하는 글들
- 2006/11/01 [src] PHP kd-tree 061101 (4)
- 2004/12/13 [src] PEAR와 Smarty를 이용한 AKI-PHP Framework
- 2004/07/21 FreeBSD에서 PHP 4.3.8 이상(mod)+extensions 포트 설치 유의점 (4)
[src] PHP kd-tree 061101
kdtree_061101.zipPHP KD-Tree 061101 ver.
어째 실험 환경이 PHP상에서 돌아가는 경우가 많거든요. :)
KD-Tree에 대해 소개드리면(이미 아시는 분은 많겠지만)
1차원 자료와는 달리 n차원 자료의 경우 B-Tree 계통처럼 구획을 나눌 필요가 있습니다.
그래야 최단거리 검색(nearest search)을 하거나 범위 검색(range search)할 수 있거든요.
물론 학부에서도 배우는거고 오래된 알고리즘이라 나쁜점이 많습니다.
가령 euclidean distance와는 생판 관계없다는 것도 문제고..
(물론 이건 parent 탐색으로 어느 정도 해결되긴 하는듯)
특히 공간 사용 효율성이 떨어집니다.
근접한 데이터의 경우 운나쁘면 심지어는 root까지 탐색해야 찾을수도 있답니다 '~';
따라서 이후 나온 R-Tree 같은게 이런걸 해결해주려고 노력..한거긴 한데,
20차원 이상으로 넘어가면 효율성이 떨어진다는 단점이 있지요.
특히 사각형 모양의 ROI(Region Of Interest)를 쓰는건 요즘 추세도 아니고 말이죠.
...처음에는 depth가 무지 높은 배열을 생각했는데,
왠지 부하가 심각할거 같아서 그냥 stack 기반으로 바꿨습니다.
기존 구조는 one depth 별로 idx depth 2개 상승..
이번건 상승하는게 없긴 합니다. '~';
물론 아직 다 구현하진 않았고 소스코드도 정리가 되지 않았습니다.
insert랑 nearest search 정도만 구현되었을듯?
나머지는 나중에 시간나면 해보도록 하죠 '~';
2차원에 대해서는 테스트를 해봤는데,
3차원 이상에 대해서는 해보질 않았네요.
혹시 안되는 분 테스트 소스랑 같이 댓글 달아주시면 시간날때마다 수정해두겠습니다.
...아, 퍼가시거나 자신의 실험환경에서 사용하실때는
소스코드에 적혀있는 주소로 간단하게 쓰겠다는 메일이라도 보내주세요.
최적화 문제도 있고...
기존 kd-tree는 balanced-tree가 형성되지 않는다는 문제도 있습니다. OTL