IT의 중심에서

IT산업에 대한 가슴아픈 고찰

지도 기반 클러스터링 기법 소개

  1. 서론

    구글맵으로 샌프란시스코와 실리콘 밸리를 한 컷에 잡은 화면입니다.
    보여지는 사진은 Panoramio 와 매쉬업된 내용입니다. 적어도 150 여개 이상의 poi 들이 있는 것 같네요.
    구글은 이렇게 많은 poi 를 찍을 때는 DOM 객체로 찍지 않고, 서버에서 실시간으로 타일 이미지를 만든 다음에 지도와 함께 뿌려주는 기술을 사용하고 있습니다.
    tile-image1

    반면, Modea 라는 광고 Agency 가 Instagram 을 프로모션하기 위해 만든 웹 페이지를 봅시다.
    샌프란시스코 Bay를 중심으로 동심원 내의 사진들을 보았습니다.
    구글처럼 “대량 poi 표출기능”이 오픈되어 있지 않기 때문에, 아래와 같이 40여개의 마커로 밖에 표현되지 않습니다.
    (100여개 이상을 마커로 표출하면, 브라우저 메모리 점유율이 올라가면서 무지하게 느려집니다.)
    insta-earth

    반면, 우리가 일반적으로 스마트폰을 통해 주변 정보를 습득하는 세 가지 방식은 아래와 같습니다.

    • 내 주변으로부터 100 미터의 카페를 찾다.
      GPS 칩이 들어가면서, 자연스럽게 이용할 수 있는 기능이 되었습니다.
      서버에서 mongo db 나 mysql 등이 이 기능을 지원하면서, “지역정보” 서비스는 새로운 경쟁의 장이 되었습니다.

    • 특정 지역(관심지역) 내의 카페를 찾다.
      특정 다각형 내의 데이터를 검색해오는 기능입니다. “대학로 카페”라고 할 때 “대학로”를 단순한 원으로만 볼 수 있을까요?
      “대학로”는 아마 다각형으로 구분지을 수 있을 겁니다. Google은 다각형내 poi 검색기능을 만들어 실험실을 통해 이 기능을 시험하고 있습니다.
      앞으로 “어디 근처” 라는 개념이 “동심원”으로 표현되기 어려운 만큼 앞으로 많이 발전할 분야로 보여집니다.

    • 시각적 패턴에 의해 정보를 선택하다.
      위에 기재된 구글맵 사례입니다.
      자신의 데이터를 다량으로 지도위에 뿌려주고 그냥 “사용자의 직관적인 경험이나 느낌”을 통해 지도 상의 데이터를 탐색하도록 하는 것을 말합니다.
      “위치 데이터가 많아질수록, 위치 데이터로부터 Context 를 발견하려는 노력이 높을수록, 시각적 패턴은 더욱 더 중요해집니다.”

    시각적 패턴정보를 위해 구글은 복잡한 poi 를 적절히 표현하기 위해 “poi clustering” 이라는 기법을 사용하고 있습니다.

    서버기반의 poi clustering 은 CPU Cost 가 높고 대용량화 될수록 Server Resources 가 기하급수적으로 늘어나기 때문에 꽤 난이도가 높은 미들웨어 기술에 속합니다. 그래서, 개방형으로 서비스하기에도 쉽지 않습니다.

    오늘은 이 기술에 대해 살펴볼까 합니다.

  2. poi clustering 기법
    1) 위경도를 중심으로 Tiling
    cluster1
    구글맵이 Panoramio 를 표현하는 것과 동일한 방식입니다.
    위경도에 맞추어 Tile 을 자르고, 해당 지역 내의 밀집도를 측정하는 방법입니다.
    밀집도가 높을 경우 강한 색으로, 밀집도가 낮을 경우 낮은 색으로 표현하면 되겠지요?
    이 표현의 장점은 동일 넓이의 타일을 기준으로 정보량을 비교하므로 넓은 지역에 일체감을 줄 수가 있습니다. 단점은 타일 내에서 정보량을 비교하므로, 걸친 지역에 대한 분석 등에 오류가 있을 수 있습니다.

    2) 지역을 사각형으로 나누어서 Tiling
    cluster2
    도시 지역이나 도로 경계나 영역에 대해 사각형으로 클러스터를 임의로 나누고, 이에 따라 밀집도를 계산하는 방식입니다. 밀집도가 사람의 느낌과 일치도가 높은 반면, 도시지역에 따라 계산하는 방식이므로 CPU Cost 가 높은 방식입니다. 도시나 도로변에 대한 분석에 유리합니다.

    3) 밀집지역 중심 Tiling
    cluster0
    보여지는 지역에서 해당 데이터의 밀집도가 높은 지역을 측정하고, 이 위치를 중심으로 기반으로 밀집도를 표현하는 방법입니다. CPU cost 가 가장 높습니다. 하지만, 자연스러워 보이는 장점이 있습니다.

  3. path 기반 poi clustering
    route_img
    샌프란시스코 공항에서 실리콘밸리까지 가는 길에 “맥도날드 같은 패스트푸드점”을 검색해내는 화면입니다.
    5마일 이내만 찾도록 했고,동일한 방식으로 주유소나 음식점 등을 찾아볼 수 있습니다.(오른쪽에는 운전경로를 보여준다.)

    경로 주변에 대해 poi 의 거리를 계산하고, 이에 대해 poi 를 clustering 함으로써, 어느 장소에서 쉬었다 갈 것인지, 어느 장소가 흥미로운지를 시각적으로 알아낼 수 있습니다.

    위 기술은 아직 널리 알려지지 않아 안타깝게도 많이 쓰이고 있지 않습니다.
    하지만, 가까운 미래에 “스마트카 내부”에 꼭 들어올 기술일 것 같습니다.

  4. path 기반의 실거리, 시간거리 탐색
    30mile-radius
    실리콘밸리를 중심으로 30 마일 이내의 거리를 계산한 예제입니다.
    유사하게 교통수단에 따라 30분 내로 거리도 계산할 수 있을 것 같습니다.

    이렇게 사람이 이동하는 동선 상에서 poi를 효과적으로 탐색하는 것은 새로운 지도검색의 미래가 아닐까 생각해봅니다.

  5. 사례 : 지오태깅 웹사이트 (Soak Digital)
    출처 : http://www.soak.co.uk/blog/server-side-map-marker-clustering/ (2011.6.24)
    저자 : eugeneingram

    Question) “구글맵을 써서 12만 개의 데이터를 동적으로 마커를 표시해주어야 할 때 어떻게 해야 할까?”
    이것은 우리가 가진 기사들을 아래와 같이 보여주려고 하는 Geo tagging 솔루션에 대해 제기한 이슈였습니다.
    server-side1

    사실상 Zoom 레벨과 중심좌표를 기준으로 모든 마커를 구글맵에 보내고 client 에서 해결하고자 하는 것은 불가능합니다.
    그래서, 서버 상에서 충분한 성능을 보장할 수 있는 server-side clustering 기법이 필요했습니다.

    이 질문을 하고 난 후, 몇몇 사람은 구글맵의 각 zoom level 마다 지구의 표면을 개념적으로 타일처럼 잘라서 접근하려고 했습니다.
    처음에는 우리 목적에 맞게 이런 타일들을 정사각형들로 다루려고 했습니다. (이 방법은 남극, 북극에 가까워질수록 오차가 심해지는 단점이 있기는 합니다.) 물론 특정 zoom level 에 있는 tile 마다 고유넘버를 부여하는 것은 가능한 일이긴 합니다.
    하지만, 21 레벨의 지도에서는 우리는 1번부터 247,390,116,249,600 번까지의 타일을 가지고 있어야 했습니다.

    그래서 DB 안에 중심 테이블을 만들고, 특정 타일 상의 데이터에 대해 평균 위치값 주변으로 각 zoom level 마다 데이터가 들어있는 타일들을 저장할 수 있게 해주었습니다. 이런 접근법들은 클러스터링된 마커 들이 너무 규칙이 엄격한 것처럼 보이지 않도록 도와줍니다.
    하나의 데이터가 시스템에 추가되어질 때, 각 zoom Level 마다 데이터가 들어 있는 타일을 계산하는 것은 단순한 작업이지요.
    그러나, 우리는 데이터들이 추가되어지거나, 편집되거나 시스템으로부터 지워질 때, 그것들이 들어있는 타일들의 평균 위치 값을 재계산할 필요가 있는 것에 주의를 기울여야 했습니다.

    “하지만, 이 구조에서 우리는 주어진 zoom level 과 지도 위치에 맞추어, 미리 클러스터링된 마커 위치들을 구글맵에 보낼 수도 있었습니다. 이 방식의 장점은 우리가 DB 를 Query 할 때, 지도 상에 보여지는 타일들에 대해서만 고민하면 된다는 것입니다. 그래서 240조 개의 타일을 만들 필요가 없습니다.

    만일 하나의 타일이 한 개 이상의 데이터를 포함하고 있다면, 우리는 데이터 숫자 만큼 저장된 평균 위치값을 중심으로 마커를 보여줄 수 있습니다. 만일 한 개의 데이터를 포함하고 있다면, 그 위치에 하나의 마커만 보여줄 수도 있었죠.

    그런 다음에 client-side code 에서 서버에 대한 Ajax call 을 만들고, 구글맵에 적절한 마커를 찍어줌으로써 우리는 해결을 했습니다.

    우리는 이런 접근이 (클러스터를 유지하는 Scenes 뒤에서 대용량 고속처리가 열심히 돌아가고 있지만) 효과적으로 작동한다는 것과 그것이 매우 매끄러운 사용자 경험을 준다는 것을 알게 되었습니다.

  6. 시사점
    현재 위치 기반의 반경검색은, 가장 손쉽게 주변 정보를 검색할 수 있는 기능입니다.
    하지만, LBSNS 가 좀 더 우리 가까이 들어오려면 지도 위에다 손으로 그려보는 여러가지 행위들이 좀 더 “서버 안으로” 들어와야 하지 않을까 싶습니다.

    그 관점에서 안드로이드 단말에 두 달이 멀다하고 자주 업데이트 하고 있는 “구글맵”의 행보는 매우 귀추가 주목됩니다.
    구글맵은 지도 상에서 사용자의 “동선”과 “시선”을 기록하고 분석하는데 역량을 기울이고 있습니다.

    안드로이드 상에서 “지역정보” 기능과 “내비게이션” 기능에 강화된 “장소 추천”을 시도하고 있어서, 이것이 구글이 바라보는 새로운 검색의 한 부분이지 않을까 조심스럽게 예견해봅니다.

    About these ads

    지도 기반 클러스터링 기법 소개”에 대한 3개의 댓글

    1. 성헌
      2012년 2월 14일

      검색하다가 우연히 보게 되었네요
      안녕하세요 구글맵 마커 처럼 적용 해봤답니다.

      저에 홈페이지는 http://linkma.kr

    2. 조규현
      2012년 5월 9일

      안녕하세요. 저는 컨텐츠 제작에 관심있는 학생입니다.
      markercluster 관련하여 정보를 검색 중에 찾아오게 되었습니다.
      글 중에서 path 기반의 poi clustering의 프로그램은 직접 제작하신 건가요?
      아니면 다른 곳에서 서비스 중인 것인가요?
      혹시 관련 정보를 알아 볼 수 있는 곳이 있을까해서 문의 드립니다.
      감사합니다.

    댓글 남기기

    아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

    WordPress.com 로고

    WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

    Twitter 사진

    Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

    Facebook 사진

    Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

    Google+ photo

    Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

    %s에 연결하는 중

정보

이 엔트리는 2012년 1월 19일에 님이 기술이야기에 게시하였으며 , 태그가 지정되었습니다.

내비게이션

팔로우

모든 새 글을 수신함으로 전달 받으세요.

다른 164명의 팔로워와 함께 하세요

%d 블로거가 이것을 좋아합니다: