English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
efficient binary relations?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-03-31 (13:42)
From: Christian Lindig <lindig@c...>
Subject: Re: [Caml-list] efficient binary relations?

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