# Descriptor-based sample navigation via dimensional reduction(ish) (proof-of-concept)

**URL:** <https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298>\
**Category:** Usage Questions\
**Created:** [July 24, 2019, 4:03pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298 "2019-07-24T16:03:16Z")\
**Posts on this page:** 12\
**Page:** 2

<div class="post-metadata">

**Author:** ![weefuzzy](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/weefuzzy/32/362_2.png) [@weefuzzy](https://discourse.flucoma.org/u/weefuzzy)\
**Post date:** [July 28, 2019, 2:23pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/21 "2019-07-28T14:23:50Z")

</div>

True!

⚠ Cavets:

- @groma knows better than me
- Per [https://en.wikipedia.org/wiki/K-d\_tree#High-dimensional\_data](https://en.wikipedia.org/wiki/K-d_tree#High-dimensional_data) how well a KDTree performs for a given dimensionality depends on how much stuff is in there. According to that wikipedia page you need many more data points than 2 to the power of your dimensions for it to do better than a brute force search.  
I’m not sure what ‘many more’ might really mean though, but _at least_ an order of magnitude I’d guess. So for 10 dimensions, at least ~10k entries? For 6 dimensions \> 640 points. Etc.
- I don’t know how well SC’s `KDTree` really scales up. I think development may have stopped before all the bits were done. Certainly, I started to make it wheeze trying even 3D radius searches at one point.
- Beyond a certain point, Approximate Nearest Neighbours can be Good Enough ™ at potentially much lower cost, but that’s not yet available for any creative coding platform, AFAIK.

---

<div class="post-metadata">

**Author:** ![spluta](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/spluta/32/21_2.png) [@spluta](https://discourse.flucoma.org/u/spluta)\
**Post date:** [July 28, 2019, 2:40pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/22 "2019-07-28T14:40:03Z")

</div>

Thanks. I was getting really nice and quick results using the NearestN UGen, which uses an altered KDTree data structure. Maybe that is the best route. (which looks like it might be an ANN implementation?)

---

<div class="post-metadata">

**Author:** ![weefuzzy](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/weefuzzy/32/362_2.png) [@weefuzzy](https://discourse.flucoma.org/u/weefuzzy)\
**Post date:** [July 28, 2019, 3:13pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/23 "2019-07-28T15:13:27Z")

</div>

Man, I didn’t even know it was there, such is my SC n00bness.

Looking at the source, I think any extra speed is because its compiled C running on the server; it uses structures generated by KDTree AFAICS, so will still be exact nearest neighbours, but it saves time by only ever retrieving up to the three nearest things. As I understand it (which is very little), Approximate NN works by generating a special hash for each entry that encodes similarity somehow \<waves hands, hopes for no follow up questions\>. ([https://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf](https://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf))

Anyway, NearestN is doing what you need, then This Is Good. (And gives a useful precedent for us to look at how matching could work server-side for the next toolbox)

---

<div class="post-metadata">

**Author:** ![groma](https://discourse.flucoma.org/letter_avatar_proxy/v4/letter/g/a4c791/32.png) [@groma](https://discourse.flucoma.org/u/groma)\
**Post date:** [July 28, 2019, 5:13pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/24 "2019-07-28T17:13:15Z")

</div>

I did not know either, although the magic here is the KDTree. Back to the yes/no quesiton, less dimensions will alwyas be faster, and in some cases it may help discarding useless information (say one descriptor is almost always zero), but not necessarily (e.g. if it is kind of random it may still be harmful).  
Yet the most important cost is in the construction of the tree, which you may do in advance in many cases.

---

<div class="post-metadata">

**Author:** ![jamesbradbury](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/jamesbradbury/32/1252_2.png) [@jamesbradbury](https://discourse.flucoma.org/u/jamesbradbury)\
**Post date:** [July 29, 2019, 10:35pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/25 "2019-07-29T22:35:05Z")

</div>

> [@weefuzzy](#):
>
> You might find that some of the more contemporary techniques like ISOMap or t-SNE give you as good or better results without needing to throw everything at it.

So I’m starting to look at these and I have a few questions/clarifications from more experienced people i.e @weefuzzy and @groma or anyone who has some insight. Please correct me where appropriate.

- t-sne is mostly concerned with distances between points. I don’t need to standardise the data but normalisation is important if i want to make features between analysis equally weighted…correct?

- should I standardise/normalise the input data for the isomap? Is it basically the same concerns as point 1?

---

<div class="post-metadata">

**Author:** ![groma](https://discourse.flucoma.org/letter_avatar_proxy/v4/letter/g/a4c791/32.png) [@groma](https://discourse.flucoma.org/u/groma)\
**Post date:** [July 30, 2019, 10:47am UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/26 "2019-07-30T10:47:19Z")

</div>

In our experience standardizing does not make a difference for the algorithms we tried. I guess the explanation would depend on the algorithm, but they all have to deal with the different distributions and scales of each dimension anyway.

---

<div class="post-metadata">

**Author:** ![jamesbradbury](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/jamesbradbury/32/1252_2.png) [@jamesbradbury](https://discourse.flucoma.org/u/jamesbradbury)\
**Post date:** [July 30, 2019, 1:19pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/27 "2019-07-30T13:19:22Z")

</div>

Okay thanks Gerard! I will stick to normalising so that the weighting is uniform.

---

<div class="post-metadata">

**Author:** ![rodrigo.constanzo](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/rodrigo.constanzo/32/12_2.png) [@rodrigo.constanzo](https://discourse.flucoma.org/u/rodrigo.constanzo)\
**Post date:** [May 4, 2020, 11:01pm UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/28 "2020-05-04T23:01:59Z")

</div>

Bit of a necro bump here, but now that I’m working through the Kaizo Snare blog post properly, I’m putting up and filming relevant bits of stuff. So I’ve cleaned up this code some and made a video demoing the audio-based version of this.

---

<div class="post-metadata">

**Author:** ![tremblap](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/tremblap/32/5_2.png) [@tremblap](https://discourse.flucoma.org/u/tremblap)\
**Post date:** [May 5, 2020, 7:24am UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/29 "2020-05-05T07:24:36Z")

</div>

> [@rodrigo.constanzo](#):
>
> now that I’m working through the Kaizo Snare blog post properly

wooohoooo! Looking forward to reading it!

---

<div class="post-metadata">

**Author:** ![rodrigo.constanzo](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/rodrigo.constanzo/32/12_2.png) [@rodrigo.constanzo](https://discourse.flucoma.org/u/rodrigo.constanzo)\
**Post date:** [May 5, 2020, 8:04am UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/30 "2020-05-05T08:04:02Z")

</div>

Man, it’s gonna be a long one. Not sure if it will be as long as the [Improv Analysis](http://www.rodrigoconstanzo.com//2015/04/making-decisions-in-time/) or [Cut Glove](http://www.rodrigoconstanzo.com/2015/06/cut-glove/) ones, but I have so much media and example I filmed along the way, it feels endless…

---

<div class="post-metadata">

**Author:** ![tremblap](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/tremblap/32/5_2.png) [@tremblap](https://discourse.flucoma.org/u/tremblap)\
**Post date:** [May 5, 2020, 8:18am UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/31 "2020-05-05T08:18:41Z")

</div>

> [@rodrigo.constanzo](#):
>
> it feels endless…

Obvious idea: break it in chapters, on vision/tech/trials/gig etc? Its 2020 nobody likes long reads 🙂 Cheeky humour apart, I am looking forward to reading your blog as usual! I’m sure @jacob.hart is also looking forward to it…

---

<div class="post-metadata">

**Author:** ![rodrigo.constanzo](https://discourse.flucoma.org/user_avatar/discourse.flucoma.org/rodrigo.constanzo/32/12_2.png) [@rodrigo.constanzo](https://discourse.flucoma.org/u/rodrigo.constanzo)\
**Post date:** [May 5, 2020, 8:36am UTC](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298/32 "2020-05-05T08:36:13Z")

</div>

Yeah obviously done that.

Not doing formal subsections, but each section gets fairly deep into details and stuff, but I don’t like the look of subsections.

[Previous page](https://discourse.flucoma.org/t/descriptor-based-sample-navigation-via-dimensional-reduction-ish-proof-of-concept/298.md?page=1)