From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id B580382355 for ; Wed, 7 Feb 2018 03:00:43 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=berenger@bioreg.kyushu-u.ac.jp; spf=None smtp.mailfrom=berenger@bioreg.kyushu-u.ac.jp; spf=None smtp.helo=postmaster@h4.hosting4.cc.kyushu-u.ac.jp Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of berenger@bioreg.kyushu-u.ac.jp) identity=pra; client-ip=133.5.13.5; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="berenger@bioreg.kyushu-u.ac.jp"; x-sender="berenger@bioreg.kyushu-u.ac.jp"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of berenger@bioreg.kyushu-u.ac.jp) identity=mailfrom; client-ip=133.5.13.5; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="berenger@bioreg.kyushu-u.ac.jp"; x-sender="berenger@bioreg.kyushu-u.ac.jp"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@h4.hosting4.cc.kyushu-u.ac.jp) identity=helo; client-ip=133.5.13.5; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="berenger@bioreg.kyushu-u.ac.jp"; x-sender="postmaster@h4.hosting4.cc.kyushu-u.ac.jp"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3ARI6D/xZ9oH1EkZBKAmeUX3j/LSx+4OfEezUN459i?= =?us-ascii?q?sYplN5qZr8u8bnLW6fgltlLVR4KTs6sC17KP9fi4EUU7or+5+EgYd5JNUxJXwe?= =?us-ascii?q?43pCcHRPC/NEvgMfTxZDY7FskRHHVs/nW8LFQHUJ2mPw6arXK99yMdFQviPgRp?= =?us-ascii?q?OOv1BpTSj8Oq3Oyu5pHfeQpFiCagbb9oMBm6sRjau9ULj4dlNqs/0AbCrGFSe+?= =?us-ascii?q?RRy2NoJFaTkAj568yt4pNt8Dletuw4+cJYXqr0Y6o3TbpDDDQ7KG81/9HktQPC?= =?us-ascii?q?TQSU+HQRVHgdnwdSDAjE6BH6WYrxsjf/u+Fg1iSWIdH6QLYpUjul86pmRh3lhS?= =?us-ascii?q?keOzIl/2zcl8h8gaJHrB6koRF03ozab5yPNPdmY63TY90aS2pCUMhfWSNODYGz?= =?us-ascii?q?YJcAAecaIeZVrZPwq0cSoRawBwShAv7kxD9Shn/x2K03y+QvERvc0wwmA90Ot3?= =?us-ascii?q?XUrM7oP6oPXu670KbGwy3CYf1ZxTn29Y/FfQs/rvGWQ71wd8XRxlc1Fw7elVqQ?= =?us-ascii?q?qIvlPymL2eQCqWSb7OphVf+0i24ntgF9uyWvyt02hYbVnI4VyEjE+Dx/zY0oK9?= =?us-ascii?q?O4T0t7bsSlEJtWryyaOIp2Qt8iQ2F1oyk20KEJuZm+fCQSyZQo2QDQZOKdf4iP?= =?us-ascii?q?+BLjW+CcKip7inJ9YL+zmhi//Ea6xuD8TMW4zVhHojBFn9XUq3wA2RLe5tKHR/?= =?us-ascii?q?dn4EutxDWC2xrO5uxLIk05k7fQJYQ7zb4qjJUTtFzOHi/ol0Xyi6+bbkUk9+ey?= =?us-ascii?q?5+TnZbXmvYOcN45yigHxPakigNCwDvgiPggNX2mb5P+81L3+/UHgXbVGlOc5nb?= =?us-ascii?q?XDvJDYPcQXvq+5AwlL3YY/8xuzEjmr3doCkXQHNl5JZRyKg5LpNl3WJfD3F/a/?= =?us-ascii?q?g1CikDdxwPDGO6XsDY7TIXjZjrjhe7l95FBGyAco1t9f5pVUCqsfL/L8QEPxt9?= =?us-ascii?q?zZDgIiMwy03ubrEch92pkEVm2TGKOZMrvSvUeS5u0zO+mMeJMVuDHlJvc5/fHu?= =?us-ascii?q?iHs5lUYZfamoxpsXdGu1Hu9mIkWceXrjmM0NEWYMvgokTezlkkeOUTBJZyX6Y6?= =?us-ascii?q?Vp7Tg+DMeiDJzfboGrmr2ImimhTbNMYWUTJEqFF3zvdp7Mcdo2RQS9D/UpxjYJ?= =?us-ascii?q?T7WnRII7/RuvsxX3xPxkP/fP+jBdqNTq3553/7uAxlkJ6TVoApHFgCm2RGZukz?= =?us-ascii?q?ZVH2ZnjpA6mlR0zxK46YY9hvVZEdJJ4PYTCVUwNJnGwuM8CMHvQQLcO8rPQV3g?= =?us-ascii?q?QM30WWhtHOJ0+McHZgNGI/vnlgrKhXH4Cb4SjbGEQp8l77ncwj3sYc92jXTehv?= =?us-ascii?q?F40gsWB/BXPGjjvZZRsgjeA4mSyheZy+Cqcr8A3SjCqCGIxiyNrVxDUBM1TOPM?= =?us-ascii?q?VjYdfhmOoA=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CFAgBJXXpamAUNBYVcGgEBAQEBAgEBA?= =?us-ascii?q?QEIAQEBAYQ3A20og2WLGI8Yl3CCFwEJI4UYAoJ1BgU3EQEBAQEBAQEBAQEBEgE?= =?us-ascii?q?BAQEBBg0LBigvgjgMDIJUBiNmJQImAgIfOBMIAQGKMBGzSYInhQCCcxxpggoBA?= =?us-ascii?q?QgCASWBD4NbhX0MhigCgj2CS4JlBYg5B4IwiG+QTx6HfI1agwQBgR6IFYgCAo1?= =?us-ascii?q?xig+BPDkGgWmBBYMDCYJcgiFpjgcBAQE?= X-IPAS-Result: =?us-ascii?q?A0CFAgBJXXpamAUNBYVcGgEBAQEBAgEBAQEIAQEBAYQ3A20?= =?us-ascii?q?og2WLGI8Yl3CCFwEJI4UYAoJ1BgU3EQEBAQEBAQEBAQEBEgEBAQEBBg0LBigvg?= =?us-ascii?q?jgMDIJUBiNmJQImAgIfOBMIAQGKMBGzSYInhQCCcxxpggoBAQgCASWBD4NbhX0?= =?us-ascii?q?MhigCgj2CS4JlBYg5B4IwiG+QTx6HfI1agwQBgR6IFYgCAo1xig+BPDkGgWmBB?= =?us-ascii?q?YMDCYJcgiFpjgcBAQE?= X-IronPort-AV: E=Sophos;i="5.46,471,1511823600"; d="scan'208";a="253868558" Received: from hosting4.cc.kyushu-u.ac.jp (HELO h4.hosting4.cc.kyushu-u.ac.jp) ([133.5.13.5]) by mail3-smtp-sop.national.inria.fr with ESMTP; 07 Feb 2018 03:00:38 +0100 Received: from [192.168.2.36] (unknown [133.5.218.148]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: berenger@bioreg.kyushu-u.ac.jp) by h4.hosting4.cc.kyushu-u.ac.jp (hde-lc-postfix) with ESMTPSA id 7F5522B6DAC for ; Wed, 7 Feb 2018 11:00:34 +0900 (JST) (envelope-from berenger@bioreg.kyushu-u.ac.jp) To: caml-list@inria.fr References: <20180123145453.GA1916@Magus.localnet> <20180123231432.GA20089@topoi.pooq.com> From: Francois BERENGER Message-ID: <51b207da-d84e-dec9-7953-7d776361d756@bioreg.kyushu-u.ac.jp> Date: Wed, 7 Feb 2018 11:00:34 +0900 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: [Caml-list] [ANN] first release of bst: a bisector tree implementation Hello, A bisector tree allows to do fast but exact nearest neighbor searches in any space provided that you have a metric (function) to measure the distance between any two points in that space. It also allows proximity queries, as in "all points within distance d from my query point". Cf. this article for details: "A Data Structure and an Algorithm for the Nearest Point Problem"; Iraj Kalaranti and Gerard McDonald. ieeexplore.ieee.org/iel5/32/35936/01703102.pdf The code is here: https://github.com/UnixJunkie/bisec-tree It might interest users of vantage point trees (minivpt, and vpt in opam), kd-trees and such. I think bst should be faster than vpt in most use cases. It should appear in opam shortly. Regards, Francois.