| 1 |
1
셀들(cells)로 구성되고, 사용자들 각각을 나타내는 정점(vertex, )의 집합()과 상기 사용자들 사이의 친구 관계를 나타내는 엣지(edge, )의 집합()으로 구성된 비방향성 그래프(undirected graph, )가 반영된 그리드(grid) 상에서 쿼리를 처리하는 친구 검색 장치에 있어서,질의자(query issuer, ), 질의 지점(query point, ), 검색 결과의 개수(, 는 자연수), 및 친밀도(, 은 자연수)를 포함하고 상기 질의자()의 -홉 친구들 중 상기 질의 지점()으로부터 가장 가까운 명에 대한 검색 요청인 -NCF 쿼리(-Nearest -Close Friends query, 와 은 자연수)를 수신하는 쿼리 수신부;상기 질의자()의 -홉 친구 리스트()와 상기 질의자()의 -홉 친구가 포함된 셀들의 리스트인 -홉 개인 셀 리스트()를 생성하는 리스트 생성부;상기 -홉 친구 리스트()와 상기 -홉 개인 셀 리스트()를 이용하여 상기 -NCF 쿼리에 대한 응답을 생성하는 쿼리 처리부; 및상기 그리드에 포함된 복수의 셀들 중 적어도 하나의 정점을 포함하는 셀들 각각에 대응하고 상기 그리드의 크기와 동일한 크기를 갖는 매트릭스(matrix, )를 생성하는 업데이트부를 포함하고,상기 매트릭스()의 성분(element, )은 상기 매트릭스()에 대응하는 셀()과 임의의 셀() 내의 정점들 사이의 엣지(edge)의 개수를 나타내는,친구 검색 장치
|
| 2 |
2
제1항에 있어서,상기 쿼리 처리부는 상기 그리드 상에서 상기 질의 지점()이 포함된 쿼리 셀()과 상기 쿼리 셀()를 둘러싸는 4 개의 직사각형들(rectangles)을 초기화된 힙(heap, )에 삽입하고,상기 그리드 상의 직사각형은 위(up), 아래(down), 왼쪽(left) 또는 오른쪽(right)을 포함하는 방향(direction)과 해당 직사각형과 상기 쿼리 셀() 사이에 존재하는 직사각형의 개수인 레벨 넘버(level number)로 표현되고,동일한 레벨 넘버를 갖는 직사각형들은 동일한 개수의 셀을 포함하는,친구 검색 장치
|
| 3 |
3
제2항에 있어서,상기 힙()의 엔트리(entry)들은 상기 질의 지점()과의 최소 거리()의 오름 차순으로 정렬되는,친구 검색 장치
|
| 4 |
4
제2항에 있어서,상기 쿼리 처리부는 상기 힙()의 엔트리들 중 상기 질의 지점()과의 최소 거리가 가장 작은 엔트리를 디-힙(de-heap)하는,친구 검색 장치
|
| 5 |
5
제4항에 있어서,상기 쿼리 처리부는,디-힙된 엔트리()가 상기 -홉 개인 셀 리스트()에 포함되는 셀이면, 디-힙된 엔트리() 내에 포함된 정점 중 상기 -홉 친구 리스트()에 포함되는 정점을 결과 집합()에 삽입하고,디-힙된 엔트리()가 직사각형이면, 상기 직사각형 내의 모든 셀들과 동일한 방향에서 다음 레벨의 직사각형을 상기 힙()에 삽입하는,친구 검색 장치
|
| 6 |
6
제5항에 있어서,상기 쿼리 처리부는,상기 힙()에 포함된 엔트리가 없거나 상기 결과 집합()의 번째 원소(component)와 상기 질의 지점() 사이의 최소 거리()가 디-힙된 엔트리()와 상기 질의 지점()과의 최소 거리() 보다 작아질 때까지,상기 질의 지점()과의 최소 거리가 가장 작은 엔트리를 디-힙하는 동작, 상기 -홉 친구 리스트()에 포함되는 정점을 결과 집합()에 삽입하는 동작, 및 상기 직사각형 내의 모든 셀들과 동일한 방향에서 다음 레벨의 직사각형을 상기 힙()에 삽입하는 동작을 반복적으로 수행하는,친구 검색 장치
|
| 7 |
7
제6항에 있어서,상기 쿼리 처리부는 상기 결과 집합()을 상기 응답으로 출력하는,친구 검색 장치
|
| 8 |
8
삭제
|
| 9 |
9
제1항에 있어서,상기 업데이트부는 임의의 사용자의 위치 변경 정보와 친구 관계 변동 정보 중 적어도 하나를 수신하고 수신된 정보에 대응하도록 상기 매트릭스를 업데이트하는,친구 검색 장치
|
