Template detection via data mining and its applications

ABSTRACT

We formulate and propose the template detection problem, and suggest a practical solution for it based on counting frequent item sets. We show that the use of templates is pervasive on the web. We describe three principles, which characterize the assumptions made by hypertext information retrieval (IR) and data mining (DM) systems, and show that templates are a major source of violation of these principles. As a consequence, basic "pure" implementations of simple search algorithms coupled with template detection and elimination show surprising increases in precision at all levels of recall.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
	2	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]
	3	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
	4	Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
	5	V. Bush. As we may think. The Atlantic Monthly, 176(1):101--108, July 1945.
	6	Soumen Chakrabarti, Integrating the document object model with hyperlinks for enhanced topic distillation and information extraction, Proceedings of the 10th international conference on World Wide Web, p.211-220, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372054]
	7	Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
	8	Soumen Chakrabarti , Byron E. Dom , David Gibson , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Topic Distillation and Spectral Filtering, Artificial Intelligence Review, v.13 n.5-6, p.409-435, Dec. 1999 [doi>10.1023/A:1006596506229]
	9	Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
	10	Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
	11	Soumen Chakrabarti , Mukul Joshi , Vivek Tawde, Enhanced topic distillation using text, markup tags, and hyperlinks, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383990]
	12	Soumen Chakrabarti , Martin van den Berg , Byron Dom, Distributed Hypertext Resource Discovery Through Examples, Proceedings of the 25th International Conference on Very Large Data Bases, p.375-386, September 07-10, 1999
	13	Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceeding of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
	14	B. D. Davison. Recognizing nepotistic links on the web. In Proceedings of the AAAI-2000 Workshop on Artificial Intelligence for Web Search, pages 23--28, 2000.
	15	Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
	16	E. Garfield. "Citation Analysis as a Tool in Journal Evaluation". Science, 178:471--479, 1972.
	17	Google. http://www.google.com.
	18	M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14:10--25, 1963.
	19	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]
	20	Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceeding of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
	21	R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.387-401, June 2000
	22	Yoëlle S. Maarek , Daniel M. Berry , Gail E. Kaiser, An Information Retrieval Approach for Automatically Constructing Software Libraries, IEEE Transactions on Software Engineering, v.17 n.8, p.800-813, August 1991 [doi>10.1109/32.83915]
	23	L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Computer Science Department, Stanford University, 1998.
	24	G. Pinski and F. Narin. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Inf. Proc. and Management, 12, 1976.
	25	Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
	26	H. Small. Co-citation in the scientific literature: A new measure of the relationship between two documents. Journal of the American Society for Information Science, 24:265--269, 1973.