Skip to content

Add KD Trees  #32

@czgdp1807

Description

@czgdp1807
Member

Description of the problem

K dimensional trees is a quite important data structure for storing high dimensional data. This issue aims at adding the same.
The task is planned to be completed in two phases, first we will add static k-d trees and in the second phase we will add, dynamic k-d trees.

API Design and Class Hierarchy Overview

Static k-d trees - These trees will be built on a given data and once built, it will not be possible to modify it.
The class name for such trees is, StaticKDTree. It will support the following operations:

  1. __new__ - Meant for building the tree.
  2. nearest_neighbour
  3. find_min
  4. find_max
  5. search

Dynamic k-d trees - These trees will be built on a given data and it will be possible to modify the tree.
The class name for such trees is, DynamicKDTree. In addition to the operations supported by static k-d trees, the following operations will be supported,

  1. insert
  2. delete
  3. balance

Example of the problem

References/Other comments

[1] https://en.wikipedia.org/wiki/K-d_tree
[2] https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf

Activity

self-assigned this
on Oct 30, 2019
removed their assignment
on Feb 17, 2020
nikipr1999

nikipr1999 commented on Mar 11, 2020

@nikipr1999

Please assign this issue to me for rgsoc20

czgdp1807

czgdp1807 commented on Mar 14, 2020

@czgdp1807
MemberAuthor

@nikipr1999 Though for RGSoC, 2020 making contributions isn't necessary till 31st March as the official coding period starts from July. Till then submit your application on RGSoC website.
You can discuss the API design of KD Trees if you have some improvements to suggest over the one given in the description of this issue. I have also created a PR which you continue if you want to. See, #48

kichloo

kichloo commented on Mar 21, 2020

@kichloo

@czgdp1807 Can you pl restore the gssoc label as there are 10 more days now for RGSOC but it can be contributed by GSSOC. Pl assign me this! I will complete asap.

czgdp1807

czgdp1807 commented on Mar 21, 2020

@czgdp1807
MemberAuthor

Hi @kichloo You can start working on this issue. You can continue, #48
Please see our issue policy for getting to know how to work on issues.

subhangi2731

subhangi2731 commented on Mar 9, 2021

@subhangi2731

can you please assign it to me?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @kichloo@czgdp1807@nikipr1999@subhangi2731

        Issue actions

          Add KD Trees · Issue #32 · codezonediitj/pydatastructs