Scorpion: Explaining Away Outliers in Aggregate Queries
Database users commonly explore large data sets by running aggregate queries that project the data down to a smaller number of points and dimensions, and visualizing the results. Often, such visualizations will reveal outliers that correspond to errors or surprising features of the input data set. U...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89076 https://orcid.org/0000-0002-7470-3265 |
| _version_ | 1826217258082369536 |
|---|---|
| author | Wu, Eugene Madden, Samuel R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wu, Eugene Madden, Samuel R. |
| author_sort | Wu, Eugene |
| collection | MIT |
| description | Database users commonly explore large data sets by running aggregate queries that project the data down to a smaller number of points and dimensions, and visualizing the results. Often, such visualizations will reveal outliers that correspond to errors or surprising features of the input data set. Unfortunately, databases and visualization systems do not provide a way to work backwards from an outlier point to the common properties of the (possibly many) unaggregated input tuples that correspond to that outlier. We propose Scorpion, a system that takes a set of user-specified outlier points in an aggregate query result as input and finds predicates that explain the outliers in terms of properties of the input tuples that are used to compute the selected outlier results. Specifically, this explanation identifies predicates that, when applied to the input data, cause the outliers to disappear from the output. To find such predicates, we develop a notion of influence of a predicate on a given output, and design several algorithms that efficiently search for maximum influence predicates over the input data. We show that these algorithms can quickly find outliers in two real data sets (from a sensor deployment and a campaign finance data set), and run orders of magnitude faster than a naive search algorithm while providing comparable quality on a synthetic data set. |
| first_indexed | 2024-09-23T17:00:31Z |
| format | Article |
| id | mit-1721.1/89076 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:00:31Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/890762022-10-03T09:47:04Z Scorpion: Explaining Away Outliers in Aggregate Queries Wu, Eugene Madden, Samuel R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Madden, Samuel Wu, Eugene Madden, Samuel R. Database users commonly explore large data sets by running aggregate queries that project the data down to a smaller number of points and dimensions, and visualizing the results. Often, such visualizations will reveal outliers that correspond to errors or surprising features of the input data set. Unfortunately, databases and visualization systems do not provide a way to work backwards from an outlier point to the common properties of the (possibly many) unaggregated input tuples that correspond to that outlier. We propose Scorpion, a system that takes a set of user-specified outlier points in an aggregate query result as input and finds predicates that explain the outliers in terms of properties of the input tuples that are used to compute the selected outlier results. Specifically, this explanation identifies predicates that, when applied to the input data, cause the outliers to disappear from the output. To find such predicates, we develop a notion of influence of a predicate on a given output, and design several algorithms that efficiently search for maximum influence predicates over the input data. We show that these algorithms can quickly find outliers in two real data sets (from a sensor deployment and a campaign finance data set), and run orders of magnitude faster than a naive search algorithm while providing comparable quality on a synthetic data set. 2014-08-27T15:33:13Z 2014-08-27T15:33:13Z 2013-06 Article http://purl.org/eprint/type/ConferencePaper 21508097 http://hdl.handle.net/1721.1/89076 Eugene Wu and Samuel Madden. 2013. Scorpion: explaining away outliers in aggregate queries. Proc. VLDB Endow. 6, 8 (June 2013), 553-564. https://orcid.org/0000-0002-7470-3265 en_US http://dx.doi.org/10.14778/2536354.2536356 Proceedings of the VLDB Endowment Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) Wu |
| spellingShingle | Wu, Eugene Madden, Samuel R. Scorpion: Explaining Away Outliers in Aggregate Queries |
| title | Scorpion: Explaining Away Outliers in Aggregate Queries |
| title_full | Scorpion: Explaining Away Outliers in Aggregate Queries |
| title_fullStr | Scorpion: Explaining Away Outliers in Aggregate Queries |
| title_full_unstemmed | Scorpion: Explaining Away Outliers in Aggregate Queries |
| title_short | Scorpion: Explaining Away Outliers in Aggregate Queries |
| title_sort | scorpion explaining away outliers in aggregate queries |
| url | http://hdl.handle.net/1721.1/89076 https://orcid.org/0000-0002-7470-3265 |
| work_keys_str_mv | AT wueugene scorpionexplainingawayoutliersinaggregatequeries AT maddensamuelr scorpionexplainingawayoutliersinaggregatequeries |