Keyword search on external memory data graphs

ABSTRACT

Keyword search on graph structured data has attracted a lot of attention in recent years. Graphs are a natural "lowest common denominator" representation which can combine relational, XML and HTML data. Responses to keyword queries are usually modeled as trees that connect nodes matching the keywords.

In this paper we address the problem of keyword search on graphs that may be significantly larger than memory. We propose a graph representation technique that combines a condensed version of the graph (the "supernode graph") which is always memory resident, along with whatever parts of the detailed graph are in a cache, to form a multi-granular graph representation. We propose two alternative approaches which extend existing search algorithms to exploit multigranular graphs; both approaches attempt to minimize IO by directing search towards areas of the graph that are likely to give good results. We compare our algorithms with a virtual memory approach on several real data sets. Our experimental results show significant benefits in terms of reduction in IO due to our algorithms.

REFERENCES

• 1: Sanjay Agrawal, Surajit Chaudhari, and Gautam Das. DBXplorer: A system for keyword-based search search over relational databases. ICDE, 2002.
• 2: 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
• 3: Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. ICDE, 2002.
• 4: Kumar Gaurav Bijay. Towards external memory algorithms for keyword-search in relational databases. Bachelors Thesis, under the guidance of S. Sudarshan, 2006.
• 5: Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
• 6: Adam L. Buchsbaum , Jefferey R. Westbrook, Maintaining hierarchical graph views, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 09-11, 2000, San Francisco, California, United States
• 7: Soumen Chakrabarti , Jeetendra Mirchandani , Arnab Nandi, SPIN: searching personal information networks, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076186]
• 8: Edward P. F. Chan , Ning Zhang, Finding shortest paths in large network systems, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512197]
• 9: Bolin Ding, Jeffrey Xu Yu, Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin. Finding top-k min-cost connected trees in databases. ICDE, 2007.
• 10: Jens Graupmann , Ralf Schenkel , Gerhard Weikum, The SphereSearch engine for unified ranked retrieval of heterogeneous XML and web documents, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 11: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 12: Nitin Gupta. EMBANKS: Towards disk based algorithms for keyword-search in structured databases. Bachelors Thesis, under the guidance of S. Sudarshan, 2006.
• 13: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, BLINKS: ranked keyword searches on graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247516]
• 14: Vagelis Hristidis , Luis Gravano , Yannis Papakonstantinou, Efficient IR-style keyword search over relational databases, Proceedings of the 29th international conference on Very large data bases, p.850-861, September 09-12, 2003, Berlin, Germany
• 15: 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
• 16: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 17: George Karypis , Vipin Kumar, Analysis of multilevel graph partitioning, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.29-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224229]
• 18: C. E. Leiserson , S. Rao , S. Toledo, Efficient out-of-core algorithms for linear relaxation using blocking covers, Proceedings of the Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, p.704-713, November 03-05, 1993 [doi>10.1109/SFCS.1993.366817]
• 19: Wen-Syan Li , K. Selçuk Candan , Quoc Vu , Divyakant Agrawal, Query Relaxation by Structure and Semantics for Retrieval of Logical Web Documents, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.768-791, July 2002 [doi>10.1109/TKDE.2002.1019213]
• 20: Fang Liu , Clement Yu , Weiyi Meng , Abdur Chowdhury, Effective keyword search in relational databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142536]
• 21: Yi Luo , Xuemin Lin , Wei Wang , Xiaofang Zhou, Spark: top-k keyword query in relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247495]
• 22: M. H. Nodine, M. T. Goodrich, and J. S. Vitter. Blocking for external graph searching. Algorithmica, 16: 181--214, 1996.
• 23: Sriram Raghavan and Hector Garcia-Molina. Representing Web graphs. ICDE, pages 405--416, 2003.
• 24: Shashi Shekhar , Andrew Fetterer , Bjajesh Goyal, Materialization Trade-Offs in Hierarchical Shortest Path Algorithms, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.94-111, July 15-18, 1997
• 25: Qi Su , Jennifer Widom, Indexing Relational Database Content Offline for Efficient Keyword-Based Search, Proceedings of the 9th International Database Engineering & Application Symposium, p.297-306, July 25-27, 2005 [doi>10.1109/IDEAS.2005.36]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Performance