Space-filling Curves for High-performance Data Mining

• URL: http://arxiv.org/abs/2008.01684v1
• Date: Tue, 4 Aug 2020 16:41:16 GMT
• Title: Space-filling Curves for High-performance Data Mining
• Authors: Christian B\"ohm
• Abstract summary: Space-filling curves like the Hilbert-curve, Peano-curve and Z-order map natural or real numbers from a two or higher dimensional space to a one dimensional space preserving locality. They have numerous applications like search structures, computer graphics, numerical simulation, cryptographics and can be used to make various algorithms cache-oblivious.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Space-filling curves like the Hilbert-curve, Peano-curve and Z-order map natural or real numbers from a two or higher dimensional space to a one dimensional space preserving locality. They have numerous applications like search structures, computer graphics, numerical simulation, cryptographics and can be used to make various algorithms cache-oblivious. In this paper, we describe some details of the Hilbert-curve. We define the Hilbert-curve in terms of a finite automaton of Mealy-type which determines from the two-dimensional coordinate space the Hilbert order value and vice versa in a logarithmic number of steps. And we define a context-free grammar to generate the whole curve in a time which is linear in the number of generated coordinate/order value pairs, i.e. a constant time per coordinate pair or order value. We also review two different strategies which enable the generation of curves without the usual restriction to square-like grids where the side-length is a power of two. Finally, we elaborate on a few applications, namely matrix multiplication, Cholesky decomposition, the Floyd-Warshall algorithm, k-Means clustering, and the similarity join.

Related papers

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  The percolation transition is defined through the appearance of the infinite cluster. We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient. Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
  arXiv  Detail & Related papers  (2022-10-15T13:53:21Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  Open quantum systems can obey the Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) equation. We exhaustively study the case of a Hilbert space dimension of $2$.
  arXiv  Detail & Related papers  (2022-04-16T07:03:54Z)
• Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces [39.71927912296049]
  We propose a unified framework for learning scalable and simple hyperbolic linear classifiers. The gist of our approach is to focus on Poincar'e ball models and formulate the classification problems using tangent space formalisms. The excellent performance of the Poincar'e second-order and strategic perceptrons shows that the proposed framework can be extended to general machine learning problems in hyperbolic spaces.
  arXiv  Detail & Related papers  (2022-03-07T21:36:21Z)
• Geometric decomposition of geodesics and null phase curves using Majorana star representation [0.0]
  We use Majorana star representation to decompose a geodesic in the Hilbert space to $n-1$ curves on the Bloch sphere. We also propose a method to construct infinitely many NPCs between any two arbitrary states for $(n>2)$-dimensional Hilbert space.
  arXiv  Detail & Related papers  (2022-02-24T17:21:17Z)
• Many Body Quantum Chaos and Dual Unitarity Round-a-Face [0.0]
  We propose a new type of locally interacting quantum circuits which are generated by unitary interactions round-a-face (IRF) We show how arbitrary dynamical correlation functions of local observables can be evaluated in terms of finite dimensional completely positive trace preserving unital maps. We provide additional data on dimensionality of the chiral extension of DUBG circuits with distinct local Hilbert spaces of dimensions $dneq d'$ residing at even/odd lattice sites.
  arXiv  Detail & Related papers  (2021-05-17T17:16:33Z)
• Linear Classifiers in Mixed Constant Curvature Spaces [40.82908295137667]
  We address the problem of linear classification in a product space form -- a mix of Euclidean, spherical, and hyperbolic spaces. We prove that linear classifiers in $d$-dimensional constant curvature spaces can shatter exactly $d+1$ points. We describe a novel perceptron classification algorithm, and establish rigorous convergence results.
  arXiv  Detail & Related papers  (2021-02-19T23:29:03Z)
• Linear-time inference for Gaussian Processes on one dimension [17.77516394591124]
  We investigate data sampled on one dimension for which state-space models are popular due to their linearly-scaling computational costs. We provide the first general proof of conjecture that state-space models are general, able to approximate any one-dimensional Gaussian Processes. We develop parallelized algorithms for performing inference and learning in the LEG model, test the algorithm on real and synthetic data, and demonstrate scaling to datasets with billions of samples.
  arXiv  Detail & Related papers  (2020-03-11T23:20:13Z)
• Radiative topological biphoton states in modulated qubit arrays [105.54048699217668]
  We study topological properties of bound pairs of photons in spatially-modulated qubit arrays coupled to a waveguide. For open boundary condition, we find exotic topological bound-pair edge states with radiative losses. By joining two structures with different spatial modulations, we find long-lived interface states which may have applications in storage and quantum information processing.
  arXiv  Detail & Related papers  (2020-02-24T04:44:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.