efficient binary relations?

Christian Lindig
 skaller

Sebastian Egner
 Christian Lindig
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060331 (13:42) 
From:  Christian Lindig <lindig@c...> 
Subject:  Re: [Camllist] 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