From dirt to shovels: fully automatic tool generation from ad hoc data
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Language identification in the limit
Gold, E. M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)91165-5 · Cited by 3,572 · cited 5×
“In 1967, Gold (1967) proved that learning a grammar for any remotely sophisticated class of languages, including regular languages, is impossible if one is only given positive example data.5 Given this negative theoretical result, and the practical fact that it is hard to be sure that training…”
BackgroundInfluentialThe Minimum Description Length Principle
Grünwald, P. D. (2007) · doi:10.7551/mitpress/4643.001.0001 · Cited by 1,644 · cited 2×
“As is common in machine learning, we have defined a scoring function based on the Minimum Description Length Principle (MDL), which states that a good description is one that minimizes the cost (in bits) of transmitting the data [8].”
Method
Cited by
Detecting large-scale system problems by mining console logs
Xu, W., Huang, L., Fox, A., Patterson, D., & Jordan, M. I. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629587 · Cited by 1,332
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1926385.1926423 · Cited by 446
SherLog: error diagnosis by connecting clues from run-time logs
Yuan, D., Mai, H., Xiong, W., Tan, L., Zhou, Y., & Pasupathy, S. (2010) · Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems · doi:10.1145/1736020.1736038 · Cited by 176
FlashExtract: a framework for data extraction by examples
Le, V., & Gulwani, S. (2014) · ACM SIGPLAN Notices · doi:10.1145/2666356.2594333 · Cited by 59
Metadata
- Authors
- Fisher, K., Walker, D., Zhu, K. Q., & White, P.
- Venue
- Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- Publisher
- ACM
- Published
- 2008-01-07
- Pages
- 421-434
- OpenAlex
- W1982280055
- Cited by
- 82
- References
- 2
- FWCI
- 8.50
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.