Flexible and efficient querying and ranking on hyperlinked data sources

ABSTRACT

There has been an explosion of hyperlinked data in many domains, e.g., the biological Web. Expressive query languages and effective ranking techniques are required to convert this data into browsable knowledge. We propose the Graph Information Discovery (GID) framework to support sophisticated user queries on a rich web of annotated and hyperlinked data entries, where query answers need to be ranked in terms of some customized ranking criteria, e.g., PageRank or ObjectRank. GID has a data model that includes a schema graph and a data graph, and an intuitive query interface. The GID framework allows users to easily formulate queries consisting of sequences of hard filters (selection predicates) and soft filters (ranking criteria); it can also be combined with other specialized graph query languages to enhance their ranking capabilities. GID queries have a well-defined semantics and are implemented by a set of physical operators, each of which produces a ranked result graph. We discuss rewriting opportunities to provide an efficient evaluation of GID queries. Soft filters are a key feature of GID and they are implemented using authority flow ranking techniques; these are query dependent rankings and are expensive to compute at runtime. We present approximate optimization techniques for GID soft filter queries based on the properties of random walks, and using novel path-length-bound and graph-sampling approximation techniques. We experimentally validate our optimization techniques on large biological and bibliographic datasets. Our techniques can produce high quality (Top K) answers with a savings of up to an order of magnitude, in comparison to the evaluation time for the exact solution.

REFERENCES

• 1: http://www.ncbi.nlm.nih.gov/sites/entrez, 2008.
• 2: http://dblp.uni-trier.de/xml/
• 3: S. Agrawal, S. Chaudhuri and G. Das: "DBXplorer: A System for Keyword-Based Search Over Relational Databases", IEEE ICDE, 2002.
• 4: Gustavo O. Arocena , Alberto O. Mendelzon, WebOQL: Restructuring Documents, Databases, and Webs, Proceedings of the Fourteenth International Conference on Data Engineering, p.24-33, February 23-27, 1998
• 5: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 6: G. Bhalotia, C. Nakhe, A. Hulgeri, S. Chakrabarti and S. Sudarshan: "Keyword Searching and Browsing in Databases using BANKS", IEEE ICDE, 2002.
• 7: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 8: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing Partial Rankings, SIAM Journal on Discrete Mathematics, v.20 n.3, p.628-648, 2006 [doi>10.1137/05063088X]
• 9: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 11: Guang Feng , Tie-Yan Liu , Ying Wang , Ying Bao , Zhiming Ma , Xu-Dong Zhang , Wei-Ying Ma, AggregateRank: bringing order to web sites, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148187]
• 12: Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for a Web-site management system, ACM SIGMOD Record, v.26 n.3, p.4-11, Sept. 1997 [doi>10.1145/262762.262763]
• 13: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 14: 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]
• 15: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, ACM SIGMOD Record, v.26 n.2, p.171-182, June 1997
• 16: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 17: V. Hristidis, Y. Papakonstantinou and A. Balmin: "Keyword Proximity Search on XML Graphs", IEEE ICDE, 2003.
• 18: L. Katz: "A New Status Index derived from Sociometric Analysis". Psychometrika, 1953, vol. 18, issue 1.
• 19: G. Kasneci, F. M. Suchanek, G. Ifrim, M. Ramanath, G. Weikum: NAGA: Searching and Ranking Knowledge. ICDE 2008: 953--962.
• 20: David Konopnicki , Oded Shmueli, W3QS: A Query System for the World-Wide Web, Proceedings of the 21th International Conference on Very Large Data Bases, p.54-65, September 11-15, 1995
• 21: A. Mendelzon, G. Mihalia, T. Milo: Querying the World Wide Web. Journal on Digital Libraries 1(1):54--67, 1997.
• 22: Lan Nie , Brian D. Davison , Xiaoguang Qi, Topical link analysis for web search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148189]
• 23: L. Page, S. Brin, R. Motwani and T. Winograd: "The pagerank citation ranking: Bringing order to the web", Technical report, Stanford University, 1998.
• 24: Sriram Raghavan , Hector Garcia-Molina, Complex queries over web repositories, Proceedings of the 29th international conference on Very large data bases, p.33-44, September 09-12, 2003, Berlin, Germany
• 25: Louiqa Raschid , Yao Wu , Woei-Jyh Lee , María Esther Vidal , Panayiotis Tsaparas , Padmini Srinivasan , Aditya Kumar Sehgal, Ranking target objects of navigational queries, Proceedings of the 8th annual ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183550.1183558]
• 26: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 27: A. Singhal: "Modern Information Retrieval: A Brief Overview". Google, IEEE Data Eng. Bull, 2001.
• 28: SPARQL: Query Language for RDF: http://www.w3.org/TR/rdf-sparql-query/
• 29: R. Varadarajan, V. Hristidis, L. Raschid: Explaining and Reformulating Authority Flow Queries. IEEE ICDE, 2008.
• 30: R. Varadarajan, V. Hristidis, L. Raschid, M. Vidal, L. Lbanez and H. Drumond: Flexible and Efficient Querying and Ranking of Hyperlinked Data Source (extended version). http://dbir.cs.fiu.edu/WebSearch/GID.pdf.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ObjectRank, authority flow ranking, hard filters, soft filters