EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data

ABSTRACT

Conventional keyword search engines are restricted to a given data model and cannot easily adapt to unstructured, semi-structured or structured data. In this paper, we propose an efficient and adaptive keyword search method, called EASE, for indexing and querying large collections of heterogenous data. To achieve high efficiency in processing keyword queries, we first model unstructured, semi-structured and structured data as graphs, and then summarize the graphs and construct graph indices instead of using traditional inverted indices. We propose an extended inverted index to facilitate keyword-based search, and present a novel ranking mechanism for enhancing search effectiveness. We have conducted an extensive experimental study using real datasets, and the results show that EASE achieves both high search efficiency and high accuracy, and outperforms the existing approaches significantly.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 3: S. Chaudhuri, R. Ramakrishnan, and G. Weikum. Integrating db and ir technologies: What is the sound of one hand clapping? In CIDR, pages 1--12, 2005.
• 4: 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
• 5: P. DeRose, W. Shen, F. Chen, Y. Lee, D. Burdick, A. Doan, and R. Ramakrishnan. Dblife: A community information management platform for the database research community. In CIDR, 2007.
• 6: 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.
• 7: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 8: Ronald Fagin, Fuzzy queries in multimedia database systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275488]
• 9: 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
• 10: L. Guo, J. Shanmugasundaram, and G. Yona. Topology search over biological databases. In ICDE, 2007.
• 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: 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]
• 13: 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
• 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, pages 367--378, 2003.
• 17: 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
• 18: 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]
• 19: Guoliang Li , Jianhua Feng , Jianyong Wang , Lizhu Zhou, Effective keyword search for valuable lcas over xml documents, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321447]
• 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: 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]
• 22: 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]
• 23: Alexander Markowetz , Yin Yang , Dimitris Papadias, Keyword search on relational data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247548]
• 24: M. Mutsuzaki, M. Theobald, A. Keijzer, J. Widom, P. Agrawal, andet al. Trio-one: Layering uncertainty and lineage on a conventional dbms. In CIDR, 2007.
• 25: 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]
• 26: Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 27: 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]
• 28: 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]
• 29: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Languages, Performance

Keywords:
graph index, indexing, keyword search, ranking