Addressing diverse user preferences in SQL-query-result navigation

ABSTRACT

Database queries are often exploratory and users often find their queries return too many answers, many of them irrelevant. Existing work either categorizes or ranks the results to help users locate interesting results. The success of both approaches depends on the utilization of user preferences. However, most existing work assumes that all users have the same user preferences, but in real life different users often have different preferences. This paper proposes a two-step solution to address the diversity issue of user preferences for the categorization approach. The proposed solution does not require explicit user involvement. The first step analyzes query history of all users in the system offline and generates a set of clusters over the data, each corresponding to one type of user preferences. When user asks a query, the second step presents to the user a navigational tree over clusters generated in the first step such that the user can easily select the subset of clusters matching his needs. The user then can browse, rank, or categorize the results in selected clusters. The navigational tree is automatically constructed using a cost-based algorithm which considers the cost of visiting both intermediate nodes and leaf nodes in the tree. An empirical study demonstrates the benefits of our approach.

REFERENCES

• 1: Rakesh Agrawal , Ralf Rantzau , Evimaria Terzi, Context-sensitive ranking, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142517]
• 2: S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis. Automated ranking of database query results. In CIDR, 2003.
• 3: Christopher Ahlberg , Ben Shneiderman, Visual information seeking: tight coupling of dynamic query filters with starfield displays, Proceedings of the SIGCHI conference on Human factors in computing systems: celebrating interdependence, p.313-317, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/191666.191775]
• 4: L. Breiman, J. Friedman, C. J. Stone, and R. Olshen. Classification and Regression Trees. CRC Press, 1984.
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690 ]
• 6: S. Card, J. MacKinlay, and B. Shneiderman. Readings in Information Visualization: Using Vision to Think. Morgan Kaufmann, 1999.
• 7: 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]
• 8: Kaushik Chakrabarti , Venkatesh Ganti , Jiawei Han , Dong Xin, Ranking objects based on relationships, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142516]
• 9: S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic ranking of database query results. In VLDB, pages 888--899, 2004.
• 10: G. Das, V. Hristidis, N. Kapoor, and S. Sudarshan. Ordering the attributes of query results. In SIGMOD, 2006.
• 11: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 12: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, Enhanced word clustering for hierarchical text classification, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775076]
• 13: Lev Finkelstein , Evgeniy Gabrilovich , Yossi Matias , Ehud Rivlin , Zach Solan , Gadi Wolfman , Eytan Ruppin, Placing search in context: the concept revisited, Proceedings of the 10th international conference on World Wide Web, p.406-414, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372094]
• 14: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 15: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843 ]
• 16: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 17: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 18: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 19: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 20: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 21: J. R. Quinlan. C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.
• 22: Xuehua Shen , Bin Tan , ChengXiang Zhai, Context-sensitive information retrieval using implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076045]
• 23: K. Sugiyama, K. Hatano, and M. Yoshikawa. Adaptive web search based on user profile constructed without any effort from users. In WWW, 2004.
• 24: Ming Tan, Cost-Sensitive Learning of Classification Knowledge and Its Applications in Robotics, Machine Learning, v.13 n.1, p.7-33, Oct. 1993 [doi>10.1023/A:1022679428250]
• 25: K. M. Ting, An Instance-Weighting Method to Induce Cost-Sensitive Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.659-665, May 2002 [doi>10.1109/TKDE.2002.1000348 ]
• 26: Lisa Tweedie , Bob Spence , David Williams , Ravinder Bhogal, The attribute explorer, Conference companion on Human factors in computing systems, p.435-436, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/259963.260433]
• 27: Vivisimo.com. Vivisimo clustering engine. http://vivisimo.com/.
• 28: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, 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.1009030]

INDEX TERMS

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

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

General Terms:
Algorithms, Human Factors

Keywords:
data exploration, user preferences