Ranking target objects of navigational queries

ABSTRACT

Web navigation plays an important role in exploring public interconnected data sources such as life science data. A navigational query in the life science graph produces a result graph which is a layered directed acyclic graph (DAG). Traversing the result paths in this graph reaches a target object set (TOS). The challenge for ranking the target objects is to provide recommendations that re ect the relative importance of the retrieved object, as well as its relevance to the specific query posed by the scientist. We present a metric layered graph PageRank (lgPR) to rank target objects based on the link structure of the result graph. LgPR is a modification of PageRank; it avoids random jumps to respect the path structure of the result graph. We also outline a metric layered graph ObjectRank (lgOR) which extends the metric ObjectRank to layered graphs. We then present an initial evaluation of lgPR. We perform experiments on a real-world graph of life sciences objects from NCBI and report on the ranking distribution produced by lgPR. We compare lgPR with PageRank. In order to understand the characteristics of lgPR, an expert compared the Top K target objects (publications in the PubMed source) produced by lgPR and a word-based ranking method that uses text features extracted from an external source (such as Entrez Gene) to rank publications.

REFERENCES

• 1: Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB, pages 564--575, 2004.
• 2: Magdalini Eirinaki , Michalis Vazirgiannis , Dimitris Kapogiannis, Web path recommendations based on page ranking and Markov models, Proceedings of the 7th annual ACM international workshop on Web information and data management, November 04-04, 2005, Bremen, Germany [doi>10.1145/1097047.1097050]
• 3: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 4: Homo sapiens in NCBI Taxonomy Browser. www.ncbi.nih.gov/Taxonomy/Browser/wwwtax.cgi? mode=Info&id=9606.
• 5: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 6: Z. Lacroix, L. Raschid, and M.-E. Vidal. Semantic model ot integrate biological resources. In International Workshop on Semantic Web and Databases (SWDB 2006), Atlanta, Georgia, USA, 3-7 April 2006.
• 7: Alex Lash , Woei-Jyh Lee , Louiqa Raschid, A Methodology to Enhance the Semantics of Links between PubMed Publications and Markers in the Human Genome, Proceedings of the Fifth IEEE Symposium on Bioinformatics and Bioengineering, p.185-192, October 19-21, 2005 [doi>10.1109/BIBE.2005.3]
• 8: Carl D. Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 9: G. Mihaila, F. Naumann, L. Raschid, and M. Vidal. A data model and query language to explore enhanced links and paths in life sciences data sources. Proceedings of the Workshop on Web and Databases, WebDB, Maryland, USA, 2005.
• 10: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 11: Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 12: Matthew Richardson and Pedro Domingos. Combining link and content information in web search. In Web Dynamics '04: Web Dynamics - Adapting to Change in Content, Size, Topology and Use, pages 179--194. Springer, 2004.
• 13: Aditya Kumar Sehgal and Padmini Srinivasan. Retrieval with gene queries. BMC Bioinformatics, 7:220, 2006.
• 14: Maria-Esther Vidal, Louiqa Raschid, Natalia Márquez, Marelis Cárdenas, and Yao Wu. Query rewriting in the semantic web. In InterDB, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
link analysis, navigational query, pagerank, ranking