Algorithms Seminar/Fall10
From ResearchWiki
(Difference between revisions)
(→Synopsis) |
(→Schedule) |
||
| Line 40: | Line 40: | ||
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Databases''' | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Databases''' | ||
|- | |- | ||
| - | | Sep 29 || Sketching and Streaming || [http://dimacs.rutgers.edu/~graham/pubs/papers/probstreams.pdf Sketching probabilistic data streams] || | + | | Sep 29 || Sketching and Streaming || How to maintain a concise summary of uncertain data on-the-fly. [http://dimacs.rutgers.edu/~graham/pubs/papers/probstreams.pdf Sketching probabilistic data streams] || |
|- | |- | ||
| - | | Oct 6 || Histograms || [http://dimacs.rutgers.edu/~graham/pubs/html/CormodeGarofalakis09.html Histograms and wavelets on probabilistic data] [http://www.cs.umass.edu/~mcgregor/papers/09-vldb.pdf Probabilistic Histograms for Probabilistic Data] || | + | | Oct 6 || Histograms || Building Histograms and other representations of uncertain probability distributions. [http://dimacs.rutgers.edu/~graham/pubs/html/CormodeGarofalakis09.html Histograms and wavelets on probabilistic data] [http://www.cs.umass.edu/~mcgregor/papers/09-vldb.pdf Probabilistic Histograms for Probabilistic Data] || |
|- | |- | ||
| - | | Oct 20 || Ranking || [http://arxiv.org/abs/0904.1366 A Unified Approach to Ranking in Probabilistic Databases] with [http://www.cs.umd.edu/~lijian/paper/vldb09_long.pdf slides] and [http://dimacs.rutgers.edu/~graham/pubs/papers/exprank.pdf Semantics of ranking queries for probabilistic data and expected ranks] || | + | | Oct 20 || Ranking || Retrieving the top (most important) data points, when all values are uncertain. [http://arxiv.org/abs/0904.1366 A Unified Approach to Ranking in Probabilistic Databases] with [http://www.cs.umd.edu/~lijian/paper/vldb09_long.pdf slides] and [http://dimacs.rutgers.edu/~graham/pubs/papers/exprank.pdf Semantics of ranking queries for probabilistic data and expected ranks] || |
|- | |- | ||
| - | | Oct 27 || Clustering ||[http://dimacs.rutgers.edu/~graham/pubs/papers/pclust.pdf Approximation Algorithms for Clustering Uncertain Data] || | + | | Oct 27 || Clustering || Constructing clusters of uncertain data sets. [http://dimacs.rutgers.edu/~graham/pubs/papers/pclust.pdf Approximation Algorithms for Clustering Uncertain Data] || |
|- | |- | ||
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Visualization''' | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Visualization''' | ||
Revision as of 04:57, 5 August 2010
Modelling Data With Uncertainty
Wed 1:25-2:45pm
MEB 3147 (LCR)
Contents |
Synopsis
We will cover many recent developments in the modeling and processing of uncertain data in computer science. The seminar will focus and the modeling, algorithmic, and data-structural foundations needed for understanding, processing, and visualizing uncertain data. First we will overview different models of uncertainty, tracing their origins and motivation (Many-world models in databases, imprecision models in geometry, probabilistic models in databases). Then we will proceed to survey recent developments in computational geometry, databases, visualization, and machine learning and statistics.
- The computational geometry section will describe basic algorithmic tools and analysis several models of uncertain data.
- The databases section will focus on data structures to manage and process large amounts of uncertain data concisely.
- The visualization section will look at models for data uncertainty for surfaces and volumes, and how the resulting data is visualized.
- The machine learning and statistics section will cover classic techniques for learning and detecting uncertainty.
Through this seminar, participants will gain an understanding of the state-of-the-art in modeling and processing uncertain data and will be exposed to several important open problems and exciting research directions.
Participants
- Jeff Phillips
- Suresh Venkatasubramanian
Schedule
(subject to change)
| Date | Topic | Outline and Paper(s) | Presenter |
|---|---|---|---|
| Aug 25 | Models of Data Uncertainty | Motivation behind modeling Uncertainty. Survey different models and where they arise. | Jeff Phillips |
| Geometry | |||
| Sep 1 | Range Spaces and epsilon-Samples | How well does random sampling work? Define important geometric-combinatorial notions: Range spaces, eps-nets, eps-samples. Prove random sampling bound for eps-samples (Sariel's Notes). Show cool application of eps-nets on uncertain data in sensor nets(eps-Sentinals) | |
| Sep 8 | Epsilon-Quantizations and Epsilon-SIPs | Modeling questions on uncertain data with probability distributions. Review specific applications to smallest enclosing ball. (Shape Fitting on Point Sets with Probability Distributions) | |
| Sep 15 | Geometry on Imprecise Points | Imprecision in data. eps-geometry for rounding errors (eps-Geometry). More general geometry problems: Basic Geometry Measures on Imprecise Points and maybe Largest and Smallest Convex Hulls on Imprecise Points | |
| Sep 22 | Hardness of Uncertainty Problems | Its not always easy! What is #P-Hard. Basic problems that are(Efficient Query Evaluation on Probabilistic Databases). LP-type problems. Non-LP-type problems that are #P-Hard([see Jeff for preprint]) | |
| Databases | |||
| Sep 29 | Sketching and Streaming | How to maintain a concise summary of uncertain data on-the-fly. Sketching probabilistic data streams | |
| Oct 6 | Histograms | Building Histograms and other representations of uncertain probability distributions. Histograms and wavelets on probabilistic data Probabilistic Histograms for Probabilistic Data | |
| Oct 20 | Ranking | Retrieving the top (most important) data points, when all values are uncertain. A Unified Approach to Ranking in Probabilistic Databases with slides and Semantics of ranking queries for probabilistic data and expected ranks | |
| Oct 27 | Clustering | Constructing clusters of uncertain data sets. Approximation Algorithms for Clustering Uncertain Data | |
| Visualization | |||
| Nov 3 | Noisy Surfaces | How to sample from uncertain objects (surfaces) and retain structure. Visualizing resulting samples. | |
| Nov 10 | Transfer Functions | Maintaining and visualizing more complicated domains under uncertainty. | |
| Machine Learning And Statistics | |||
| Nov 17 | Support Vector Machines | Classifying uncertain data. Support Vector Classification with Input Data Uncertainty | |
| Nov 24 | Markov Random Fields | Harnessing Locality. | |
| Dec 1 | Particle Filters | Maintaining uncertain estimates. | |
| Dec 8 | Multi-Armed Bandits | Trading off investigation of uncertainty and rewards. | |
