From dirt to shovels: fully automatic tool generation from ad hoc data

ABSTRACT

An ad hoc data source is any semistructured data source for which useful data analysis and transformation tools are not readily available. Such data must be queried, transformed and displayed by systems administrators, computational biologists, financial analysts and hosts of others on a regular basis. In this paper, we demonstrate that it is possible to generate a suite of useful data processing tools, including a semi-structured query engine, several format converters, a statistical analyzer and data visualization routines directly from the ad hoc data itself, without any human intervention. The key technical contribution of the work is a multi-phase algorithm that automatically infers the structure of an ad hoc data source and produces a format specification in the PADS data description language. Programmers wishing to implement custom data analysis tools can use such descriptions to generate printing and parsing libraries for the data. Alternatively, our software infrastructure will push these descriptions through the PADS compiler, creating format-dependent modules that, when linked with format-independent algorithms for analysis and transformation, result infully functional tools. We evaluate the performance of our inference algorithm, showing it scales linearlyin the size of the training data - completing in seconds, as opposed to the hours or days it takes to write a description by hand. We also evaluate the correctness of the algorithm, demonstrating that generating accurate descriptions often requires less than 5% of theavailable data.

REFERENCES

• 1: Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
• 2: Arvind Arasu , Hector Garcia-Molina , Stanford University, 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]
• 3: Geert Jan Bex , Frank Neven , Thomas Schwentick , Karl Tuyls, Inference of concise DTDs from XML data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Geert Jan Bex , Frank Neven , Stijn Vansummeren, Inferring XML schema definitions from XML data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.175-186, May 21-24, 2001, Santa Barbara, California, United States
• 6: David Burke, Kathleen Fisher, David Walker, Peter White, and Kenny Q. Zhu. Towards 1-click tool generation with PADS. In CAGI, Corvallis, OR, June 2007.
• 7: Sudarshan Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, and Jennifer Widom. The TSIMMIS project: Integration of heterogeneous information sources. In 16th Meeting of the Information Processing Society of Japan, pages 7--18, Tokyo, Japan, 1994.
• 8: 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
• 9: François Denis , Aurélien Lemay , Alain Terlutte, Learning regular languages using RFSAs, Theoretical Computer Science, v.313 n.2, p.267-294, 17 February 2004 [doi>10.1016/j.tcs.2003.11.008]
• 10: Mary F. Fernández, Kathleen Fisher, Robert Gruber, and Yitzhak Mandelbaum. PADX: Querying large-scale ad hoc data with XQuery. In PLAN-X, January 2006.
• 11: Henning Fernau, Learning XML Grammars, Proceedings of the Second International Workshop on Machine Learning and Data Mining in Pattern Recognition, p.73-87, July 25-27, 2001
• 12: Kathleen Fisher , Robert Gruber, PADS: a domain-specific language for processing ad hoc data, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 13: Kathleen Fisher , Yitzhak Mandelbaum , David Walker, The next 700 data description languages, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, January 11-13, 2006, Charleston, South Carolina, USA
• 14: Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: a system for extracting document type descriptors from XML documents, ACM SIGMOD Record, v.29 n.2, p.165-176, June 2000
• 15: E. M. Gold. Language identification in the limit. Information and Control, 10(5):447--474, 1967.
• 16: Peter D. Grünwald. The Minimum Description Length Principle. MIT Press, May 2007.
• 17: Theodore W. Hong. Grammatical Inference for Information Extraction and Visualisation on the Web. Ph.D. Thesis, Imperial College London, 2002.
• 18: Ykä Huhtala, Juha Kärkkäinen, Pasi Porkka, and Hannu Toivonen. TANE: An efficient algorithm for discovering functional and approximate dependencies. The Computer Journal, 42(2):100--111, 1999.
• 19: Jason L. Hutchens and Michael D. Alder. Finding structure via compression. In David M. W. Powers, editor, Proceedings of the Joint Conference on New Methods in Language Processing and Computational Natural Language Learning, pages 79--82. 1998.
• 20: Nicholas Kushmerick , Daniel S. Weld, Wrapper induction for information extraction, University of Washington, 1997
• 21: Nicholas Kushmerick, Daniel S. Weld, and Robert B. Doorenbos. Wrapper induction for information extraction. In IJCAI, pages 729--737, 1997. Kristina Lerman, Lise Getoor, Steven Minton, and Craig Knoblock. Using the structure of web sites for automatic segmentation of tables. In SIGMOD, pages 119--130, New York, NY, USA, 2004.
• 22: 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]
• 23: J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.
• 24: Yitzhak Mandelbaum , Kathleen Fisher , David Walker , Mary Fernandez , Artem Gleyzer, PADS/ML: a functional data description language, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 25: Wim Martens , Frank Neven , Thomas Schwentick , Geert Jan Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems (TODS), v.31 n.3, p.770-813, September 2006 [doi>10.1145/1166074.1166076]
• 26: Ion Muslea, Steve Minton, and Craig Knoblock. Active learning with strong and weak views: a case study on wrapper induction. In IJCAI, pages 415--420, 2003.
• 27: Hwee Tou Ng , Chung Yong Lim , Jessica Li Teng Koo, Learning to recognize tables in free text, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.443-450, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034746]
• 28: J. Oncina and P. Garcia. Inferring regular languages in polynomial updated time. Machine Perception and Artificial Intelligence, 1:29--61, 1992.
• 29: PADS Project. PADS project. http://www.padsproj.org/, 2007.
• 30: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 31: Stefan Raeymaekers, Maurice Bruynooghe, and Jan Van den Bussche. Learning (k, l)-contextual tree languages for information extraction. In ECML, pages 305--316, 2005.
• 32: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 33: Kurt A. Shoens , Allen Luniewski , Peter M. Schwarz , James W. Stamos , Joachim Thomas, II, The Rufus System: Information Organization for Semi-Structured Data, Proceedings of the 19th International Conference on Very Large Data Bases, p.97-107, August 24-27, 1993
• 34: Stephen Soderland, Learning Information Extraction Rules for Semi-Structured and Free Text, Machine Learning, v.34 n.1-3, p.233-272, Feb. 1999
• 35: Andreas Stolcke , Stephen M. Omohundro, Inducing Probabilistic Grammars by Bayesian Model Merging, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.106-118, September 21-23, 1994
• 36: Enrique Vidal, Grammatical Inference: An Introduction Survey, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.1-4, September 21-23, 1994
• 37: R. M. Wharton. Approximate language identification. Information and Control, 26(3):236--255, 1974.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.m Miscellaneous

General Terms:
Algorithms, Languages

Keywords:
ad hoc data, data description languages, grammar induction, tool generation