Skip to content

Instantly share code, notes, and snippets.

@mikolalysenko

mikolalysenko/Chrome 34

Last active August 29, 2015 13:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mikolalysenko/10758605 to your computer and use it in GitHub Desktop.
Save mikolalysenko/10758605 to your computer and use it in GitHub Desktop.
Download ZIP
Preliminary benchmarks for static-kdtree
Raw
Chrome 34
# Chrome 34
| Data Structure | [Linear scan](http://en.wikipedia.org/wiki/Brute-force_search) | [static-kdtree](https://github.com/mikolalysenko/static-kdtree) | [Ubilabs kdtree](https://github.com/ubilabs/kd-tree-javascript) |
| :--- | ---: | ---: | ---: |
| Dynamic? | ✓ | ✗ | ✓ |
| Works in browser? | ✓ | ✓ | ✓ |
| Construction: (n=100,d=2) | 0ms | 0.1376ms | 0.1204ms |
| Construction: (n=1000,d=2) | 0ms | 1.51ms | 3.102ms |
| Construction: (n=10000,d=2) | 0ms | 17.63ms | 58.74ms |
| Construction: (n=100000,d=2) | 0ms | 214.8ms | 1149.4ms |
| Range: (n=100,d=2) | 0.000833ms | 0.002196ms | N/A |
| Range: (n=1000,d=2) | 0.01036ms | 0.00458ms | N/A |
| Range: (n=10000,d=2) | 0.0999ms | 0.0235ms | N/A |
| Range: (n=100000,d=2) | 1.043ms | 0.195ms | N/A |
| rNN: (n=100,d=2) | 0.00115ms | 0.002827ms | ERROR |
| rNN: (n=1000,d=2) | 0.01121ms | 0.00532ms | ERROR |
| rNN: (n=10000,d=2) | 0.1134ms | 0.0235ms | ERROR |
| rNN: (n=100000,d=2) | 1.22ms | 0.203ms | ERROR |
| kNN: (n=100,d=2,k=1) | 0.001116ms | 0.001891ms | 0.041338ms |
| kNN: (n=1000,d=2,k=1) | 0.010708188428706925ms | 0.002861207714195384ms | 0.05545368321214037ms |
| kNN: (n=10000,d=2,k=1) | 0.10623ms | 0.00385ms | 0.06481ms |
| kNN: (n=100000,d=2,k=1) | 1.0662460567823344ms | 0.004542586750788643ms | 0.0726813880126183ms |
| kNN: (n=100,d=2,k=10) | 0.00628ms | N/A | 0.13818ms |
| kNN: (n=1000,d=2,k=10) | 0.04873817034700315ms | N/A | 0.16933753943217666ms |
| kNN: (n=10000,d=2,k=10) | 0.4583ms | N/A | 0.2004ms |
| kNN: (n=100000,d=2,k=10) | 4.4971875ms | N/A | 0.201875ms |
| kNN: (n=100,d=2,k=100) | 0.006ms | N/A | 0.553ms |
| kNN: (n=1000,d=2,k=100) | 0.0553125ms | N/A | 1.125ms |
| kNN: (n=10000,d=2,k=100) | 0.451ms | N/A | 1.195ms |
| kNN: (n=100000,d=2,k=100) | 4.555ms | N/A | 1.167ms |
Raw
node.js 0.10.26
# node 0.10.26
| Data Structure | [Linear scan](http://en.wikipedia.org/wiki/Brute-force_search) | [static-kdtree](https://github.com/mikolalysenko/static-kdtree) | [Ubilabs kdtree](https://github.com/ubilabs/kd-tree-javascript) | [node-kdtree](https://github.com/justinethier/node-kdtree) |
| :--- | ---: | ---: | ---: | ---: |
| Dynamic? | ✓ | ✗ | ✓ | ✓ |
| Works in browser? | ✓ | ✓ | ✓ | ✗ |
| Construction: (n=100,d=2) | 0ms | 0.1738ms | 0.1083ms | 0.0354ms |
| Construction: (n=1000,d=2) | 0ms | 1.991ms | 1.772ms | 0.435ms |
| Construction: (n=10000,d=2) | 0ms | 23.62ms | 34.1ms | 6.37ms |
| Construction: (n=100000,d=2) | 0ms | 305.6ms | 766.7ms | 124.2ms |
| Range: (n=100,d=2) | 0.001252ms | 0.004351ms | N/A | N/A |
| Range: (n=1000,d=2) | 0.01335ms | 0.01418ms | N/A | N/A |
| Range: (n=10000,d=2) | 0.1318ms | 0.0928ms | N/A | N/A |
| Range: (n=100000,d=2) | 2.013ms | 0.812ms | N/A | N/A |
| rNN: (n=100,d=2) | 0.001433ms | 0.005687ms | ERROR | 0.002928ms |
| rNN: (n=1000,d=2) | 0.01459ms | 0.01438ms | ERROR | 0.01522ms |
| rNN: (n=10000,d=2) | 0.1455ms | 0.0772ms | ERROR | 0.1502ms |
| rNN: (n=100000,d=2) | 2.559ms | 0.707ms | ERROR | 2.023ms |
| kNN: (n=100,d=2,k=1) | 0.001372ms | 0.005088ms | 0.004811ms | 0.001671ms |
| kNN: (n=1000,d=2,k=1) | 0.013727473917167247ms | 0.006772051849509959ms | 0.006421119190641796ms | 0.0021656655074296554ms |
| kNN: (n=10000,d=2,k=1) | 0.1367ms | 0.00888ms | 0.00851ms | 0.00409ms |
| kNN: (n=100000,d=2,k=1) | 1.5938170347003155ms | 0.010157728706624606ms | 0.009495268138801262ms | 0.009558359621451105ms |
| kNN: (n=100,d=2,k=10) | 0.00745ms | N/A | 0.01614ms | N/A |
| kNN: (n=1000,d=2,k=10) | 0.06082018927444795ms | N/A | 0.019968454258675078ms | N/A |
| kNN: (n=10000,d=2,k=10) | 0.5784ms | N/A | 0.0299ms | N/A |
| kNN: (n=100000,d=2,k=10) | 7.0034375ms | N/A | 0.0315625ms | N/A |
| kNN: (n=100,d=2,k=100) | 0.0082ms | N/A | 0.0627ms | N/A |
| kNN: (n=1000,d=2,k=100) | 0.07ms | N/A | 0.14125ms | N/A |
| kNN: (n=10000,d=2,k=100) | 0.6ms | N/A | 0.208ms | N/A |
| kNN: (n=100000,d=2,k=100) | 7.415ms | N/A | 0.208ms | N/A |
@mikolalysenko
Copy link
Author

Chrome 34

Data Structure Linear scan static-kdtree Ubilabs kdtree
Dynamic? ✓ ✗ ✓
Works in browser? ✓ ✓ ✓
Construction: (n=100,d=2) 0ms 0.1376ms 0.1204ms
Construction: (n=1000,d=2) 0ms 1.51ms 3.102ms
Construction: (n=10000,d=2) 0ms 17.63ms 58.74ms
Construction: (n=100000,d=2) 0ms 214.8ms 1149.4ms
Range: (n=100,d=2) 0.000833ms 0.002196ms N/A
Range: (n=1000,d=2) 0.01036ms 0.00458ms N/A
Range: (n=10000,d=2) 0.0999ms 0.0235ms N/A
Range: (n=100000,d=2) 1.043ms 0.195ms N/A
rNN: (n=100,d=2) 0.00115ms 0.002827ms ERROR
rNN: (n=1000,d=2) 0.01121ms 0.00532ms ERROR
rNN: (n=10000,d=2) 0.1134ms 0.0235ms ERROR
rNN: (n=100000,d=2) 1.22ms 0.203ms ERROR
kNN: (n=100,d=2,k=1) 0.001116ms 0.001891ms 0.041338ms
kNN: (n=1000,d=2,k=1) 0.010708188428706925ms 0.002861207714195384ms 0.05545368321214037ms
kNN: (n=10000,d=2,k=1) 0.10623ms 0.00385ms 0.06481ms
kNN: (n=100000,d=2,k=1) 1.0662460567823344ms 0.004542586750788643ms 0.0726813880126183ms
kNN: (n=100,d=2,k=10) 0.00628ms N/A 0.13818ms
kNN: (n=1000,d=2,k=10) 0.04873817034700315ms N/A 0.16933753943217666ms
kNN: (n=10000,d=2,k=10) 0.4583ms N/A 0.2004ms
kNN: (n=100000,d=2,k=10) 4.4971875ms N/A 0.201875ms
kNN: (n=100,d=2,k=100) 0.006ms N/A 0.553ms
kNN: (n=1000,d=2,k=100) 0.0553125ms N/A 1.125ms
kNN: (n=10000,d=2,k=100) 0.451ms N/A 1.195ms
kNN: (n=100000,d=2,k=100) 4.555ms N/A 1.167ms

node 0.10.26

Data Structure Linear scan static-kdtree Ubilabs kdtree node-kdtree
Dynamic? ✓ ✗ ✓ ✓
Works in browser? ✓ ✓ ✓ ✗
Construction: (n=100,d=2) 0ms 0.1738ms 0.1083ms 0.0354ms
Construction: (n=1000,d=2) 0ms 1.991ms 1.772ms 0.435ms
Construction: (n=10000,d=2) 0ms 23.62ms 34.1ms 6.37ms
Construction: (n=100000,d=2) 0ms 305.6ms 766.7ms 124.2ms
Range: (n=100,d=2) 0.001252ms 0.004351ms N/A N/A
Range: (n=1000,d=2) 0.01335ms 0.01418ms N/A N/A
Range: (n=10000,d=2) 0.1318ms 0.0928ms N/A N/A
Range: (n=100000,d=2) 2.013ms 0.812ms N/A N/A
rNN: (n=100,d=2) 0.001433ms 0.005687ms ERROR 0.002928ms
rNN: (n=1000,d=2) 0.01459ms 0.01438ms ERROR 0.01522ms
rNN: (n=10000,d=2) 0.1455ms 0.0772ms ERROR 0.1502ms
rNN: (n=100000,d=2) 2.559ms 0.707ms ERROR 2.023ms
kNN: (n=100,d=2,k=1) 0.001372ms 0.005088ms 0.004811ms 0.001671ms
kNN: (n=1000,d=2,k=1) 0.013727473917167247ms 0.006772051849509959ms 0.006421119190641796ms 0.0021656655074296554ms
kNN: (n=10000,d=2,k=1) 0.1367ms 0.00888ms 0.00851ms 0.00409ms
kNN: (n=100000,d=2,k=1) 1.5938170347003155ms 0.010157728706624606ms 0.009495268138801262ms 0.009558359621451105ms
kNN: (n=100,d=2,k=10) 0.00745ms N/A 0.01614ms N/A
kNN: (n=1000,d=2,k=10) 0.06082018927444795ms N/A 0.019968454258675078ms N/A
kNN: (n=10000,d=2,k=10) 0.5784ms N/A 0.0299ms N/A
kNN: (n=100000,d=2,k=10) 7.0034375ms N/A 0.0315625ms N/A
kNN: (n=100,d=2,k=100) 0.0082ms N/A 0.0627ms N/A
kNN: (n=1000,d=2,k=100) 0.07ms N/A 0.14125ms N/A
kNN: (n=10000,d=2,k=100) 0.6ms N/A 0.208ms N/A
kNN: (n=100000,d=2,k=100) 7.415ms N/A 0.208ms N/A

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