Minimum-effort driven dynamic faceted search in structured databases

ABSTRACT

In this paper, we propose minimum-effort driven navigational techniques for enterprise database systems based on the faceted search paradigm. Our proposed techniques dynamically suggest facets for drilling down into the database such that the cost of navigation is minimized. At every step, the system asks the user a question or a set of questions on different facets and depending on the user response, dynamically fetches the next most promising set of facets, and the process repeats. Facets are selected based on their ability to rapidly drill down to the most promising tuples, as well as on the ability of the user to provide desired values for them. Our facet selection algorithms also work in conjunction with any ranked retrieval model where a ranking function imposes a bias over the user preferences for the selected tuples. Our methods are principled as well as efficient, and our experimental study validates their effectiveness on several application scenarios.

REFERENCES

• 1: Kaushik Chakrabarti , Surajit Chaudhuri , Seung-won Hwang, Automatic categorization of query results, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007653]
• 2: Venkatesan T. Chakaravarthy , Vinayaka Pandit , Sambuddha Roy , Pranjal Awasthi , Mukesh Mohania, Decision trees for entity identification: approximation algorithms and hardness results, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265538]
• 3: Jennifer English , Marti Hearst , Rashmi Sinha , Kirsten Swearingen , Ka-Ping Yee, Hierarchical faceted metadata in site search interfaces, CHI '02 extended abstracts on Human factors in computing systems, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/506443.506517]
• 4: W. Dakka, P. G. Ipeirotis and K. R. Wood. Faceted Browsing over Large Databases of Text-Annotated Objects. ICDE 2007.
• 5: 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]
• 6: E. Stoica, M. Hearst and M. Richardson. Automating Creation of Hierarchical Faceted Metadata Structures. In the proceedings of NAACL-HLT 2007.
• 7: Surajit Chaudhuri , Gautam Das , Vagelis Hristidis , Gerhard Weikum, Probabilistic information retrieval approach for ranking of database query results, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1134-1168, September 2006 [doi>10.1145/1166074.1166085]
• 8: Sanjay Agrawal , Surajit Chaudhuri , Gautam Das, DBXplorer: enabling keyword search over relational databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564782]
• 9: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 10: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 11: Ykä Huhtala , Juha Kärkkäinen , Pasi Porkka , Hannu Toivonen, Efficient Discovery of Functional and Approximate Dependencies Using Partitions, Proceedings of the Fourteenth International Conference on Data Engineering, p.392-401, February 23-27, 1998
• 12: 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
• 13: B. Aditya, G. Bhalotia, S. Chakrabarti, A. Hulgeri, C. Nakhe, P. S. Sudarshan. BANKS: Browsing and Keyword Searching in Relational Databases. ICDE 2003.
• 14: C. L. Lucchesi and S. L. Osborn. Candidate Keys for Relations. J. Comput. Syst. Sci., 17(2): 1978.
• 15: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest—A Framework for Fast Decision Tree Construction of Large Datasets, Data Mining and Knowledge Discovery, v.4 n.2-3, p.127-162, July 2000 [doi>10.1023/A:1009839829793]
• 16: http://www.l3s.de/growbag/demonstrators.php.
• 17: J. Shlens. A Tutorial on Principal Component Analysis. Institute for Nonlinear Science, UCSD, 2005.
• 18: Gautam Das , Vagelis Hristidis , Nishant Kapoor , S. Sudarshan, Ordering the attributes of query results, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142518]
• 19: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 20: S. Agrawal, S. Chaudhuri, G. Das, A. Gionis. Automated Ranking of Database Query Results. CIDR 2003.
• 21: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 22: E. N. Efthimiadis. Query Expansion. Annual Review of Information Systems and Technology 1996.
• 23: Ori Ben-Yitzhak , Nadav Golbandi , Nadav Har'El , Ronny Lempel , Andreas Neumann , Shila Ofek-Koifman , Dafna Sheinwald , Eugene Shekita , Benjamin Sznajder , Sivan Yogev, Beyond basic faceted search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341539]
• 24: Wisam Dakka , Panagiotis G. Ipeirotis , Kenneth R. Wood, Automatic construction of multifaceted browsing interfaces, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099738]
• 25: Innes Martin , Joemon M. Jose, A personalised information retrieval tool, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860532]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Search process

General Terms:
Algorithms, Design, Performance

Keywords:
data browsing, dynamic facet generation, minimum-effort entity search