Name
Abstract | ||
|---|---|---|
Hilbert sort arranges given points of a high-dimensional space with integer coordinates along a Hilbert curve. A naive method first draws a Hilbert curve of a sufficient resolution to separate all the points, associates integers called Hilbert indices representing the orders along the Hilbert curve to points, and then, sorts the pairs of points and indices. Such a method requires an exponentially large cost with respect to both the dimensionality n of the space and the order m of the Hilbert curve even if obtaining Hilbert indices. A known improved method computes the Hilbert index for each point in O(mn) time. In this paper, we propose an algorithm which directly sorts N points along a Hilbert curve in O(mnN) time without using Hilbert indices. This algorithm has the following three advantages; (1) it requires no extra space for Hilbert indices, (2) it handles simultaneously multiple points, and (3) it simulates the Hilbert curve in heterogeneous resolution, that is, in lower order for sparse space and higher order for dense space. It, therefore, runs much faster on random data in O(NlogN) time. Furthermore, it can be expected to run very fast on practical data, such as high-dimensional features of multimedia data. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-46759-7_20 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Projective Hilbert space,Hilbert series and Hilbert polynomial,Moore curve,Hilbert R-tree,Hilbert spectral analysis,Mathematics,Rigged Hilbert space,Reproducing kernel Hilbert space,Hilbert curve | Conference | 9939 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
3 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yasunobu Imamura | 1 | 0 | 0.34 |
| takeshi shinohara | 2 | 103 | 12.69 |
| Kouichi Hirata | 3 | 130 | 32.04 |
| Tetsuji Kuboyama | 4 | 140 | 29.36 |