BROWSE
Detail
Journal Article
Finding Top-k Answers in Node Proximity Search Using Distribution State Transition Graph
- Authors
- Jaehui Park, Sang-Goo Lee
- Issue Date
- 2016-08
- Citation
- ETRI Journal, v.38, no.4, pp.714-723
- ISSN
- 1225-6463
- Publisher
- 한국전자통신연구원 (ETRI)
- Language
- English
- Type
- Journal Article
- Abstract
- 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 Keywords
- Distribution Model, Graph data, Node proximity, Query Processing, Recommendation System, State Transition Graph, Top-K, User query, Weight distribution, challenging problems, large-scale