Efficient type-ahead search on relational data: a TASTIER approach

ABSTRACT

Existing keyword-search systems in relational databases require users to submit a complete query to compute answers. Often users feel "left in the dark" when they have limited knowledge about the data, and have to use a try-and-see approach for modifying queries and finding answers. In this paper we propose a novel approach to keyword search in the relational world, called Tastier. A Tastier system can bring instant gratification to users by supporting type-ahead search, which finds answers "on the fly" as the user types in query keywords. A main challenge is how to achieve a high interactive speed for large amounts of data in multiple tables, so that a query can be answered efficiently within milliseconds. We propose efficient index structures and algorithms for finding relevant answers on-the-fly by joining tuples in the database. We devise a partition-based method to improve query performance by grouping highly relevant tuples and pruning irrelevant tuples efficiently. We also develop a technique to answer a query efficiently by predicting the highly relevant complete queries for the user. We have conducted a thorough experimental evaluation of the proposed techniques on real data sets to demonstrate the efficiency and practicality of this new search paradigm.

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: 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: Holger Bast , Alexandru Chitea , Fabian Suchanek , Ingmar Weber, ESTER: efficient search on text, entities, and relations, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277856]
• 4: Holger Bast , Ingmar Weber, Type less, find more: fast autocompletion search with a succinct index, 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.1148234]
• 5: H. Bast and I. Weber. The completesearch engine: Interactive, efficient, and towards ir&db integration. In CIDR pages 88--95, 2007.
• 6: 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
• 7: Surajit Chaudhuri , Raghav Kaushik, Extending autocompletion to tolerate errors, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559919]
• 8: 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
• 9: B. D. Davison and H. Hirsh. Predicting sequences of user actions. In AAAI/ICML Workshop on Predicting the Future 1998.
• 10: 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 pages 836--845, 2007.
• 11: Korinna Grabski , Tobias Scheffer, Sentence completion, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009066]
• 12: 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]
• 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: Shengyue Ji , Guoliang Li , Chen Li , Jianhua Feng, Efficient interactive fuzzy keyword search, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526760]
• 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: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 19: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 20: Karen Kukich, Techniques for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
• 21: Guoliang Li , Jianhua Feng , Lizhu Zhou, Interactive search in XML data, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526857]
• 22: 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]
• 23: 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]
• 24: 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
• 25: 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]
• 26: 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]
• 27: 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]
• 28: Hiroshi Motoda , Kenichi Yoshida, Machine learning techniques to make computers easier to use, Artificial Intelligence, v.103 n.1-2, p.295-321, Aug. 1998 [doi>10.1016/S0004-3702(98)00062-9]
• 29: Arnab Nandi , H. V. Jagadish, Effective phrase prediction, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 30: J Pearl, Evidential reasoning using stochastic simulation of causal models, Artificial Intelligence, v.32 n.2, p.245-257, May 1987 [doi>10.1016/0004-3702(87)90012-9]
• 31: 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]
• 32: Hugh E. Williams , Justin Zobel , Dirk Bahle, Fast phrase querying with combined indexes, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.573-594, October 2004 [doi>10.1145/1028099.1028102]
• 33: 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]
• 34: 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]

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.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
keyword search, query prediction, type-ahead search