K-d tree (original) (raw)
Ein -dimensionaler Baum oder -d-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür liegt der Speicheraufwand in statt in (siehe Komplexitätstheorie - Landau-Notation). k-d-Bäume sind Spezialfälle von BSP-Bäumen, deren teilende Hyperebenen entlang der Achsen des Koordinatensystems ausgerichtet sind. Er wurde von Jon Bentley eingeführt.
| Property | Value |
|---|---|
| dbo:abstract | Ein -dimensionaler Baum oder -d-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür liegt der Speicheraufwand in statt in (siehe Komplexitätstheorie - Landau-Notation). k-d-Bäume sind Spezialfälle von BSP-Bäumen, deren teilende Hyperebenen entlang der Achsen des Koordinatensystems ausgerichtet sind. Er wurde von Jon Bentley eingeführt. (de) In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. k-d trees are a special case of binary space partitioning trees. (en) En ciencias de la computación, un Árbol kd (abreviatura de árbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un Espacio euclídeo de k dimensiones. Los árboles kd son un caso especial de los árboles BSP. Un árbol kd emplea sólo planos perpendiculares a uno de los ejes del sistema de coordenadas. Esto difiere de los árboles BSP, donde los planos pueden ser arbitrarios. Además, todos los nodos de un árbol kd, desde el nodo raíz hasta los nodos hoja, almacenan un punto. Mientras tanto, en los árboles BSP son las hojas los únicos nodos que contienen puntos (u otras primitivas geométricas). Como consecuencia, cada plano debe pasar a través de uno de los puntos del árbol kd. Técnicamente, la letra k se refiere al número de dimensiones. Un árbol kd tridimensional podría ser llamado un árbol 3d. Sin embargo se suele emplear la expresión "árbol kd tridimensional". (También es más descriptivo, ya que un árbol tridimensional puede ser varias cosas, pero el término árbol kd se refiere a un tipo en concreto de árbol de particionado.) Las letras k y d se escriben en minúsculas, incluso al principio de una oración. La k se escribe en cursiva, aunque son también comunes las formas "árbol KD" y "árbol Kd". (es) Un arbre k-d (ou k-d tree, pour k-dimensional tree) est une structure de données de partition de l'espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees). Cette structure a été proposée par Jon Louis Bentley de l'Université Stanford en 1975. (fr) 컴퓨터 과학에서 k-d 트리(영어: k-d tree, k-차원(dimensional) 트리)는 k차원 공간의 점들을 구조화하는 자료 구조이다. k-d 트리는 다차원 탐색 키에 관련된 탐색 같은 적용분야에 유용한 자료구조이다(예: 과 최근접 이웃 탐색). k-d 트리는 이진 공간 분할 트리의 특수한 경우이다. (ko) kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造をと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。 (ja) Drzewo kd (ang. k-dimensional tree, k-d tree, drzewo k-wymiarowe) – struktura danych, będąca wariantem drzew binarnych, używana do . Drzewa kd są przydatne do tworzenia struktur w niektórych zastosowaniach, takich jak lub znajdowanie punktów w prostokątnych obszarach. Czasowa złożoność obliczeniowa tych zadań wynosi gdzie to całkowita liczba punktów, – liczba znalezionych punktów. (pl) k-d-дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d-деревья — особый вид двоичных деревьев поиска. (ru) Em ciência da computação, uma árvore k-d (abreviação para a árvore k-dimensional) é uma estrutura de dados de para a organização de pontos em um k-dimensional espaço. Árvores k-d são estruturas úteis para uma série de aplicações, tais como pesquisas envolvendo de chaves (e.g. e busca do vizinho mais próximo). Árvores k-d são um caso especial de árvores de particionamento binário de espaço. (pt) В інформатиці k-d дерево (англ. k-d tree, скорочення від k-вимірне дерево) — це структура даних з поділом простору для упорядкування точок в k-вимірному просторі. K-d дерева використовуються для деяких застосувань, таких як пошук у багатовимірному просторі ключів ( і пошук найближчого сусіда). K-d дерева — особливий вид дерев двійкового поділу простору. (uk) 在计算机科学里，k-d树（k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（binary space partitioning）的一种特殊情况。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/3dtree.png?width=300 |
| dbo:wikiPageID | 1676725 (xsd:integer) |
| dbo:wikiPageLength | 29150 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1115861309 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:SciPy dbr:Scikit-learn dbr:Nearest_neighbor_search dbr:Binary_Search_Tree dbr:Binary_search_tree dbr:Binary_tree dbr:Algorithm dbr:Jon_Bentley_(computer_scientist) dbr:Curse_of_dimensionality dbr:Vantage-point_tree dbr:Interval_tree dbr:Invariant_(computer_science) dbr:Median dbr:Quadtree dbr:R-tree dbr:Bounding_interval_hierarchy dbr:Min/max_kd-tree dbr:Tree_data_structure dbr:Subtree dbc:Computer_graphics_data_structures dbr:Computer_graphics dbr:Computer_science dbr:Half-space_(geometry) dbr:Point_(geometry) dbr:Median_of_medians dbr:C++ dbr:CGAL dbr:C_Sharp_(programming_language) dbr:Adaptive_k-d_tree dbc:Geometric_data_structures dbr:Tree_(data_structure) dbr:Data_structure dbr:K-D-B-tree dbr:ALGLIB dbc:Data_types dbr:Euclidean_space dbr:Ball_tree dbr:Guillotine_problem dbr:Heapsort dbr:Hyperplane dbr:Hyperrectangle dbc:Articles_with_example_Python_(programming_language)_code dbc:Trees_(data_structures) dbr:Big_O_notation dbr:Binary_space_partitioning dbr:Ray_tracing_(graphics) dbr:Recursive_partitioning dbr:Relaxed_k-d_tree dbc:Database_index_techniques dbr:Plane_(mathematics) dbr:Mergesort dbr:Nearest_neighbour_search dbr:Rectangle dbr:Klee's_measure_problem dbr:Hypersphere dbr:Tree_rotation dbr:Selection_algorithm dbr:Octree dbr:Point_cloud dbr:Space_partitioning dbr:Orthogonal_range_searching dbr:Implicit_kd-tree dbr:Range_search dbr:Balanced_tree dbr:Best-bin-first_search dbr:Surface_normal dbr:File:Kdtree_2d.svg dbr:File:Kdtreeogg.ogg dbr:File:Tree_0001.svg |
| dbp:caption | A 3-dimensional k-d tree. The first split cuts the root cell into two subcells, each of which is then split into two subcells. Finally, four cells are split into two subcells. Since there is no more splitting, the final eight are called leaf cells. (en) |
| dbp:inventedBy | dbr:Jon_Bentley_(computer_scientist) |
| dbp:inventedYear | 1975 (xsd:integer) |
| dbp:name | k-d tree (en) |
| dbp:type | Multidimensional BST (en) |
| dbp:wikiPageUsesTemplate | dbt:CS-Trees dbt:Expand_section dbt:Main dbt:Reflist dbt:Short_description dbt:Infobox_data_structure |
| dct:subject | dbc:Computer_graphics_data_structures dbc:Geometric_data_structures dbc:Data_types dbc:Articles_with_example_Python_(programming_language)_code dbc:Trees_(data_structures) dbc:Database_index_techniques |
| gold:hypernym | dbr:Structure |
| rdf:type | yago:WikicatComputerGraphicsDataStructures yago:Ability105616246 yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Event100029378 yago:Know-how105616786 yago:Method105660268 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:WikicatGeometricDataStructures yago:YagoPermanentlyLocatedEntity dbo:Building yago:Rule105846932 yago:Structure105726345 yago:Technique105665146 yago:WikicatDatabaseIndexTechniques |
| rdfs:comment | Ein -dimensionaler Baum oder -d-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür liegt der Speicheraufwand in statt in (siehe Komplexitätstheorie - Landau-Notation). k-d-Bäume sind Spezialfälle von BSP-Bäumen, deren teilende Hyperebenen entlang der Achsen des Koordinatensystems ausgerichtet sind. Er wurde von Jon Bentley eingeführt. (de) In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. k-d trees are a special case of binary space partitioning trees. (en) Un arbre k-d (ou k-d tree, pour k-dimensional tree) est une structure de données de partition de l'espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees). Cette structure a été proposée par Jon Louis Bentley de l'Université Stanford en 1975. (fr) 컴퓨터 과학에서 k-d 트리(영어: k-d tree, k-차원(dimensional) 트리)는 k차원 공간의 점들을 구조화하는 자료 구조이다. k-d 트리는 다차원 탐색 키에 관련된 탐색 같은 적용분야에 유용한 자료구조이다(예: 과 최근접 이웃 탐색). k-d 트리는 이진 공간 분할 트리의 특수한 경우이다. (ko) kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造をと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。 (ja) Drzewo kd (ang. k-dimensional tree, k-d tree, drzewo k-wymiarowe) – struktura danych, będąca wariantem drzew binarnych, używana do . Drzewa kd są przydatne do tworzenia struktur w niektórych zastosowaniach, takich jak lub znajdowanie punktów w prostokątnych obszarach. Czasowa złożoność obliczeniowa tych zadań wynosi gdzie to całkowita liczba punktów, – liczba znalezionych punktów. (pl) k-d-дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d-деревья — особый вид двоичных деревьев поиска. (ru) Em ciência da computação, uma árvore k-d (abreviação para a árvore k-dimensional) é uma estrutura de dados de para a organização de pontos em um k-dimensional espaço. Árvores k-d são estruturas úteis para uma série de aplicações, tais como pesquisas envolvendo de chaves (e.g. e busca do vizinho mais próximo). Árvores k-d são um caso especial de árvores de particionamento binário de espaço. (pt) В інформатиці k-d дерево (англ. k-d tree, скорочення від k-вимірне дерево) — це структура даних з поділом простору для упорядкування точок в k-вимірному просторі. K-d дерева використовуються для деяких застосувань, таких як пошук у багатовимірному просторі ключів ( і пошук найближчого сусіда). K-d дерева — особливий вид дерев двійкового поділу простору. (uk) 在计算机科学里，k-d树（k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（binary space partitioning）的一种特殊情况。 (zh) En ciencias de la computación, un Árbol kd (abreviatura de árbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un Espacio euclídeo de k dimensiones. Los árboles kd son un caso especial de los árboles BSP. (es) |
| rdfs:label | K-d-Baum (de) Árbol kd (es) K-d tree (en) Arbre kd (fr) K-d 트리 (ko) Kd木 (ja) Drzewo kd (pl) Árvore k-d (pt) K-d-дерево (ru) K-d树 (zh) K-вимірне дерево (uk) |
| owl:sameAs | freebase:K-d tree yago-res:K-d tree wikidata:K-d tree dbpedia-de:K-d tree dbpedia-es:K-d tree dbpedia-fa:K-d tree dbpedia-fr:K-d tree dbpedia-he:K-d tree dbpedia-ja:K-d tree dbpedia-ko:K-d tree dbpedia-pl:K-d tree dbpedia-pt:K-d tree dbpedia-ru:K-d tree dbpedia-sl:K-d tree dbpedia-sr:K-d tree dbpedia-uk:K-d tree dbpedia-zh:K-d tree https://global.dbpedia.org/id/2suSp |
| prov:wasDerivedFrom | wikipedia-en:K-d_tree?oldid=1115861309&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3dtree.png wiki-commons:Special:FilePath/Kdtree_2d.svg wiki-commons:Special:FilePath/Tree_0001.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:K-d_tree |
| is dbo:wikiPageDisambiguates of | dbr:KD |
| is dbo:wikiPageRedirects of | dbr:KD_tree dbr:Kd-trie dbr:Kd_tree dbr:Extended_k-d_tree dbr:Kd-tree dbr:Kdtree |
| is dbo:wikiPageWikiLink of | dbr:SciPy dbr:Enfilade_(Xanadu) dbr:List_of_data_structures dbr:Nearest_neighbor_search dbr:Metric_tree dbr:Jon_Bentley_(computer_scientist) dbr:Best,_worst_and_average_case dbr:Perst dbr:Vantage-point_tree dbr:Visualization_Library dbr:David_Mount dbr:KD_tree dbr:Kd-trie dbr:Kd_tree dbr:T-tree dbr:Range_tree dbr:R-tree dbr:Search_data_structure dbr:Gerris_(software) dbr:Bounding_volume_hierarchy dbr:Min/max_kd-tree dbr:Pole_of_inaccessibility dbr:Median_cut dbr:CGAL dbr:Adaptive_k-d_tree dbr:K-D-B-tree dbr:DBSCAN dbr:ELKI dbr:EXtremeDB dbr:Ball_tree dbr:Differentiable_neural_computer dbr:Discrete_global_grid dbr:Floorplan_(microelectronics) dbr:Iterative_closest_point dbr:R+_tree dbr:Bag-of-words_model_in_computer_vision dbr:OPTICS_algorithm dbr:Range_searching dbr:Big_O_notation dbr:Bin_(computational_geometry) dbr:Binary_space_partitioning dbr:Relaxed_k-d_tree dbr:Point_Cloud_Library dbr:Scale-invariant_feature_transform dbr:Spatiotemporal_database dbr:Implicit_k-d_tree dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:KD dbr:Octree dbr:Space_partitioning dbr:Russell_A._Brown dbr:Range_query_(database) dbr:Extended_k-d_tree dbr:Kd-tree dbr:Kdtree |
| is rdfs:seeAlso of | dbr:Binary_space_partitioning |
| is foaf:primaryTopic of | wikipedia-en:K-d_tree |
