AncomWiki

실시간 스토리 식별을 위한 스트리밍 환경에서의 밀집 부분 그래프 유지

Properties1
description본 논문은 소셜 미디어의 실시간 데이터 스트림에서 밀접하게 연결된 엔티티 군집(밀집 부분 그래프)을 효율적으로 유지하여 실시간 스토리를 식별하는 문제를 다룹니다. 기존 기법들의 한계를 극복하기 위해, 단일 간선 가중치 업데이트가 밀집도에 미치는 변화의 크기에 대한 이론적 결과를 도출하고, 이를 바탕으로 새로운 알고리즘인 'DynDens'를 제안합니다. DynDens는 기존 기법보다 우수한 성능을 보이며, 대규모 실증 및 합성…

15 min read

실시간 스토리 식별을 위한 스트리밍 환경에서의 밀집 부분 그래프 유지

Source

  • Evernote/IFTTT Feedly/Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification.md

Summary

본 논문은 소셜 미디어의 실시간 데이터 스트림에서 밀접하게 연결된 엔티티 군집(밀집 부분 그래프)을 효율적으로 유지하여 실시간 스토리를 식별하는 문제를 다룹니다. 기존 기법들의 한계를 극복하기 위해, 단일 간선 가중치 업데이트가 밀집도에 미치는 변화의 크기에 대한 이론적 결과를 도출하고, 이를 바탕으로 새로운 알고리즘인 ‘DynDens’를 제안합니다. DynDens는 기존 기법보다 우수한 성능을 보이며, 대규모 실증 및 합성 데이터셋을 통한 실험으로 그 유효성이 검증되었습니다.

Key Points

  • 소셜 미디어의 방대하고 빠르게 변화하는 데이터에서 실시간으로 주목받는 스토리(밀집 부분 그래프)를 식별하는 것이 핵심 과제임.
  • 스트리밍 환경에서 간선 가중치가 지속적으로 업데이트될 때 밀집 부분 그래프를 효율적으로 유지하는 문제를 최초로 체계적으로 연구함.
  • 다양한 밀집도 정의에 대해 단일 간선 업데이트가 초래하는 변화의 상한에 대한 이론적 분석을 수행함.
  • 이론적 분석을 기반으로 한 새로운 알고리즘 ‘DynDens’를 제안하며, 기존 기법 대비 성능 우위를 입증함.
  • 대규모 실제 데이터 및 합성 데이터를 통한 실험으로 알고리즘의 유효성과 확장성을 검증함.

그래프 뷰

백링크