Query based optimal web site clustering using simulated annealing

ABSTRACT

Clustering is a viable technique to deal with the scaling issue for the web documents, which has been known for complicated combinatorial optimization problem. It is hard to develop a generally applicable optimal algorithm on the web document clustering and classification for which a simulated annealing algorithm is developed. The web document classification problem is addressed as the problem of best describing match between a web query and a hypothesized web object. The normalized term frequency and inverse document frequency coefficient is used as a measure of the match. Test beds are generated on-line during the search by transforming web sites. As a result, web sites can be clustered optimally in terms of keyword vectors of corresponding web documents.

REFERENCES

• 1: J. Edmonds, "Optimum Branching," Journal of Research of the National Bureau of Standards, 71B, pp. 233--240. 1967.
• 2: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 3: O. Etzioni, M. Cafarella, D. Downey, A. Popescu, T. Shaked, S. Soderland, D. Weld, and A. Yates, "Methods for Domain-Independent Information Extraction from the web: An Experimental Comparison," Proc. AAAI, pp. 391--398, 2004.
• 4: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: John Garofalakis , Panagiotis Kappos , Dimitris Mourloukos, Web Site Optimization Using Page Popularity, IEEE Internet Computing, v.3 n.4, p.22-29, July 1999 [doi>10.1109/4236.780957]
• 6: P. A. Gloor, and S. B. Dynes, "Cybermap - Visually Navigating the Web," Journal of Visual Languages and Computing, vol. 9, no. 3, pp. 319--336, 1998.
• 7: Eric Glover , David M. Pennock , Steve Lawrence , Robert Krovetz, Inferring hierarchical descriptions, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584876]
• 8: Mohamed Hammami , Youssef Chahir , Liming Chen, WebGuard: A Web Filtering Engine Combining Textual, Structural, and Visual Content-Based Analysis, IEEE Transactions on Knowledge and Data Engineering, v.18 n.2, p.272-284, February 2006 [doi>10.1109/TKDE.2006.34]
• 9: Taher H. Haveliwala, Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.784-796, July 2003 [doi>10.1109/TKDE.2003.1208999]
• 10: Jingyu Hou , Yanchun Zhang, Effectively Finding Relevant Web Pages from Linkage Information, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.940-951, July 2003 [doi>10.1109/TKDE.2003.1209010]
• 11: Melody Y. Ivory , Marti A. Hearst, Improving Web Site Design, IEEE Internet Computing, v.6 n.2, p.56-63, March 2002 [doi>10.1109/4236.991444]
• 12: 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]
• 13: Ray R. Larson, TREC interactive with Chesire II, Information Processing and Management: an International Journal, v.37 n.3, p.485-505, May 2001 [doi>10.1016/S0306-4573(00)00058-3]
• 14: Kristina Lerman , Lise Getoor , Steven Minton , Craig Knoblock, Using the structure of Web sites for automatic segmentation of tables, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007584]
• 15: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 16: Olfa Nasraoui , Cesar Cardona , Carlos Rojas, Using retrieval measures to assess similarity in mining dynamic web clickstreams, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081921]
• 17: Mark W. Newman , James A. Landay, Sitemaps, storyboards, and specifications: a sketch of Web site design practice, Proceedings of the 3rd conference on Designing interactive systems: processes, practices, methods, and techniques, p.263-274, August 17-19, 2000, New York City, New York, United States [doi>10.1145/347642.347758]
• 18: Gopal Pandurangan , Prabhakar Raghavan , Eli Upfal, Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.330-339, August 15-17, 2002
• 19: D. M. Pennock, G. W. Flake, S. Lawrence, E. J. Glover, and C. L. Giles, "Winners Don't Take All: Characterizing the Competition for Links on the Web," Computer Science, vol. 99, no. 8, pp. 5207--5211, 2002.
• 20: Slawomir Pilarski , Tiko Kameda, Simple bounds on the convergence rate of an ergodic Markov chain, Information Processing Letters, v.45 n.2, p.81-87, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90220-4]
• 21: Peter Pirolli , Stuart K. Card , Mija M. Van Der Wege, The effects of information scent on visual search in the hyperbolic tree browser, ACM Transactions on Computer-Human Interaction (TOCHI), v.10 n.1, p.20-53, March 2003 [doi>10.1145/606658.606660]
• 22: E. Ravasz, and A. L. Barabasi, "Hierarchical Organization in Complex Networks," PHYSICAL REVIEW, vol. 67, 2003.
• 23: R. Tarjan, "Enumeration of the Elementary Circuits of a Directed Graph," SIAM J. Computing, vol. 2, no. 3, pp. 211--216, 1973.
• 24: Masashi Toyoda , Masaru Kitsuregawa, A system for visualizing and analyzing the evolution of the web with a time series of graphs, Proceedings of the sixteenth ACM conference on Hypertext and hypermedia, September 06-09, 2005, Salzburg, Austria [doi>10.1145/1083356.1083387]
• 25: Andreas S. Weigend , Erik D. Wiener , Jan O. Pedersen, Exploiting Hierarchy in Text Categorization, Information Retrieval, v.1 n.3, p.193-216, October 1999 [doi>10.1023/A:1009983522080]
• 26: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]
• 27: B. Yoon, "Finding the Number of Clusters and Various Experiments Based on ASA Clustering Method," Journal of KORMS, pp. 87--98, 2006.
• 28: Wookey Lee, S. Kang, S. Lim, M. Shin, and Y. Kim, "Adaptive Hierarchical Surrogate for Searching Web with Mobile Devices," IEEE Transactions on Consumer Electronics, Vol. 53, No. 2, pp. 796--803, 2007.
• 29: Wookey Lee, Seungkil Lim: Maximum Rooted Spanning Trees for the Web. OTM Workshops, LNCS, pp. 1873--1882, 2006.

INDEX TERMS

Keywords:
combinatorial optimization, simulated annealing, visualization, web clustering