We humans mostly deal with low dimensional data, so we give this type of structure some names:
<\/p>\n\n\n\n
- 1-D data: binary tree<\/li>
- 2-D data: quadtree<\/li>
- 3-D data: octree<\/li>
- K-D data: k-d tree<\/strong>, or k-dimensional\u00a0tree<\/strong>, is a data structure used in computer science for organizing some number of points in a space with k dimensions.<\/li><\/ul>\n\n\n\n
These are all tree-like data structures, which are very useful for range and nearest neighbor searches.<\/p>\n\n\n\n
Octree example
<\/figcaption><\/figure>\n\n\n\nSpace Filling Curves<\/strong><\/h2>\n\n\n\n
Space filling curves<\/strong> refers to a class of functions<\/em> that k dimensional data to 1 dimension. <\/p>\n\n\n\n
Meaning a class of functions that can map k-dimensional data into a single number n<\/p>\n\n\n\n
f(n_1, n_2, …, n_k) -> n <\/em><\/p>\n\n\n\n
The caveat is there is a restriction on the number it maps, i.e. n_1, as space filling curves are a fractal functions, it cannot be extended to the reals, but rather to the binary fractions (a subset of the rationals). This lets you get arbitrarily close to any number you want (and cover all the IEEE floating points).<\/p>\n\n\n\n
Class of functions means that there are many functions that can be considered a space filling curve. Common to use Hibert and Z-order.
<\/figcaption><\/figure>\n\n\n\nVisualization of a 3D space filling curve may look like with a Hilbert curve function.<\/figcaption><\/figure>\n\n\n\n Compare and contrast<\/h2>\n\n\n\n
There are certain optimal use cases for each of these. <\/p>\n\n\n\n
- Trees have the benefit being able to limit the depth of your queries, which makes it especially useful in computer graphics so you can stop querying for points that you don’t need.<\/li>
- Space filling curves have the benefit of modify data faster, because the location to store that data can be calculated. Because trees have the cost of potentially rebalancing subtrees and creating\/updating\/deleting. <\/li><\/ul>\n\n\n\n
Other structures?<\/h2>\n\n\n\n
There are some variants on structures for storing multi-dimensional data.<\/p>\n\n\n\n
R-Tree<\/strong><\/a><\/p>\n\n\n\n
It’s yet another type of tree.<\/p>\n\n\n\n
Visualization of an R*-tree for 3D points using ELKI<\/a>.Hilbert R-Tree<\/a> is a variant on the R-Tree to achieve better performance. <\/figcaption><\/figure>\n\n\n\n Data Stores<\/h2>\n\n\n\n
I won’t go in too much detail because this is out of scope, but in programming there are databases and data stores which can handle large amount of high dimensional data. <\/p>\n\n\n\n
First, a distinction. A database<\/strong> can handle complex queries. A data store<\/strong> can be dumber, simple storage format and won’t handle things like transaction for you. <\/p>\n\n\n\n
An analogy could be like “database<\/strong> is like an accountant, who you can ask for certain data and operations, such as ‘give me all last year’s data for people with last names in T'”, whereas “data store<\/strong> is like a library and you have to go find and collect that data yourself, but it’s stored in an organized fashion”.<\/p>\n","protected":false},"excerpt":{"rendered":"
Octree An\u00a0octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. We humans mostly deal with low dimensional data, so we give this type of structure … Continue reading Space Filling Curves vs. Octree<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[34],"tags":[39,52,51,50,54,53],"class_list":["post-844","post","type-post","status-publish","format-standard","hentry","category-thoughts","tag-3d","tag-data-structure","tag-lidar","tag-mapping","tag-octree","tag-space-filling-curve"],"_links":{"self":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/comments?post=844"}],"version-history":[{"count":1,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/844\/revisions"}],"predecessor-version":[{"id":845,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/posts\/844\/revisions\/845"}],"wp:attachment":[{"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/media?parent=844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/categories?post=844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sunapi386.ca\/wordpress\/wp-json\/wp\/v2\/tags?post=844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"\/](\"https:\/\/lh6.googleusercontent.com\/1uIuBlcjMAH-WhzYvl_iXwMPPTi4-Shz9OBYeK-SeAhMw-ptQ9lXF1y0550ELEZqyBeKvDIheD0jG4ui_M19m_W-26h-4BYRPAHTlLyaKRTTVB6RLUMiVskYFDWu_y7KYOy-jYsf\")
![\"\"\/](\"https:\/\/lh4.googleusercontent.com\/h2AG8Mf4nkrjJC4M15_AO4Ghug4dRUNDngs4diLulvNU2_ubNlyvqLRe5gKJFnWXiovG_mVGQCe9iYUVQB6WqKdmE02lYJsuWVEdupE4AJkQW1PITkrQnLdf3_DvVrotDmIBeNrw\")
![\"\"\/](\"https:\/\/lh5.googleusercontent.com\/tKLAndmJhaDHJXTOtsFakcv5fe3Z1Fh_mbyJ3dgSFaJy2zO918_fl4yjrR5BK8N8uUsh8v_vPOptZHSqlKQceGV1xuQUJkq3sdAdUZcPoVE_qcgu2eh7V_TQMoll72TP6IPd6O42\")
![\"\"\/](\"https:\/\/lh5.googleusercontent.com\/1m7HULfC39N-ZXcG1LM0UIEC18laSjcnoZDmi8dxD8UuyYerFoJtIlfbQvlv-xHHMOjU01NzTKL4qON8riV--HDgvhCkMcDf1lPj0pYgx8AQbOZSCgS7jExIaey1IF6aUXWnEg5N\")