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

Kathleen Fisher, David Walker, Kenny Q. Zhu, Peter White

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPOPL'08 - Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
Pages421-434
Number of pages14
DOIs
StatePublished - Dec 1 2008
Event35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'08 - San Francisco, CA, United States
Duration: Jan 7 2008Jan 12 2008

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

Other

Other35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'08
CountryUnited States
CitySan Francisco, CA
Period1/7/081/12/08

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • ad hoc data
  • data description languages
  • grammar induction
  • tool generation

Fingerprint Dive into the research topics of 'From dirt to shovels: Fully automatic tool generation from ad hoc data'. Together they form a unique fingerprint.

  • Cite this

    Fisher, K., Walker, D., Zhu, K. Q., & White, P. (2008). From dirt to shovels: Fully automatic tool generation from ad hoc data. In POPL'08 - Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (pp. 421-434). (Conference Record of the Annual ACM Symposium on Principles of Programming Languages). https://doi.org/10.1145/1328438.1328488