Efficient keyword proximity search using a frontier-reduce strategy based on d-distance graph index

ABSTRACT

Current keyword proximity search approaches on general graph lack effective means to reduce the search space, and thus suffer from low efficiency when dealing with large search space. In this paper, we present a novel approach in order to address this problem. Our approach employs a best-effort frontier-reduce strategy that aims to find a set of subgraphs containing the best answers. So we need only to search over these small subgraphs to get the top-k answers, and thus the efficiency can be significantly improved. To fulfill our strategy, we define a d-distance subgraph with upper size bound, and extract such subgraphs from the graph to build a new index structure combining the mappings between keywords, vertexes and subgraphs, by which we can quickly look up the target subgraphs for specific queries. Then, we perform an efficient algorithm to find the top-k answers, which can overcome the subgraph overlap problem and support existing optimal prioritization techniques.

Lastly, we evaluate the effectiveness and efficiency of our approach with extensive experiments. The experimental results show that our approach can outperform existing approaches by a large margin with little or none loss of answer quality.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In ICDE Conference Proceedings, pages 5--16, 2002.
• 2: A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB Conference Proceedings, pages 564--75, 2004.
• 3: G. Bhalotia, A. Hulgeriy, C. Nakhez, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using banks. In ICDE Conference Proceedings, pages 431--440, 2002.
• 4: B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin. Finding top-k min-cost connected trees in databases. In ICDE Conference Proceedings, pages 836--845, 2007.
• 5: R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. Proximity search in databases. In VLDB Conference Proceedings, pages 26--37, 1998.
• 6: K. Golenberg, B. Kimelfeld, and Y. Sagiv. Keyword proximity search in complex data graphs. In SIGMOD Conference Proceedings, pages 927--940, 2008.
• 7: L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. Xrank: Ranked keyword search over xml documents. In SIGMOD Conference Proceedings, pages 16--27, 2003.
• 8: A. Halevy, M. Franklin, and D. Maier. Principles of dataspace systems. In PODS Conference Proceedings, pages 1--9, 2006.
• 9: H. He, H. Wang, J. Yang, and P. S. Yu. Blinks: Ranked keyword searches on graphs. In SIGMOD Conference Proceedings, pages 305--316, 2007.
• 10: V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB Conference Proceedings, pages 850--861, 2003.
• 11: V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In VLDB Conference Proceedings, pages 670--681, 2002.
• 12: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword proximity search on xml graphs. In ICDE Conference Proceedings, pages 367--378, 2003.
• 13: V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In SIGMOD Conference Proceedings, pages 505--516, 2005.
• 14: G. Li, J. Feng, J. Wang, and L. Zhou. Effective keyword search for valuable lcas over xml documents. In CIKM Conference Proceedings, pages 31--40, 2007.
• 15: G. Li, B. C. Ooi, J. Feng, J. Wang, and L. Zhou. Ease: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In SIGMOD Conference Proceedings, pages 903--914, 2008.
• 16: W.-S. Li, K. Candan, Q. Vu, and D. Agrawal. Retrieving and organizing web pages by "information unit". In WWW Conference Proceedings, pages 230--244, 2001.
• 17: F. Liu, C. Yu, W. Meng, and A. Chowdhury. Effective keyword search in relational databases. In SIGMOD Conference Proceedings, pages 563--574, 2006.
• 18: Y. Luo, X. Lin, W. Wang, and X. Zhou. Spark: Top-k keyword query in relational databases. In SIGMOD Conference Proceedings, pages 115--126, 2007.
• 19: M. Sayyadian, H. LeKhac, A. Doan, and L. Gravano. Efficient keyword search across heterogeneous relational databases. In ICDE Conference Proceedings, pages 346--355, 2007.
• 20: C. Sun, C.-Y. Chan, and A. K. Goenka. Multiway slca-based keyword search in xml data. In WWW Conference Proceedings, pages 1043--1052, 2007.
• 21: Y. Xu and Y. Papakonstantinou. Efficient keyword search for smallest lcas in xml databases. In SIGMOD Conference Proceedings, pages 527--538, 2005.
• 22: Y. Xu and Y. Papakonstantinou. Efficient lca based keyword search in xml data. In EDBT Conference Proceedings, pages 535--546, 2008.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Design, Performance

Keywords:
graph index, keyword proximity search, search space reduction