From dev-return-37435-archive-asf-public=cust-asf.ponee.io@ignite.apache.org Sat Aug 4 07:19:28 2018 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx-eu-01.ponee.io (Postfix) with SMTP id 2A9D6180626 for ; Sat, 4 Aug 2018 07:19:27 +0200 (CEST) Received: (qmail 97878 invoked by uid 500); 4 Aug 2018 05:19:27 -0000 Mailing-List: contact dev-help@ignite.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@ignite.apache.org Delivered-To: mailing list dev@ignite.apache.org Received: (qmail 97867 invoked by uid 99); 4 Aug 2018 05:19:27 -0000 Received: from mail-relay.apache.org (HELO mailrelay1-lw-us.apache.org) (207.244.88.152) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 04 Aug 2018 05:19:27 +0000 Received: from mail-qk0-f173.google.com (mail-qk0-f173.google.com [209.85.220.173]) by mailrelay1-lw-us.apache.org (ASF Mail Server at mailrelay1-lw-us.apache.org) with ESMTPSA id 3D679208E for ; Sat, 4 Aug 2018 05:19:26 +0000 (UTC) Received: by mail-qk0-f173.google.com with SMTP id b5-v6so5516047qkg.6 for ; Fri, 03 Aug 2018 22:19:26 -0700 (PDT) X-Gm-Message-State: AOUpUlEgAsXJJ7/vAzQNLzniVwct/rOF/08P8uaX7c3P6F52SX3oS9yW jZsxom+csY4hZcG5ybjXz9kGkVOnMTCuA1l1TYegUA== X-Google-Smtp-Source: AAOMgpetkLU+06hPXfdwD/a0fTWpOv/CNQG9DtMb9jtmeiYLfb9QNhquB/+MhaVu9hTIXZIIxgKOc1dMaxWYPtIqhxY= X-Received: by 2002:a37:c91b:: with SMTP id q27-v6mr6376473qki.397.1533359965695; Fri, 03 Aug 2018 22:19:25 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Denis Magda Date: Fri, 3 Aug 2018 22:18:59 -0700 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [Distributed SQL] Do we have a plan to implement QuadTree index? To: dev Content-Type: multipart/alternative; boundary="0000000000001189c105729530ad" --0000000000001189c105729530ad Content-Type: text/plain; charset="UTF-8" Alexey, are you working on some new ML/DL APIs/algorithms? Please elaborate what you'd like to add to Ignite. -- Denis On Wed, Aug 1, 2018 at 3:10 PM Pavel Kovalenko wrote: > Hello Alexey, > > It's not so difficult to implement new type of indexing of data, but if you > want to reach performance in distributed environment you need to have > strong knowledge of a data you're indexing and what kind of queries you > want to execute. > Should be this index in-memory only or you want to persist it? > In case of persistence your index should fit our page memory model > requirements. > In both cases your index should be ready to work in concurrent environment. > > In general index can be implemented in two ways per-partition and per-node. > Per-partition may be efficient if you have a lot of points (x,y) > representing a big one, e.g. image. In this case it's required that all of > these points will be in one partition that query e.g. makes images > intersection will execute in one node. But if you have multiple images, > your index will contain also another points from other object and will > overload it. > Per-node may be efficient if you have a lot of points (x,y) that are > independent of each other, that you will use it as spatial e.g.. But in > this case, I think K-d tree is preferable as it can be used in more wide > way. > > Could you please share use cases you're trying to solve with QuadTree? With > close to real data and examples of queries? Because now the question is too > abstract and it's hard to understand how it should be implemented to reach > good results. > > > 2018-08-01 16:45 GMT+03:00 Alexey Zinoviev : > > > Hi, Igniters. > > > > Currently I'm working on different math stuff over the Apache Ignite and > in > > a few tasks I need to implement in memory something like this > > > > https://en.wikipedia.org/wiki/Quadtree > > > > I didn't find such index in Apache Ignite, but maybe it's under > development > > by somebody? > > > > Is it a difficult to add a new index type to our distributed SQL (from > > point of view of different infrastructure issues and so on P.S I don't > > worry the math stuff here because I've implemented it many times in > > non-distributed version)? > > > > It will be great to hear any kind of your thoughts and maybe somebody > could > > help with implementation > > > > zaleslaw > > > --0000000000001189c105729530ad--