메트릭 공간에서 색인화 및 검색을위한 잘 설명 된 알고리즘

Question

Postgres (*) (PL 또는 PL/Python)에서 어떤 종류의 메트릭 공간 검색을 구현해야합니다. 그래서 저는이 아이디어 뒤에있는 기계에 대한 매우 명확하고 선명한 설명으로 좋은 출처 (또는 논문)를 찾고 있습니다.

효율성보다 명확성을 선호합니다.

(*) 그 필요성이 더 잘 설명됩니다. 여기.

Answer 1

특히 지리적 데이터의 경우보십시오 Postgis 먼저 무엇이든 구현 해야하는지 확인하십시오. 그렇다면, GIST에 Wikipedia 항목.

링크를 살펴보면 메트릭 공간이 메트릭과 같은 종류의 편집 거리가있는 문자열 인 것 같습니다. 일부 솔루션에 대한 멋지지만 오래된 개요는 Navarro, Baeza-Yates, Sutinen 및 Tarhio, IEEE Data Engineering Bulletin, 2001; Citeseer의 관련 논문도 유용 할 수 있습니다. 지역 민감한 해싱 유용 할 수있는 최신 기술이지만 많은 논문이 수학에 무겁습니다.

Answer 2

BK-Trees 삼각형 불평등, 메트릭 공간이 포함 된 모든 것을 색인화하고 검색하는 데 유용합니다. 표준 예는 대상의 주어진 편집 거리 내에서 문자열을 검색하는 것입니다. 나는 그것에 관한 기사를 썼습니다 여기.

불행히도 Postgres에는이를 지원하지 않습니다. 당신은 그것을 사용하여 직접 구현할 수 있습니다 요점, 그러나 분명히 그것은 많은 일이 될 것입니다. 나는 나무를 테이블에 저장하지 않는 자신의 색인을 작성하지 않고도 구현할 수있는 방법을 생각할 수 없습니다.

Answer 3

당신은 시도 할 수 있습니다 http://sisap.org BK-Tree를 포함하여 많은 현대 메트릭 인덱스가 나열된 곳. 다른 대안을 시도하려면 C에서 코드를 찾을 수 있습니다.

Answer 4

당신을 도울 수있는 공간 검색과 관련된 일부 기술은 언덕 등반, 신경망 훈련, 유전자 알고리즘 및 입자 떼입니다.

또한 메트릭 공간에 대한 거리 메트릭을 정의해야합니다. 당신은 그렇게 했습니까?