L^p,q Tree

LpqTree is a C++ library that generalize k-d trees to L^p,q Minkowski mixed-norm (entry-wise matrix distance).
It can be used for, radius search and k-nearest neighbors search for a list of M×N matrices.

Distance / Norm computation

The L^p,q norm is defined like this :

In the LpqTree code, matrix row and column are swapped, for faster operation along the last axis:

import numpy as np
def Lpq_norm(A, p, q):
    return np.sum( np.sum( np.abs(A)**p, axis=-1 )**(q/p), axis=-1)**(1.0/q)

Distance computation is optimized for on L^2,1 applications, with M×2, M×3 or M×4 structures. Meanwhile, it also works for any M×N matrices using L^p,q, where 1 ≤ p ≤ 9 and 1 ≤ q ≤ 9.

K-d Tree Implementation

Modified version of Nanoflann k-d trees to support L^p,q norm.
It includes python binder, pybind11 , based of pynanoflann.

Installation

pip install lpqtree

Python Usage

import numpy as np
import lpqtree
import lpqtree.lpqpydist as lpqdist

# Create 3 matrices composed of four 2D points (4x2)
matrices_a = np.array([[[0.0, 0.0], [1.0, 1.0], [2.0, 1.0], [3.0, 2.0]],
                       [[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [2.0, 2.0]],
                       [[0.0, 1.0], [1.0, 0.0], [2.0, 1.0], [3.0, 2.0]]])

# Create 2 matrices composed of four 2D points (4x2)
matrices_b = np.array([[[0.1, 0.1], [1.5, 0.8], [1.8, 1.0], [2.5, 2.0]],
                       [[3.0, 2.2], [2.0, 1.0], [1.0, 0.0], [0.0, 1.0]]])

# Search metric Lpq apply the "p-norm" along the last axis and the "q-norm" after
lpq_metric = "l21" # L21 is equivalent to the Sum of L2 norm

# Compute the Lpq-norm of each matrix in "matrices_a"
lpqdist.lpq_str_switch(matrices_a, lpq_metric)
# lpqdist.l21(matrices_a) == lpqdist.l1(lpqdist.l2(matrices_a))

# Compute all distances from each pair "matrices_a" to "matrices_b"
lpqdist.lpq_allpairs(matrices_a, matrices_b, p=2, q=1)

# Generate the k-d tree for the search (with "matrices_b")
mtree = lpqtree.KDTree(n_neighbors=1, radius=2.5, metric=lpq_metric)
mtree.fit(matrices_b)

# For each matrix in "matrices_a" search the nearest in "matrices_b"
nn_ids_b, nn_dist = mtree.query(matrices_a)

# For each matrix in "matrices_a" search the nearest in "matrices_b"
ids_a, ids_b, r_dists = mtree.radius_neighbors(matrices_a, radius=2.5)

# Get the adjacency matrix as scipycsr_matrix
adjacency_m = mtree.get_csr_matrix()

Reference

LpqTree paper is in progress

Cite as:

@article{st2022fast,
  title={Fast Streamline Search: An Exact Technique for Diffusion MRI Tractography},
  author={St-Onge, Etienne and Garyfallidis, Eleftherios and Collins, D Louis},
  journal={Neuroinformatics},
  pages={1--12},
  year={2022},
  publisher={Springer}
}

@misc{blanco2014nanoflann,
  title        = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
  author       = {Blanco, Jose Luis and Rai, Pranjal Kumar},
  howpublished = {\url{https://github.com/jlblancoc/nanoflann}},
  year         = {2014}
}