Improvement of HITS-based algorithms on web documents

ABSTRACT

In this paper, we present two ways to improve the precision of HITS-based algorithms on Web documents. First, by analyzing the limitations of current HITS-based algorithms, we propose a new weighted HITS-based method that assigns appropriate weights to in-links of root documents. Then, we combine content analysis with HITS-based algorithms and study the effects of four representative relevance scoring methods, VSM, Okapi, TLS, and CDR, using a set of broad topic queries. Our experimental results show that our weighted HITS-based method performs significantly better than Bharat's improved HITS algorithm. When we combine our weighted HITS-based method or Bharat's HITS algorithm with any of the four relevance scoring methods, the combined methods are only marginally better than our weighted HITS-based method. Between the four relevance-scoring methods, there is no significant quality difference when they are combined with a HITS-based algorithm.

REFERENCES

• 1: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 2: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Computer Networks and ISDN Systems, v.30 n.1-7, p.65-74, April 1, 1998
• 3: Huan Chang , David Cohn , Andrew McCallum, Learning to Create Customized Authority Lists, Proceedings of the Seventeenth International Conference on Machine Learning, p.127-134, June 29-July 02, 2000
• 4: Steve Chien , Jonathan Gratch , Michael Burl, On the Efficient Allocation of Resources for Hypothesis Evaluation: A Statistical Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.7, p.652-665, July 1995 [doi>10.1109/34.391408]
• 5: S. Chien, A. Stechert, and D. Mutz. Efficient heuristic hypothesis ranking. Journal of Artificial Intelligence Research, pages 375--397, 10 (1999).
• 6: C. L. A. Clark, G. V. Cormack, and F. J. Burkowski. Shortest substring ranking. In Fourth Text Retrieval Conference (TREC-4), pages 295--304, Gaithersburg, MD, 1995.
• 7: Charles L. A. Clarke , Gordon V. Cormack , Elizabeth A. Tudhope, Relevance ranking for one to three term queries, Information Processing and Management: an International Journal, v.36 n.2, p.291-311, Jan.1.2000 [doi>10.1016/S0306-4573(99)00017-5]
• 8: S. J. Clarke and P. Willett. Estimating the recall performance of web search engines. Aslib Proceedings, pages 184--189, July/August 1997.
• 9: W. Ding and G. Marchionini. A comparative study of web search service performance. In ASIS'96: Proc. 59th ASIS Annual Meeting, pages 136--141, Medford, NJ: Information Today, Inc., 1996.
• 10: A. Farahat, T. LoFaro, and J. C. Miller. Modification of kleinberg's hits algorithm using matrix exponentiation and web log records. In Proceedings of the 24th International Conference on Research and Development in Information Retrieval (SIGIR 2001), New Orleans, USA, September 2001.
• 11: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 12: David A. Grossman , Ophir Frieder , David O. Holmes , David C. Roberts, Integrating structured data and text: a relational approach, Journal of the American Society for Information Science, v.48 n.2, p.122-132, Feb. 1997 [doi>10.1002/(SICI)1097-4571(199702)48:2<122::AID-ASI3>3.0.CO;2-#]
• 13: D. Hawking, P. Bailey, and N. Craswell. Acsys trec-8 experiments. In Proceedings of the TREC-8, 1999.
• 14: D. Hawking, N. Craswell, and P. Thistlewaste. Overview of the trec-7 very large collection track. In Proceedings of the TREC-7, 1998.
• 15: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 17: H. Vernon Leighton , Jaideep Srivastava, First 20 precision among World Wide Web search services (search engines), Journal of the American Society for Information Science, v.50 n.10, p.870-881, 1999 [doi>10.1002/(SICI)1097-4571(1999)50:10<870::AID-ASI4>3.3.CO;2-7]
• 18: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 19: A new statistical method for performance evaluation of search engines, Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence, p.208, November 13-15, 2000
• 20: S. L. MacCall and A. D. Cleveland. A relevance-based quantitative measure for internet information retrieval evaluation. In Proceedings of the American Society for Information Science 1999 Annual Meeting, pages 763--768, 1999.
• 21: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 22: Longzhuang Li , Yi Shang, A new method for automatic performance comparison of search engines, World Wide Web, v.3 n.4, p.241-247, December 2000 [doi>10.1023/A:1018790907285]
• 23: Amit Singhal , Gerard Salton , Mandar Mitra , Chris Buckley, Document Length Normalization, Cornell University, Ithaca, NY, 1995
• 24: D. Sullivan. www.searchenginewatch.com/reports/sizes.html, Search Engine Sizes, August 15, 2001.
• 25: R. Wilkinson, J. J. Zobel, and R. Sacks-Davis. Similarity measures for short queries. In Fourth Text Retrieval Conference (TREC-4), pages 277--285, Gaithersburg, MD, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Measurement, Performance

Keywords:
HITS-based algorithms, information retrieval, relevance scoring methods