[Caml-list] Set/Map with intervals and/or order-related operations

[Caml-list] Set/Map with intervals and/or order-related operations

[Yamagata Yoriyuki]

Hi, folks,

I'm looking for the Set/Map like data-structures which can efficiently
add and remove large intervals over integers, and support
intersections, unions and compliments.  Does anybody make such
libraries?  Baire contains interval.ml[i] but misses these
functionalities.  Is it easy to add them to Baire, or are Baire's
intervals something different than I thought?

Failing that, is there Set/Map with order-related operations?
Actually I have one but if there is one actively developed, I would
like to use it.

By the way, I have a library for arbitrary orders on (finite sets of)
integers.  I think comparison of two integer is O(log n ^ 2)
time. (n for the size of the finite set.)  Do you think it is worth to
make public?

Cheers,
--
Yamagata Yoriyuki

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Eray Ozkural]

Yamagata must read a computational geometry text, he shall find that 
structures like interval trees provide for such operations. But according to 
which operations you need fast you may have to design your data structure....

Structure monster just got out of a computational geometry project disaster so 
he can't really help in a substantial way (^_^)

All I can say is don't try to make it very functional.

Of course a computational geometry library would be nice :) But it's so hard 
to write decent code in that area.

Cheers,

On Sunday 25 May 2003 13:26, Yamagata Yoriyuki wrote:
> Hi, folks,
>
> I'm looking for the Set/Map like data-structures which can efficiently
> add and remove large intervals over integers, and support
> intersections, unions and compliments.  Does anybody make such
> libraries?  Baire contains interval.ml[i] but misses these
> functionalities.  Is it easy to add them to Baire, or are Baire's
> intervals something different than I thought?
>
> Failing that, is there Set/Map with order-related operations?
> Actually I have one but if there is one actively developed, I would
> like to use it.
>
> By the way, I have a library for arbitrary orders on (finite sets of)
> integers.  I think comparison of two integer is O(log n ^ 2)
> time. (n for the size of the finite set.)  Do you think it is worth to
> make public?
>
> Cheers,
> --
> Yamagata Yoriyuki
>
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives:
> http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
> http://caml.inria.fr/FAQ/ Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Diego Olivier Fernandez Pons]

    Bonjour,

> Structure monster just got out of a computational geometry project
> disaster so he can't really help in a substantial way (^_^)

Sometime ago I answered to a comment of Oleg Trott in private, since I
felt it wasn't really interesting for the other users of the caml-list
but if this experience can help...

Oleg Trott wrote :

>> Baire has not even been released after 1 year of work,
>
> I understand that you are not designing new algorithms, but coding
> up ones that are well-known. If so, what is the limiting factor in
> your work : trying to anticipate what features users might and might
> not need ?

The first point is not absolutely true : Baire contains a useless
generalization of balancing schemes, a few operations on zippers,
graph data structure based on ternary balanced trees (both inspired by
Gerard Huet's Zen library), lexical maps, there were dynamic optimal
trees (see the art of computer programming for the statical version)
based on Cartesian trees... But this is not the problem.

The main problems are :
- lack of knowledge
- lack of time
- lack of organization

And the worse is the last one.

I wanted to write a library of NP-hard approximation algorithms over
Baire's graph data structures. I soon understood I would need a
LP-solver and an efficient branch-and-bound scheme.

I then experimented on branch-and-bound (huge trees) with two
techniques : continuations (simulated by exceptions) and zippers.
Wrote some code. I also experimented a few LP algorithms mostly on
Bender's decomposition to obtain a quasi-recursive scheme and to be
able to use a persistent data structure (sparse arrays). Wrote
some code.

The LP-algorithms had numerical unstability problems. I investigated
how to face this kind of problem (interval arithmetic, stochastic
arithmetic, regressive analysis). Chose CESTAC (stochastic arithmetic)
and wrote some code.

I also investigated a few tree traversal algorithms (classical
depth-first and best-first but also limited discrepancy search,
bounded-depth discrepancy seach, interleaved-discrepancy search, ...)

Tired of being rewriting trivial data structure (trees, heaps) because
I needed an immediate acces to X where X could be { the size, the
depth on the tree, the number of left segment in the path, ... } I
said to myself "wrong way...  automatic code generation is the only
truth".

Worked on automata (pda, lpda), attribute grammars and code
generation/specialisation. Wrote some code.

Result :
- a lot of pieces of unrelated code
- no library, not even a single line of code directly related to the
initial goal
- Baire hasn't been maintained and developed as it should have

This is the classical scheme of the 'library project disaster'.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Diego Olivier Fernandez Pons]

    Bonjour,

> I'm looking for the Set/Map like data-structures which can efficiently
> add and remove large intervals over integers, and support
> intersections, unions and compliments.  Does anybody make such
> libraries?  Baire contains interval.ml[i] but misses these
> functionalities.  Is it easy to add them to Baire, or are Baire's
> intervals something different than I thought?

Baire's interval Set/Map data structure is based on Martin Erwig's
paper 'Diets for fat sets, Journal of Functional programming Vol 8,
N°6, 627-632, 1998'. It seems to be the data structure you are looking
for (that is an extension to usual sets and maps with a better support
for interval query, insertion, removal, ...)

Erwig's paper is available from his home page, there is also a version
by Olivier Andrieu.

There are interval data structures used in computational geometry
(interval tree, ...) but I don't think this is what you are refering
to, is it ?

Martin Erwig's paper presents the data structure and says that one
could easily add
- a balancing scheme
- the set operations (union, intersection, ...)

I did the first one longtime ago (should clean the data structure and
remove some bugs) but didn't have the courage to face the 23 cases of
interval respective positions needed to implement the 'difference'
operation over sets.  I also tried some generic implementation
(extending the 'partition' operation) but never ended that work.

> Failing that, is there Set/Map with order-related operations?
> Actually I have one but if there is one actively developed, I would
> like to use it.

I dont understand exactly what do you mean by 'order-related
operations'. Anyway, if you have some code, it would be interesting to
release it.

> By the way, I have a library for arbitrary orders on (finite sets of)
> integers.  I think comparison of two integer is O(log n ^ 2)
> time. (n for the size of the finite set.)  Do you think it is worth to
> make public?

Yes. It could be included to one of the 'data structure projects'
being developed in Caml.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Set/Map with intervals and/or order-related operations

[Yamagata Yoriyuki]

Thanks everyone for suggestions.  Perhaps I will develop my own since
I need balancing schema, and a Map-like structure (not only a Set-like
structure.) based on Diet.  I only need queries for individual
elements, not intervals.  So I don't think a k-d tree is appropriate.
Also I need the data structure purely functional, because the cost of
copying is not negligible.  So, even though several people points out
the existence of C implementations, I will opt an ocaml one.  The dom
type of FaCiLe is essentially a list of intervals.  Maybe I can use
Baire implementations.

Cheers,
--
Yamagata Yoriyuki


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re : [Caml-list] Set/Map with intervals and/or order-related operations

[Diego Olivier Fernandez Pons]

    Bonjour,

> Perhaps I will develop my own since I need balancing schema, and a
> Map-like structure (not only a Set-like structure.) based on Diet.
> I only need queries for individual elements, not intervals. So I
> don't think a k-d tree is appropriate. Also I need the data
> structure purely functional, because the cost of copying is not
> negligible. So, even though several people points out the existence
> of C implementations, I will opt an ocaml one. The dom type of
> FaCiLe is essentially a list of intervals. Maybe I can use Baire
> implementations.

I am afraid I haven't yet understood your problem and I will need more
explanations to be able to help you.

There are several points in your message I would like to comment :
- Tree-like data structure balancing
- Diet (discrete interval encoding scheme)

1. Balancing tree-like data structure

You should separate the design of the tree-like data structure and its
balancing.

First write down your unbalanced data structure and get your
algorithms right, only then choose one and implement one of the
multiple balancing schemes available

The trick is very simple (Stephen Adams) : encapsulate the balancing
information in << smart constructors >>.

At the beginning this constructors will be trivial

let makeTree = fun l v r -> N (l, v, r)

and your functions will look like this

let rec insert x = function
  | E -> single x
  | N (l, v, r) ->
     match compare x v with
        | n when n < 0 -> makeTree (insert x l) v r
        | n when n > 0 -> makeTree l v (insert x r)
        | _ -> failwith "already in the data structure"

Once everything goes right, you will add a balancing constructor and
replace your [makeTree] by the balancing constructor [makeBTree].

Sometimes you will find usefull not to recompute all the balancing
information at every node, then you just need to add a cache. This is
of course optional.

...
| E -> injection x
| N (l, v, r, _) -> (* the last int is a cache for the constructor *)
...

Your balanced function will look like this

let rec insert x = function
  | E -> single x
  | N (l, v, r, _) ->
     match compare x v with
        | n when n < 0 -> makeBTree (insert x l) v r
        | n when n > 0 -> makeBTree l v (insert x r)
        | _ -> failwith "already in the data structure"

Conclusion : You do not need to bother with balancing schemes from the
beginning. Once your unbalanced data structure works fine, you can add
them very easely.

Baire contains a few examples :
- unbalancedSet.ml contains unbalanced trees and AVL-trees without
cache (does not change the data type) (0)
- avlSet.ml contains avl sets with cache (1)
- weighBalancedSet.ml contains WB sets with cache (2)
...

(1) and (2) are just a copy-paste of (0) with the described
modifications and (1) and (2) share all but 40 lines of code (namely
the 4 balancing constructors).


2. Discrete interval encoding tree

The idea of diet is to replace successive integers by an interval

{3} {5} {6} {7} {9} -> {3} [5-7] {9}

Then, a Diet is just a tree of intervals and singletons with some
join/separate instructions. Since I do not understand what you mean by
'map-like operations' I don't know if this is appropriate.

{3, 4} {5, 2} {6, 2} {7, 3} {9, 4} -> {3, 4} [5-6, 2] {7, 3} {9, 4}

This will work (I mean with a significant compression rate) only if
you can ensure that consecutive bindings will have very often the same
image.

Or are you binding sigletons and intervals to values ?

{3, 4} {[5-7], 2} {[6-10], 5} {9, 4}

find 5 myDataStructure -> [(5, 2); (5, 5)]

Are the intervals supposed to be disjoint ?

{3, 4} {[5-7], 2} {[8-10], 3}

find 5 myDataStructure -> (5, 2)

Or are you binding keys to multiple values

{3, {4}} {5, {2, 5}} {6, {2, 5}} {7, {2, 5}} {8, 5} {9, {4, 5}} {10,
{5}}

find 5 myDataStructure -> [(5, 2); (5, 5)]

Multidimensional data structure (k-d trees, range trees, cartesian
trees) may be what you are looking for. It depends highly on what you
mean by "set/map with intervals" and "order related operations".

Could you give a few examples of what you expect of such a data
structure ?

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners