Re: [Caml-list] efficient binary relations?

[Christian Lindig <lindig@cs.uni-sb.de>]

On Mar 31, 2006, at 2:50 PM, Sebastian Egner wrote:

> Please could you clarify the circumstances a little bit?
>
> 1. Are you looking for a data structure that you set
> up for a fixed R once and then query many times for
> different X? Or are you looking for a dynamic data
> structure in which you keep changing R? Or are you
> looking for a 'functional data structure' where the
> older versions of R are preserved? Or for a functional
> data structure where R is fixed, but the queries X
> are constructed incrementally?
>
> 2. Is R sparse, i.e. is |R| << |\X|*|\Y|?

First, thanks for a detailed suggestion! R is sparse, constructed once, 
and queried often. As I mentioned, this is in the context of concept 
analysis. The ' operation computes the maximal blocks (or concepts) in 
a cross table; typically their number grows cubic with the size |R| of 
the relation - hence the importance of the ' operation. (In the worst 
case, when the matrix is densely populated, there may be exponentially 
many blocks.)

I generally prefer applicative data structures (without side effects) 
but understand that this is not always possible.

-- Christian