Extracting data records from the web using tag path clustering

ABSTRACT

Fully automatic methods that extract lists of objects from the Web have been studied extensively. Record extraction, the first step of this object extraction process, identifies a set of Web page segments, each of which represents an individual object (e.g., a product). State-of-the-art methods suffice for simple search, but they often fail to handle more complicated or noisy Web page structures due to a key limitation -- their greedy manner of identifying a list of records through pairwise comparison (i.e., similarity match) of consecutive segments. This paper introduces a new method for record extraction that captures a list of objects in a more robust way based on a holistic analysis of a Web page. The method focuses on how a distinct tag path appears repeatedly in the DOM tree of the Web document. Instead of comparing a pair of individual segments, it compares a pair of tag path occurrence patterns (called visual signals) to estimate how likely these two tag paths represent the same list of objects. The paper introduces a similarity measure that captures how closely the visual signals appear and interleave. Clustering of tag paths is then performed based on this similarity measure, and sets of tag paths that form the structure of data records are extracted. Experiments show that this method achieves higher accuracy than previous methods.

REFERENCES

• 1: Arvind Arasu , Hector Garcia-Molina, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 2: A Fully Automated Object Extraction System for the World Wide Web, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.361, April 16-19, 2001
• 3: M. J. Cafarella, A. Halevy, D. Z. Wang, E. Wu, and Y. Zhang. WebTables: Exploring the power of tables on the Web. In Proceedings of the 34th International Conference on Very Large Data Bases, pages 538--549, 2008.
• 4: Chia-Hui Chang , Shao-Chen Lui, IEPAD: information extraction based on pattern discovery, Proceedings of the 10th international conference on World Wide Web, p.681-688, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372182]
• 5: Kevin Chen-Chuan Chang , Bin He , Chengkai Li , Mitesh Patel , Zhen Zhang, Structured databases on the web: observations and implications, ACM SIGMOD Record, v.33 n.3, September 2004 [doi>10.1145/1031570.1031584]
• 6: Cobra: Java HTML Renderer and Parser, http://lobobrowser.org/cobra.jsp.
• 7: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 8: DBLP Computer Science Bibliography, http://www.informatik.uni-trier.de/~ley/db/.
• 9: Alberto H. F. Laender , Berthier A. Ribeiro-Neto , Altigran S. da Silva , Juliana S. Teixeira, A brief survey of web data extraction tools, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565137]
• 10: 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]
• 11: Bing Liu , Robert Grossman , Yanhong Zhai, Mining data records in Web pages, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956826]
• 12: B. Liu and Y. Zhai. NET: System for extracting Web data from flat and nested data records. In Proceedings of the Conference on Web Information Systems Engineering, pages 487--495, 2005.
• 13: A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Proceedings of the Neural Information Processing Systems Conference, pages 849--856, 2001.
• 14: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 15: Kai Simon , Georg Lausen, ViPER: augmenting automatic information extraction with visual perceptions, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099672]
• 16: Junichi Tatemura , Songting Chen , Fenglin Liao , Oliver Po , K. Selcuk Candan , Divyakant Agrawal, UQBE: uncertain query by example for web service mashup, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376754]
• 17: Jiying Wang , Fred H. Lochovsky, Data extraction and label assignment for web databases, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775179]
• 18: Yasuhiro Yamada , Nick Craswell , Tetsuya Nakatoh , Sachio Hirokawa, Testbed for information extraction from deep web, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013468]
• 19: Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060761]
• 20: Hongkun Zhao , Weiyi Meng , Zonghuan Wu , Vijay Raghavan , Clement Yu, Fully automatic wrapper generation for search engines, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060760]
• 21: Hongkun Zhao , Weiyi Meng , Clement Yu, Mining templates from search result records of search engines, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281286]
• 22: Jun Zhu , Zaiqing Nie , Ji-Rong Wen , Bo Zhang , Wei-Ying Ma, Simultaneous record detection and attribute labeling in web data extraction, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150457]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering, data record extraction, information extraction