Query result clustering for object-level search

ABSTRACT

Query result clustering has recently attracted a lot of attention to provide users with a succinct overview of relevant results. However, little work has been done on organizing the query results for object-level search. Object-level search result clustering is challenging because we need to support diverse similarity notions over object-specific features (such as the price and weight of a product) of heterogeneous domains. To address this challenge, we propose a hybrid subspace clustering algorithm called Hydra. Algorithm Hydra captures the user perception of diverse similarity notions from millions of Web pages and disambiguates different senses using feature-based subspace locality measures. Our proposed solution, by combining wisdom of crowds and wisdom of data, achieves robustness and efficiency over existing approaches. We extensively evaluate our proposed framework and demonstrate how to enrich user experiences in object-level search using a real-world product search scenarios.

REFERENCES

• 1: Charu C. Aggarwal, A human-computer cooperative system for effective high dimensional clustering, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.221-226, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502542]
• 2: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 4: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 5: Mikhail Bilenko , Sugato Basu , Mehran Sahami, Adaptive Product Normalization: Using Online Learning for Record Linkage in Comparison Shopping, Proceedings of the Fifth IEEE International Conference on Data Mining, p.58-65, November 27-30, 2005 [doi>10.1109/ICDM.2005.18]
• 6: Chun-Hung Cheng , Ada Waichee Fu , Yi Zhang, Entropy-based subspace clustering for mining numerical data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.84-93, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312199]
• 7: David Cheng , Ravi Kannan , Santosh Vempala , Grant Wang, A divide-and-merge methodology for clustering, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1499-1525, December 2006 [doi>10.1145/1189769.1189779]
• 8: S. Goil, H. Nagesh, and A. Choudhary. Mafia: efficient and scalable subspace clustering for very large data sets. In Technical Report, Northwesthen University, 1999.
• 9: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 10: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 11: Xiang Ji , Wei Xu, Document clustering with prior knowledge, 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.1148241]
• 12: Ying Liu , Wenyuan Li , Yongjing Lin , Liping Jing, Spectral geometry for simultaneously clustering and ranking query search results, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390427]
• 13: Giansalvatore Mecca , Salvatore Raunich , Alessandro Pappalardo, A new algorithm for clustering search results, Data & Knowledge Engineering, v.62 n.3, p.504-522, September, 2007 [doi>10.1016/j.datak.2006.10.006]
• 14: Zaiqing Nie , Yunxiao Ma , Shuming Shi , Ji-Rong Wen , Wei-Ying Ma, Web object retrieval, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242584]
• 15: Z. Nie, J.-R. Wen, and W.-Y. Ma. Object-level vertical search. In CIDR, 2007.
• 16: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 17: Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004 [doi>10.1145/1007730.1007731]
• 18: Anne Patrikainen , Marina Meila, Comparing Subspace Clusterings, IEEE Transactions on Knowledge and Data Engineering, v.18 n.7, p.902-916, July 2006 [doi>10.1109/TKDE.2006.106]
• 19: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 20: Xuanhui Wang , ChengXiang Zhai, Learn from web search logs to organize search results, 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.1277759]
• 21: K.-G. Woo, J.-H. Lee, M.-H. Kim, and Y.-J. Lee. FINDIT: a fast intelligent subspace clusteing algorithm using diemsnion voting. Information and Sofeware Technology, 2004.
• 22: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, 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.860485]
• 23: Kevin Y. Yip , David W. Cheung , Michael K. Ng, HARP: A Practical Projected Clustering Algorithm, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1387-1397, November 2004 [doi>10.1109/TKDE.2004.74]
• 24: Kevin Y. Yip , David W. Cheung , Michael K. Ng, On Discovery of Extremely Low-Dimensional Clusters Using Semi-Supervised Projected Clustering, Proceedings of the 21st International Conference on Data Engineering, p.329-340, April 05-08, 2005 [doi>10.1109/ICDE.2005.96]
• 25: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 26: 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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms

Keywords:
object-level search, subspace clustering