잠재적으로 큰 데이터 값을 비교 내가 잠재적으로 거대한 데이터 세트에 대한 값을 비교하는 가장 효율적인 방법을 알아 내려고 노력하고 있어요

Question

을 설정합니다. 문제는 내가 무엇을 찾고 있는지 정확히 모르는 것이다. 나는 알고리즘을 정렬하고 검색하는 것에 대한 연구를 해왔지만 (대부분 non-cs로 여기에서 중요하다), 내가 찾은 대부분의 결과는 차이점을 반환하거나 데이터를 정렬한다. 이 방법이 유용 할 수도 있지만 계산할 결과를 최소화 할 수있는 방법을 찾아내는 중입니다.

응용 프로그램은 지정된 거리 (예 : 5 마일) 내에있는 모든 게시물을 반환하기 위해 데이터베이스에있는 다른 모든 게시물에 게시물 (사용자가 아닌 사용자와 연결되는 위도/경도)을 비교할 때 지정된 사용자 위도와 경도를 비교합니다.

내 응용 프로그램의 첫 번째 버전 (아직 개발) 단지 5 마일 반경 내에서만 게시물과 표시들 사이의 정확한 거리를 돌아 데이터베이스에 다른 모든 게시물에 게시물을 비교합니다. 그것은 테스트 사용자가 수십 번호와 잘 작동하지만 나는 살아 갈 때이 일일 사용자/게시물의 수백만의 수와 전체 데이터베이스에 PHP에서 이러한 계산을 수행하는 것은 적합하지 않다고 알고 있습니다.

쿼리 게시물의 위도가 +/- 5 분 ​​(~ 5 마일) 인 지난 72 시간의 게시물로 임시 테이블을 만든 다음 PHP를 사용하여 실제 거리를 계산하는 방법이 있습니다. 비 관련 경도를 효과적으로 제거하는이 작은 세트의 이 쿼리에서 경도를 사용하여 탐색 할 수도 있지만 거리가 다양하기 때문에 엄청나게 정확하지는 않습니다. 아마도 여전히 극에서 5 마일 이내에 가을과 여전히 (내가 BTW 극에서 많은 사용자를 가지고하지 않을 예정) 적도의 데이터 세트의 크기를 줄일 수 경도에 과장 5 개도를 사용하여.

이 소리인가, 아니면 더 좋은 방법은 무엇입니까?

어떤 아이디어 또는 제안 된 측정 값?

Answer 1

k-d tree은 가능한 한 확실하게 이동하는 방법이지만, 문제는 "특정 반경 내의 모든 게시물"을 찾고 있다는 것입니다. 그 중 많은 수가 (100 ~ 10000 초)있을 수 있습니다. 그러나, 집중도가 높은 경우와 반경 (5km)을 깎아서 다른 이점을 피하기 위해 게시물을 클러스터링하는 것이 좋습니다. 이를 수행 할 수있는 방법은 smallest-circle에 대해 선형 알고리즘을 사용하는 것입니다.

def cluster_posts(points,cluster_radius): 
    clusters = dict() 
    for p in posts: 
     # This inner part is also done whenever a new post is added 
     clusters[p] = Cluster([p]) 
    points_set = set(points) 
    While points_set: 
     # This inner part is also done whenever a new post is added 
     p = points_set.pop() 
     q = kd_tree.nearest_neighbor(p) 
     dist = distance(p,q) 
     radius_p = clusters[p].smallest_circle_radius() 
     radius_q = clusters[q].smallest_circle_radius() 
     if radius_p + dist + radius_q < cluster_radius: 
      new_cluster = clusters[p].merge(clusters[q]) 
      r = new_cluster.smallest_circle_radius() 
      if r < cluster_radius: 
       c = new_cluster.smallest_circle_center() 
       points_set.remove(q) 
       clusters.remove(q) 
       clusters.remove(p) 
       kd_tree.remove(p) 
       kd_tree.remove(q) 
       points_set.add(c) 
       kd_tree.add(c) 
       clusters[c] = new_cluster 

위의 예는 두 개의 클러스터를 cluster_radius를 기반으로 한 단일 클러스터로 결합하려고 시도합니다. 최적화를위한 여지가 있지만 O (N log N) 주변에서 실행되어야합니다. 이후 특정 클래스와 함수를 코딩하지 않았으므로 컴파일되지는 않을 것이지만 잘하면이 아이디어를 얻을 수 있습니다. 포인트 (위도/경도)가 이미 k-d 트리에 입력되어 있다고 가정합니다. 또한 위도와 경도를 분 - 초 - 분수에서 초로 변환하는 것은 나쁜 생각이 아닙니다. 분수. 어쨌든 클러스터링과 비슷하기 때문에 5 킬로미터는 좌표를 유클리드 점으로 처리 할 수있을 정도로 작을 것입니다.

쿼리는 k-d 트리를 통해 사용자 위치의 (query_radius - cluster_radius) 내의 모든 클러스터를 찾고 적어도 가장 가까운 클러스터를 포함합니다. 당신이 준 숫자는 쿼리 반경을 5km로 만들 것입니다.

• 5km (전체 반경)
• 2.5 km (반 반경) 백
• 몇 피트 (블록에 의해 클러스터) 돌이켜

Answer 2

데이터베이스에 게시물을 저장하려는 경우 (테이블에 위도, 경도 및 게시물 텍스트가 포함되어 있고 위도와 경도를 인덱싱하는 경우), 범위 쿼리를 수행하여 적절한 게시물 (위도 (경도 10 및 20 사이) 및 (경도 40-50 사이)

모든 데이터가 메모리에 있으면 range tree 또는 k-d tree은 원하는 데이터 구조입니다. 수백만 개의 게시물을 가지고 있다면 데이터베이스를 사용하고자 할 것입니다.

SQLite은 무료로 사용할 수있는 무료 경량 데이터베이스입니다