The ObjectRank system applies the random walk model, the effectiveness of which is proven by Google's PageRank, to keyword search in databases modeled as labeled graphs. The system ranks the database objects with respect to the user-provided keywords.
The PageRank technique assigns to each page p a score based on the score of the pages pointing to p. Hence, pages pointed by many high-score pages receive a high score as well. Alternatively, the score of p is equal to the probability that a random surfer, starting from a random page, will be at p at a specific time. For more information on PageRank see the original PageRank paper.
We apply this idea to databases, which require modifications of the original algorithms to exploit the semantic information of every application, which is represented by annotating the database schema. Another novelty of ObjectRank is that we perform keyword-specific ObjectRank and not global as Google. Hence, for each <keyword, object> we compute an ObjectRank value. In particular, random walks start from the objects containing the keywords. Each object is ranked with respect to the particular keywords, based on the stationary probability that random walks are found at the object at a given time.
ObjectRank is adjustable to the semantics of each database and the
varying requirements of object ranking. In particular, we adjust the weight of
global importance, the weight of each keyword of the query, the importance of a
result actually containing the keywords versus being referenced by nodes with
high ObjectRank, and the volume of authority flow via each type of semantic
Novel performance challenges and opportunities are addressed. First, schemas impose constraints on the graph, which are exploited for performance purposes. Second, we employ aggressive precomputation and experiment on storage space versus execution time tradeoffs. Finally, the keyword specific ObjectRanks are efficiently combined in order to produce the top-k objects.
Example: The following figure illustrates a small subset of the DBLP database in the form of a labeled graph (author, conference and year nodes except for ``R. Agrawal'', ``ICDE'' and ``ICDE 1997'' respectively are omitted to simplify the figure). The weights on edges represent the authority flow through them. For example, more authority is transferred from a paper to a cited paper than from a paper to its author. Also notice that no authority is transferred from the cited papers to the citing.
Given a keyword query, e.g. the single keyword query "OLAP", ObjectRank sorts the database objects by their importance with respect to the user-provided keywords. The papers of the above figure are ranked as folows:
Modeling Multidimensional Databases
Range Queries in OLAP
Index Selection for OLAP
Notice that the "Data Cube" and the "Modeling Multidimensional Databases" papers do not contain the keyword "OLAP", but they clearly constitute important papers in the OLAP area, since they are referenced by other papers of the OLAP area, or have been written by authors who have written other important "OLAP" papers, or appear in conferences important to "OLAP".
|Yannis Papakonstantinou, Professor|
|Andrey Balmin, PhD student|
|Vagelis Hristidis, PhD student|
|Vincenzo Di Nicola, exchange student|
|Andrey Balmin, Vagelis Hristidis, Yannis Papakonstantinou: Authority-Based Keyword Queries in Databases using ObjectRank. VLDB 2004|
Random Walk in Stuctured Databases, at UCSD Research Seminar, 2003
The DBLP subset of the demo consists of the available publications in 12 major database conferences, including SIGMOD, VLDB, PODS, ICDE, ICDT and EDBT. The schema of the database is the following
For AND (OR) semantics, the score of a node u is the product (sum) of the keyword-specific ObjectRanks of u with respect to each of the user-specified keywords. The demo also provides two other adjusting parameters: The "containment of actual keywords" parameter determines how important it is for a result to contain the user-specified keywords, as opposed to being pointed by other nodes with high score. The "global ObjectRank" parameter specifies if the global (keyword-independent) ObjectRank is included in the calculation of the scores.
On the demo page, we describe some typical search profiles for various selections of paramaters.
Go to ObjectRank Demo
(original jsp interface by Michael Sirivianos )
Inquiries for commercial use of this software should be directed to firstname.lastname@example.org.