Implicit link analysis for small web search

ABSTRACT

Current Web search engines generally impose link analysis-based re-ranking on web-page retrieval. However, the same techniques, when applied directly to small web search such as intranet and site search, cannot achieve the same performance because their link structures are different from the global Web. In this paper, we propose an approach to constructing implicit links by mining users' access patterns, and then apply a modified PageRank algorithm to re-rank web-pages for small web search. Our experimental results indicate that the proposed method outperforms content-based method by 16%, explicit link-based PageRank by 20% and DirectHit by 14%, respectively.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: AltaVista. <http://www.altavista.com>.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Pavel Berkhin , Jonathan D. Beche , Dee Jay Randall, Interactive path analysis of web site traffic, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.414-419, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502574]
• 5: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 7: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 8: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 9: Chen M., Hearst M., Hong J. and Lin J. Cha-Cha: a system for organizing intranet search results. In Proceedings of the 2nd USITS, Boulder, CO, October 1999.
• 10: Cooley R., Mobasher B. and Srivastava J. Data preparation for mining World Wide Web browsing patterns. Knowledge and Information Systems, 1(1):5--32, 1999.
• 11: Robert Cooley , Pang-Ning Tan , Jaideep Srivastava, Discovery of Interesting Usage Patterns from Web Data, Revised Papers from the International Workshop on Web Usage Analysis and User Profiling, p.163-182, August 15, 1999
• 12: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 13: DirectHit. <http://www.directhit.com>.
• 14: Google. <http://www.google.com>.
• 15: Hagen P., Manning H. and Paul Y. Must search stink? The Forrester report, Forrester, June 2000.
• 16: Hawking D., Voorhees E., Bailey P. and Craswell N. Overview of TREC-8 web track. In Proc. of TREC-8, 131--150, Gaithersburg MD, November 1999.
• 17: Hearst M. Next generation web search: setting our sites. IEEE Data Engineering Bulletin, 23(3):38--48, September 2000.
• 18: Henzinger M. R. Link analysis in web information retrieval. IEEE Data Engineering Bulletin, 23(3):3--8, September 2000.
• 19: Kessler M. M. Bibliographic coupling between scientific papers. American Documentation, 14(1):10--25, 1963.
• 20: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 21: Kleinberg J. M., Kumar R., Raghavan P., Rajagopalan S. and Tomkins A. S. The Web as a graph: measurements, models, and methods. In Proc. of COCOON'99, 26--28, Tokyo, 1999.
• 22: Levene M. and Loizou G. Web interaction and the navigation problem in hypertext. Encyclopedia of Microcomputers, 28(7):381-398, Marcel Dekker, NY, 2001.
• 23: Levene M. and Wheeldon R. A web site navigation engine. In Proc. of WWW10, Hong Kong, May 2001.
• 24: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 25: Joel C. Miller , Gregory Rae , Fred Schaefer , Lesley A. Ward , Thomas LoFaro , Ayman Farahat, Modifications of Kleinberg's HITS algorithm using matrix exponentiation and web log records, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.444-445, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384086]
• 26: Takehiro Nakayama , Hiroki Kato , Yohei Yamane, Discovering the gap between Web site designers' expectations and users' behavior, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.811-822, June 2000, Amsterdam, The Netherlands
• 27: Page L., Brin S., Motwani R. and Winograd T. The PageRank citation ranking: bringing order to the Web. Technical report, Stanford University Database Group, 1998.
• 28: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Hua Zhu, Mining Access Patterns Efficiently from Web Logs, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.396-407, April 18-20, 2000
• 29: Prabhakar Raghavan, Social Networks: From the Web to the Enterprise, IEEE Internet Computing, v.6 n.1, p.91-94, January 2002 [doi>10.1109/4236.989007]
• 30: Robertson S. E., Walker S., Beaulieu M. M., and Gatford M., Payne A. 1995. Okapi at TREC-4. In Proc. of TREC-4, 73--96, NIST Special Publication 500-236, October 1996.
• 31: Ramakrishnan Srikant , Yinghui Yang, Mining web logs to improve website organization, Proceedings of the 10th international conference on World Wide Web, p.430-437, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372097]
• 32: Qiang Yang , Haining Henry Zhang , Tianyi Li, Mining web logs for prediction models in WWW caching and prefetching, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.473-478, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502584]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
information retrieval, link analysis, log mining, web search