상세정보
학술지
Finding Top-k Answers in Node Proximity Search Using Distribution State Transition Graph
- 저자
- 박재휘, 이상구
- 발행일
- 201608
- 출처
- ETRI Journal, v.38 no.4, pp.714-723
- ISSN
- 1225-6463
- 출판사
- 한국전자통신연구원 (ETRI)
- 협약과제
- 14PC3900, 중소 제조산업의 4M (Man, Machine, Materiel, Method) 데이터 통합 분석을 활용한 프리틱디브 매뉴펙춰링 시스템 개발 , 지수영
- 초록
- Considerable attention has been given to processing graph data in recent years. An efficient method for computing the node proximity is one of the most challenging problems for many applications such as recommendation systems and social networks. Regarding large-scale, mutable datasets and user queries, top-觀 query processing has gained significant interest. This paper presents a novel method to find top-觀 answers in a node proximity search based on the well-觀nown measure, Personalized PageRank (PPR). First, we introduce a distribution state transition graph (DSTG) to depict iterative steps for solving the PPR equation. Second, we propose a weight distribution model of a DSTG to capture the states of intermediate PPR scores and their distribution. Using a DSTG, we can selectively follow and compare multiple random paths with different lengths to find the most promising nodes. Moreover, we prove that the results of our method are equivalent to the PPR results. Comparative performance studies using two real datasets clearly show that our method is practical and accurate.
- KSP 제안 키워드
- Distribution Model, Graph data, Node proximity, Query Processing, Recommendation System, State Transition Graph, Top-K, User query, Weight distribution, challenging problems, large-scale