From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA23550; Tue, 27 Aug 2002 14:13:14 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA23179 for ; Tue, 27 Aug 2002 14:13:13 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g7RCDCn00083 for ; Tue, 27 Aug 2002 14:13:12 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g7RCDCjR034476 ; Tue, 27 Aug 2002 14:13:12 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id OAA16160 ; Tue, 27 Aug 2002 14:11:31 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with SMTP id OAA124332 ; Tue, 27 Aug 2002 14:09:42 +0200 Date: Tue, 27 Aug 2002 14:09:42 +0200 (DST) From: Diego Olivier Fernandez Pons To: Markus Mottl cc: caml-list@inria.fr Subject: Re: [Caml-list] intersecting huge integer sets In-Reply-To: <20020827115215.GB32176@fichte.ai.univie.ac.at> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Markus Mottle a =E9crit : > Yes, you'll probably want Patricia trees. You can get them from > Jean-Christophe Filliatre's page: >=20 > http://www.lri.fr/~filliatr/software.en.html >=20 > They support very fast set operations (union, difference, intersection). Patricia Trees are tries in dimension 2. In fact, one could try tries in dimension 30 with the leafs being integers (a kind of mix between bitvectors and tries). I have been doing a few test, a very simple implementation should be avaible in the pre-release of the data structure library. But I don't know yet if it is faster than Patricia trees or not. At least it should save some space 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