Keyword search on structured and semi-structured data

ABSTRACT

Empowering users to access databases using simple keywords can relieve the users from the steep learning curve of mastering a structured query language and understanding complex and possibly fast evolving data schemas. In this tutorial, we give an overview of the state-of-the-art techniques for supporting keyword search on structured and semi-structured data, including query result definition, ranking functions, result generation and top-k query processing, snippet generation, result clustering, query cleaning, performance optimization, and search quality evaluation. Various data models will be discussed, including relational data, XML data, graph-structured data, data streams, and workflows. We also discuss applications that are built upon keyword search, such as keyword based database selection, query generation, and analytical processing. Finally we identify the challenges and opportunities of future research to advance the field.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A system for keyword-based search over relational databases. In ICDE, 2002.
• 2: Sihem Amer-Yahia , Jayavel Shanmugasundaram, XML full-text search: challenges and opportunities, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Zhifeng Bao , Tok Wang Ling , Bo Chen , Jiaheng Lu, Effective XML Keyword Search with Relevance Oriented Ranking, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.517-528, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.16]
• 4: G. Bhalotia, C. Nakhe, A. Hulgeri, S. Chakrabarti, and S. Sudarshan. Keyword Searching and Browsing in Databases using BANKS. In ICDE, 2002.
• 5: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 6: Bhavana Bharat Dalvi , Meghana Kshirsagar , S. Sudarshan, Keyword search on external memory data graphs, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453982]
• 7: Ian De Felipe , Vagelis Hristidis , Naphtali Rishe, Keyword Search on Spatial Databases, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.656-665, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497474]
• 8: 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, 2007.
• 9: 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
• 10: Konstantin Golenberg , Benny Kimelfeld , Yehoshua Sagiv, Keyword proximity search in complex data graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376708]
• 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: Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142352]
• 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 , Nick Koudas , Yannis Papakonstantinou , Divesh Srivastava, Keyword Proximity Search in XML Trees, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.525-539, April 2006 [doi>10.1109/TKDE.2006.61]
• 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: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword proximity search on xml graphs. In ICDE, 2003.
• 17: Yu Huang , Ziyang Liu , Yi Chen, eXtract: a snippet generation system for XML search, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454181]
• 18: Yu Huang , Ziyang Liu , Yi Chen, Query biased snippet generation in XML search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376651]
• 19: INEX. Initiative for the evaluation of xml retrieval. http://inex.is.informatik.uni-duisburg.de/.
• 20: H. V. Jagadish , Adriane Chapman , Aaron Elkiss , Magesh Jayapandian , Yunyao Li , Arnab Nandi , Cong Yu, Making database systems usable, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247483]
• 21: 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
• 22: KEYS 2009. The first international workshop on keyword search on structured data, 2009.
• 23: Benny Kimelfeld , Yehoshua Sagiv, Finding and approximating top-k answers in keyword proximity search, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142377]
• 24: Lingbo Kong , Rémi Gilleron , Aurélien Lemay Mostrare, Retrieving meaningful relaxed tightest fragments for XML keyword search, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516454]
• 25: Georgia Koutrika , Alkis Simitsis , Yannis Ioannidis, Précis: The Essence of a Query Answer, Proceedings of the 22nd International Conference on Data Engineering, p.69, April 03-07, 2006 [doi>10.1109/ICDE.2006.114]
• 26: Georgia Koutrika , Zahra Mohammadi Zadeh , Hector Garcia-Molina, Data clouds: summarizing keyword search results over structured data, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516406]
• 27: Guoliang Li , Jianhua Feng , Jianyong Wang , Lizhu Zhou, An effective and versatile keyword search engine on heterogenous data sources, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454198]
• 28: Guoliang Li , Beng Chin Ooi , Jianhua Feng , Jianyong Wang , Lizhu Zhou, EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376706]
• 29: Guoliang Li , Xiaofang Zhou , Jianhua Feng , Jianyong Wang, Progressive Keyword Search in Relational Databases, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1183-1186, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.196]
• 30: Wen-Syan Li , K. Selçuk Candan , Quoc Vu , Divyakant Agrawal, Retrieving and organizing web pages by “information unit”, Proceedings of the 10th international conference on World Wide Web, p.230-244, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372057]
• 31: Yunyao Li , Ishan Chaudhuri , Huahai Yang , Satinder Singh , H. V. Jagadish, DaNaLIX: a domain-adaptive natural language interface for querying XML, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247643]
• 32: Yunyao Li , Cong Yu , H. V. Jagadish, Schema-free XQuery, Proceedings of the Thirtieth international conference on Very large data bases, p.72-83, August 31-September 03, 2004, Toronto, Canada
• 33: 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]
• 34: Ziyang Liu , Yi Chen, Identifying meaningful return information for XML keyword search, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247518]
• 35: Ziyang Liu , Yi Chen, Answering Keyword Queries on XML Using Materialized Views, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1501-1503, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497603]
• 36: Ziyang Liu , Yi Cher, Reasoning and identifying relevant matches for XML keyword search, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453956]
• 37: Ziyang Liu , Jeffrey Walker , Yi Chen, XSeek: a semantic XML search engine using keywords, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 38: 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]
• 39: Yi Luo , Wei Wang , Xuemin Lin, SPARK: A Keyword Search Engine on Relational Databases, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1552-1555, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497619]
• 40: Alexander Markowetz , Yin Yang , Dimitris Papadias, Reachability Indexes for Relational Keyword Search, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1163-1166, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.191]
• 41: Ken Q. Pu , Xiaohui Yu, Keyword query cleaning, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453955]
• 42: M. Sayyadian, H. LeKhac, A. Doan, and L. Gravano. Efficient keyword search across heterogeneous relational databases. In ICDE, 2007.
• 43: Feng Shao , Lin Guo , Chavdar Botev , Anand Bhaskar , Muthiah Chettiar , Fan Yang , Jayavel Shanmugasundaram, Efficient keyword search over virtual XML views, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 44: Qihong Shao , Peng Sun , Yi Chen, WISE: A Workflow Information Search Engine, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1491-1494, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.89]
• 45: 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]
• 46: Chong Sun , Chee-Yong Chan , Amit K. Goenka, Multiway SLCA-based keyword search in XML data, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242713]
• 47: Databases and IR: Perspectives of a SQL guy. NSF Information and Data Management PI Workshop, 2003.
• 48: Partha Pratim Talukdar , Marie Jacob , Muhammad Salman Mehmood , Koby Crammer , Zachary G. Ives , Fernando Pereira , Sudipto Guha, Learning to create data-integrating queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453941]
• 49: Yufei Tao , Jeffrey Xu Yu, Finding frequent co-occurring terms in relational keyword search, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516456]
• 50: Sandeep Tata , Guy M. Lohman, SQAK: doing more with keywords, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376705]
• 51: Thanh Tran , Haofen Wang , Sebastian Rudolph , Philipp Cimiano, Top-k Exploration of Query Candidates for Efficient Keyword Search on Graph-Shaped (RDF) Data, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.405-416, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.119]
• 52: Quang Hieu Vu , Beng Chin Ooi , Dimitris Papadias , Anthony K. H. Tung, A graph method for keyword-based selection of the top-K databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376707]
• 53: Shan Wang , Zhaohui Peng , Jun Zhang , Lu Qin , Sheng Wang , Jeffrey Xu Yu , Bolin Ding, NUITS: a novel user interface for efficient keyword search over databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 54: Gerhard Weikum, DB&IR: both sides now, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247484]
• 55: Ping Wu , Yannis Sismanis , Berthold Reinwald, Towards keyword-driven analytical processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247549]
• 56: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 57: Yu Xu , Yannis Papakonstantinou, Efficient LCA based keyword search in XML data, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353408]
• 58: Bei Yu , Guoliang Li , Karen Sollins , Anthony K. H. Tung, Effective keyword-based selection of relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247498]
• 59: Dongxiang Zhang , Yeow Meng Chee , Anirban Mondal , Anthony K. H. Tung , Masaru Kitsuregawa, Keyword Search in Spatial Databases: Towards Searching by Document, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.688-699, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.77]
• 60: Bin Zhou , Jian Pei, Answering aggregate keyword queries on relational databases using minimal group-bys, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516374]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
databases, keyword search, top-k, xml