is invariant under swaps as defined in Gionis et al (2007). For positive realvalued databases, the δ**-swap operations reduce to the Addition Mask method**
in Ojala et al (2008).

## 5 Using The Maxent Model: Randomizing Databases, And Subjective Interestingness Of Tiles

In this Section we will describe how the MaxEnt model from Sec. 3 allows one to take prior information effectively into account in the data mining process, for concreteness focusing on binary databases. First we show how it can be used to randomize databases highly efficiently, such that it is a fast alternative to swap randomizations. Subsequently, we define a new interestingness measure for tiles in binary databases when contrasted with prior information **on the row** and column sum, based one of the ideas presented in Sec. 2.2.

## 5.1 Randomizing Binary Databases

The (δ-)swap operations discussed in the previous Section, being simple invariants of the MaxEnt distribution, can be used for randomizing any of **the types of**
databases discussed in this paper. This being said, it should be reiterated that the availability of the MaxEnt distribution should make randomizing the **data**
using δ**-swaps unnecessary. Should it be needed to generate randomizations of a**
given database, one can instead sample directly from the MaxEnt distribution, thus avoiding the computational cost and potential convergence **problems faced** in randomizing the data. The thus randomized databases can be used exactly as proposed in Gionis et al (2007) for the assessment of data mining **results.**
A randomized binary database can be sampled directly from the MaxEnt model by looping through all database entries and sampling a Bernoulli random variable with success probability Pij (D(i, j**) = 1). The complexity of this**
approach is O(mn**)—prohibitive for large sparse databases.**
Fortunately, a faster approach exists, based on the observation that the number of experiments between two successes in a series of Bernoulli experiments is geometrically distributed. We can sample a sparse representation of a large number of Bernoulli random variables by sampling these so-called interarrival-times from the geometric distribution. In this way, the time required is proportional to the number of successes in the set of Bernoulli experiments, rather than to the total number of Bernoulli experiments.

This approach can only be used if all Bernoulli random variables have the same success probability, which is not true for the success probabilities Pij (D(i, j) =
1) of the entries under the MaxEnt model. However, two database **entries will** have a different success probability only if either their column sums or **their** row sums (and thus the associated Lagrange multipliers) are different. From Lemma 2, it is immediate that the number different combinations of row and column sums is me ne ≤ (
√2s)
2 = 2s**, i.e. at most proportional to the number of**
non-zeros in the original matrix.