  Estimating the dependency of variables is a fundamental task in data
analysis. Identifying the relevant attributes in databases leads to better data
understanding and also improves the performance of learning algorithms, both in
terms of runtime and quality. In data streams, dependency monitoring provides
key insights into the underlying process, but is challenging. In this paper, we
propose Monte Carlo Dependency Estimation (MCDE), a theoretical framework to
estimate multivariate dependency in static and dynamic data. MCDE quantifies
dependency as the average discrepancy between marginal and conditional
distributions via Monte Carlo simulations. Based on this framework, we present
Mann-Whitney P (MWP), a novel dependency estimator. We show that MWP satisfies
a number of desirable properties and can accommodate any kind of numerical
data. We demonstrate the superiority of our estimator by comparing it to the
state-of-the-art multivariate dependency measures.
