[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[task #15713] Make quad structure to make unique hashes of 4 objects

From: Sachin Kumar Singh
Subject: [task #15713] Make quad structure to make unique hashes of 4 objects
Date: Fri, 17 Jul 2020 19:56:31 -0400 (EDT)
User-agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:76.0) Gecko/20100101 Firefox/76.0

Follow-up Comment #19, task #15713 (project gnuastro):

For the kd-tree, I have a bit dilemma on choosing the type of implementation.
In one implementation(as given in its Wikipedia) it uses median to build the
tree. But in another, it is also possible to build a tree without median(using
only the axis to determine the next child). Also, it is mentioned in its
Wikipedia page that,

Note that it is not required to select the median point. In the case where
median points are not selected, there is no guarantee that the tree will be
balanced. To avoid coding a complex O(n) median-finding algorithm or using an
O(n log n) sort such as heapsort or mergesort to sort all n points, a popular
practice is to sort a fixed number of randomly selected points and use the
median of those points to serve as the splitting plane. In practice, this
technique often results in nicely balanced trees.

Now it is desired/recommended to use a balanced tree for proper tree heights
and skewness and hence fast operations. But if I choose the one with median,
I'll have to make the array beforehand rather than inserting the hashes as
they are made, which is a better and more modular design. What do you

P.S- Both kinds of implementation are ready to be tested after this minor
problem is solved:-)


Reply to this item at:


  Message sent via Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]