Z-order curve (original) (raw)
Mortonův rozklad (též Mortonova Z-křivka, Morton scan order, Z-order curve) je prostor vyplňující křivka, která udává lineární pořadí průchodu vícerozměrným prostorem. Jinými slovy mapuje vícerozměrný prostor do jednorozměrného. Poprvé ji v roce 1966 představil zaměstnanec kanadské IBM .
| Property | Value |
|---|---|
| dbo:abstract | La corba de Lebesgue és una corba fractal contínua que recobreix el pla i és derivable gairebé a tots els punts, introduïda per Henri Lebesgue l'any 1905. També s'anomena corba de Morton per , el primer informàtic de dades que va fer-la servir per emmagatzemar dades de forma seqüencial, com a mapatge de dades multidimensionals a una única dimensió preservant la localitat dels punts de dades propers. Aquest mapatge és efectiu perquè la corba correspon al valor z d'un punt multidimensional, és a dir, una estructura intercalada de les representacions binàries dels seus valors de coordenades; per aquest motiu també se l'anomena corba d'ordre z. Un cop ordenades les dades en aquest ordre, es pot utilitzar qualsevol estructura de dades unidimensionals, com ara arbres de cerca binària, arbres B, skip lists o taules hash.L'ordenació resultant es pot descriure de manera equivalent com l'ordre que s'obtindria d'un primer recorregut de profunditat d'un quadtree. (ca) Mortonův rozklad (též Mortonova Z-křivka, Morton scan order, Z-order curve) je prostor vyplňující křivka, která udává lineární pořadí průchodu vícerozměrným prostorem. Jinými slovy mapuje vícerozměrný prostor do jednorozměrného. Poprvé ji v roce 1966 představil zaměstnanec kanadské IBM . (cs) Die Z-Kurve (Lebesgue-Kurve, englisch Z-order curve) ist eine Abbildung, die Punkte aus dem mehrdimensionalen Raum in eine lineare Ordnung, die Z-Ordnung oder Morton-Ordnung, bringt, eine Ordnung mit nachbarschaftserhaltenden Eigenschaften: Wenn zwei Raumpunkte im Mehrdimensionalen nah beisammen liegen, liegen mit hoher Wahrscheinlichkeit auch ihre Z-Werte nah beisammen. Der Z-Wert eines Raumpunktes wird durch bitweises Verschränken der binären Koordinatenwerte berechnet. Mit Hilfe der Z-Ordnung lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört Binäres Suchen, Binärer Suchbaum, Skip-Liste, B-Baum, oder ein B+-Baum. Im letzteren Fall wird er nach Rudolf Bayer UB-Baum (Universal B-Tree) genannt. Die Z-Ordnung ist auch vorteilhaft, wenn sich an einen Direktzugriff eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen vorteilhaft ausgenutzt werden können. Die Z-Ordnung ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung und der einfachen Berechenbarkeit der Z-Werte. Bei der Hilbert-Kurve ist die Nachbarschaftserhaltung besser, doch sind die Rechnungen komplizierter. Dieser Artikel beschäftigt sich ganz vorwiegend mit dem zweidimensionalen Fall. (de) En mathématiques, et plus précisément en géométrie, la courbe de Lebesgue a été étudiée par le mathématicien français Henri Lebesgue en 1904. Elle consiste en une courbe continue, de l'intervalle [0, 1] dans le carré et qui remplit entièrement le carré. Elle constitue donc une courbe de remplissage. (fr) In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It is named in France after Henri Lebesgue, who studied it in 1904, and named in US after , who first applied the order to file sequencing in 1966. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree or octree. (en) 解析学、計算機科学、数学的な関数など分野ごとに、 Z階数、 ルベーグ曲線、 モートン階数 あるいは モートン符号 などと呼ばれ、多次元のデータをその局所部位の部分データを保持したまま1次元に写像する手法である。本手法は 1966 年に により発表された。この手法では多次元のデータに含まれるある点の部分データを、その点の座標値の2進符号化に現れる交互配置性を基に単純な計算による z値 として表す。一度、この階数によりデータを再配置すれば、2分木、B木、スキップリスト、ハッシュテーブルなどのあらゆる1次元のデータを扱う構造が適用可能となる。これは 4分木 の深度優先探索とも等価である。 (ja) В математическом анализе и информатике кривая Мортона, Z-последовательность, Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 году Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры, такие как двоичные деревья поиска, B-деревья, списки с пропусками или хеш-таблицы (с отбрасыванием младших битов). Созданный таким образом порядок можно эквивалентно описать как порядок, который можно получить обходом в глубину дерева квадрантов. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Four-level_Z.svg?width=300 |
| dbo:wikiPageExternalLink | https://sites.google.com/a/compgeom.com/stann/ http://graphics.stanford.edu/~seander/bithacks.html%23InterleaveTableObvious |
| dbo:wikiPageID | 1699416 (xsd:integer) |
| dbo:wikiPageLength | 18629 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109793531 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_code dbr:Binary_search_tree dbr:Bitwise_operations dbc:Database_algorithms dbr:Depth-first_search dbr:Interleave_sequence dbr:GPU dbr:Mathematical_analysis dbr:Geohash dbr:Quadtree dbr:R-tree dbr:Function_(mathematics) dbr:Linear_algebra dbr:Computer_science dbr:Parallel_algorithm dbr:Pointer_(computer_programming) dbr:Strassen_algorithm dbr:Matrix_representation dbr:B-tree dbc:Geometric_data_structures dbr:Transbase dbc:Fractal_curves dbr:Locality_of_reference dbc:Linear_algebra dbr:Exclusive_or dbr:Barnes–Hut_simulation dbr:Hilbert_R-tree dbr:Hilbert_curve dbr:Hash_table dbr:Henri_Lebesgue dbr:UB-tree dbc:Database_index_techniques dbr:Sparse_matrix dbr:Spatial_index dbr:Space-filling_curve dbr:Synchronous_dynamic_random-access_memory dbr:Netto's_theorem dbr:Locality_preserving_hashing dbr:Octree dbr:Moser–de_Bruijn_sequence dbr:PH-tree dbr:Skip_list dbr:Oracle_database dbr:Texture_map dbr:Texture_mapped_rasterization dbr:Cache_lines dbr:File:Moser–de_Bruijn_addition.svg dbr:File:Z-curve45.svg dbr:File:BIGMIN_search_in_a_Z-order_curve.svg dbr:File:Four-level_Z.svg dbr:File:Zcurve45bits.png dbr:Guy_Macdonald_Morton dbr:Oct-tree_hashing |
| dbp:direction | vertical (en) |
| dbp:footer | Z-order curve iterations extended to three dimensions. (en) |
| dbp:image | Lebesgue-3d-step2.png (en) Lebesgue-3d-step3.png (en) |
| dbp:width | 150 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Clear dbt:Distinguish dbt:Multiple_image dbt:Nobreak dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Database_algorithms dbc:Geometric_data_structures dbc:Fractal_curves dbc:Linear_algebra dbc:Database_index_techniques |
| gold:hypernym | dbr:Function |
| rdf:type | owl:Thing yago:WikicatCurves yago:Ability105616246 yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Attribute100024264 yago:Cognition100023271 yago:Curve113867641 yago:DataStructure105728493 yago:Event100029378 yago:Form105930736 yago:Fractal105931152 yago:Know-how105616786 yago:Line113863771 yago:Method105660268 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricDataStructures yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:Shape100027807 yago:Structure105726345 yago:Technique105665146 yago:WikicatDatabaseAlgorithms yago:WikicatDatabaseIndexTechniques yago:WikicatFractalCurves yago:WikicatFractals |
| rdfs:comment | Mortonův rozklad (též Mortonova Z-křivka, Morton scan order, Z-order curve) je prostor vyplňující křivka, která udává lineární pořadí průchodu vícerozměrným prostorem. Jinými slovy mapuje vícerozměrný prostor do jednorozměrného. Poprvé ji v roce 1966 představil zaměstnanec kanadské IBM . (cs) En mathématiques, et plus précisément en géométrie, la courbe de Lebesgue a été étudiée par le mathématicien français Henri Lebesgue en 1904. Elle consiste en une courbe continue, de l'intervalle [0, 1] dans le carré et qui remplit entièrement le carré. Elle constitue donc une courbe de remplissage. (fr) 解析学、計算機科学、数学的な関数など分野ごとに、 Z階数、 ルベーグ曲線、 モートン階数 あるいは モートン符号 などと呼ばれ、多次元のデータをその局所部位の部分データを保持したまま1次元に写像する手法である。本手法は 1966 年に により発表された。この手法では多次元のデータに含まれるある点の部分データを、その点の座標値の2進符号化に現れる交互配置性を基に単純な計算による z値 として表す。一度、この階数によりデータを再配置すれば、2分木、B木、スキップリスト、ハッシュテーブルなどのあらゆる1次元のデータを扱う構造が適用可能となる。これは 4分木 の深度優先探索とも等価である。 (ja) В математическом анализе и информатике кривая Мортона, Z-последовательность, Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 году Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры, такие как двоичные деревья поиска, B-деревья, списки с пропусками или хеш-таблицы (с отбрасыванием младших битов). Созданный таким образом порядок можно эквивалентно описать как порядок, который можно получить обходом в глубину дерева квадрантов. (ru) La corba de Lebesgue és una corba fractal contínua que recobreix el pla i és derivable gairebé a tots els punts, introduïda per Henri Lebesgue l'any 1905. També s'anomena corba de Morton per , el primer informàtic de dades que va fer-la servir per emmagatzemar dades de forma seqüencial, com a mapatge de dades multidimensionals a una única dimensió preservant la localitat dels punts de dades propers. Aquest mapatge és efectiu perquè la corba correspon al valor z d'un punt multidimensional, és a dir, una estructura intercalada de les representacions binàries dels seus valors de coordenades; per aquest motiu també se l'anomena corba d'ordre z. Un cop ordenades les dades en aquest ordre, es pot utilitzar qualsevol estructura de dades unidimensionals, com ara arbres de cerca binària, arbres B, (ca) Die Z-Kurve (Lebesgue-Kurve, englisch Z-order curve) ist eine Abbildung, die Punkte aus dem mehrdimensionalen Raum in eine lineare Ordnung, die Z-Ordnung oder Morton-Ordnung, bringt, eine Ordnung mit nachbarschaftserhaltenden Eigenschaften: Wenn zwei Raumpunkte im Mehrdimensionalen nah beisammen liegen, liegen mit hoher Wahrscheinlichkeit auch ihre Z-Werte nah beisammen. Der Z-Wert eines Raumpunktes wird durch bitweises Verschränken der binären Koordinatenwerte berechnet. Dieser Artikel beschäftigt sich ganz vorwiegend mit dem zweidimensionalen Fall. (de) In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It is named in France after Henri Lebesgue, who studied it in 1904, and named in US after , who first applied the order to file sequencing in 1966. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a d (en) |
| rdfs:label | Corba de Lebesgue (ca) Mortonův rozklad (cs) Z-Kurve (de) Courbe de Lebesgue (fr) Z階数曲線 (ja) Кривая Мортона (ru) Z-order curve (en) |
| owl:differentFrom | dbr:Z_curve dbr:Z-order |
| owl:sameAs | freebase:Z-order curve yago-res:Z-order curve wikidata:Z-order curve dbpedia-ca:Z-order curve dbpedia-cs:Z-order curve dbpedia-de:Z-order curve dbpedia-fa:Z-order curve dbpedia-fr:Z-order curve dbpedia-ja:Z-order curve dbpedia-ru:Z-order curve dbpedia-sr:Z-order curve https://global.dbpedia.org/id/Mity |
| prov:wasDerivedFrom | wikipedia-en:Z-order_curve?oldid=1109793531&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/BIGMIN_search_in_a_Z-order_curve.svg wiki-commons:Special:FilePath/Four-level_Z.svg wiki-commons:Special:FilePath/Lebesgue-3d-step2.png wiki-commons:Special:FilePath/Lebesgue-3d-step3.png wiki-commons:Special:FilePath/Moser–de_Bruijn_addition.svg wiki-commons:Special:FilePath/Z-curve45.svg wiki-commons:Special:FilePath/Zcurve45bits.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Z-order_curve |
| is dbo:wikiPageRedirects of | dbr:Morton-order dbr:Morton-order_matrix_representation dbr:Morton-order_matrix_represention dbr:Morton_code dbr:Morton_order dbr:Morton_number_(number_theory) dbr:Z-order_(curve) dbr:Texture_Swizzling dbr:Swizzled_textures |
| is dbo:wikiPageWikiLink of | dbr:Morton-order dbr:Morton-order_matrix_representation dbr:Morton-order_matrix_represention dbr:Morton_code dbr:Morton_order dbr:Interleave_sequence dbr:Geographic_coordinate_system dbr:Geohash dbr:Geohash-36 dbr:Quadtree dbr:GeoMesa dbr:Swizzling_(computer_graphics) dbr:Address_geocoding dbr:Discrete_global_grid dbr:Spatiotemporal_database dbr:Quater-imaginary_base dbr:Moser–de_Bruijn_sequence dbr:PH-tree dbr:Morton_number_(number_theory) dbr:Z-order_(curve) dbr:Texture_Swizzling dbr:Swizzled_textures |
| is foaf:primaryTopic of | wikipedia-en:Z-order_curve |
