EFFICIENT RANKING ON ENTITY GRAPHS WITH PERSONALIZED RELATIONSHIPS
Authority flow techniques like Page Rank and Object Rank can provide personalized ranking of typed entity-relationship graphs. There are two main ways to personalize authority flow ranking: Node-based personalization, where authority originates from a set of user-specific nodes; Edge-based personalization, where the importance of different edge types is user-specific. We propose the first approach to achieve efficient edge-based personalization using a combination of precomputation and runtime algorithms. In particular, we apply our method to ObjectRank, where a personalized weight assignment vector (WAV) assigns different weights to each edge type or relationship type. Our approach includes a repository of rankings for various WAVs. We consider the following two classes of approximation: (a) SchemaApprox is formulated as a distance minimization problem at the schema level; (b) DataApprox is a distance minimization problem at the data graph level. SchemaApprox is not robust since it does not distinguish between important and trivial edge types based on the edge distribution in the data graph. In contrast, DataApprox has a provable error bound. Both SchemaApprox and DataApprox are expensive so we develop efficient heuristic implementations, ScaleRank and PickOne respectively. Extensive experiments on the DBLP data graph show that ScaleRank provides a fast and accurate personalized authority flow ranking.
Authority originates from a query- or user-specific set of objects, and spreads via edges whose authority flow weights is determined by their edge (relationship) type. For instance, a paper-to-paper citation edge may have a higher authority flow weight than the paper-to-author edge in a bibliographic data graph. Two fundamental approaches have been proposed to personalize authority flow ranking: (a) Node-based personalization: a personalized base set, i.e., the authority originates from a query- or user-specific set of objects; (b) Edge-based personalization: personalized weight assignment vector (WAV) which assigns a weight to each edge (relationship) type. We use ObjectRank as an exemplar of this latter class.
DISADVANTAGES OF EXISTING SYSTEM:
vAuthority flow techniques typically require dozens of iteration across the data graph.
vThere is no work to facilitate efficient computation of edge-based personalization.
Our specific challenge is on-the-fly execution of authority flow fixpoint computation for a user-specific or query-specific weight assignment vector (WAV). While we use ObjectRank as an exemplar, our approach is applicable to other authority flow ranking techniques like. Given a keyword query, ObjectRank first computes the base set of nodes in the data graph that contain the query keywords.
ADVANTAGES OF PROPOSED SYSTEM:
vThe authority flows from the base set to the whole data graph, until the authority scores on the nodes converge. The nodes with the top score are returned. The authority transfer edges of the data graph are represented by a transition matrix.
Processor - Pentium –IV
Speed - 1.1 Ghz
RAM - 512 MB(min)
Hard Disk - 40 GB
Key Board - Standard Windows Keyboard
Mouse - Two or Three Button Mouse
Monitor - LCD/LED
Operating system : Windows XP.
Coding Language : .Net
Data Base : SQL Server 2005
Tool : VISUAL STUDIO 2008.
Vagelis Hristidis, Yao Wu, and Louiqa Raschid, “EFFICIENT RANKING ON ENTITY GRAPHS WITH PERSONALIZED RELATIONSHIPS” IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 26, NO. 4, APRIL 2014