Möbius Transformation for Fast Inner Product Search on Graph

2019-12-01 · NeurIPS 2019 12 · Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, Ping Li

We present a fast search on graph algorithm for Maximum Inner Product Search (MIPS). This optimization problem is challenging since traditional Approximate Nearest Neighbor (ANN) search methods may not perform efficiently in the non-metric similarity measure. Our proposed method is based on the property that Möbius transformation introduces an isomorphism between a subgraph of l^2-Delaunay graph and Delaunay graph for inner product. Under this observation, we propose a simple but novel graph indexing and searching algorithm to find the optimal solution with the largest inner product with the query. Experiments show our approach leads to significant improvements compared to existing methods.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Computational Aspects of the Mobius Transform

2013-03-27 · Robert Kennes, Philippe Smets

In this paper we associate with every (directed) graph G a transformation called the Mobius transformation of the graph G. The Mobius transformation of the graph (O) is of major significance for Dempster-Shafer theory of…

Conformal Surface Alignment With Optimal Mobius Search

2016-06-01 · CVPR 2016 6 · Huu Le, Tat-Jun Chin, David Suter

Deformations of surfaces with the same intrinsic shape can often be described accurately by a conformal model. A major focus of computational conformal geometry is the estimation of the conformal mapping that aligns a gi…

Möbius Convolutions for Spherical CNNs

2022-01-28 · Thomas W. Mitchel, Noam Aigerman, Vladimir G. Kim, Michael Kazhdan

M\"obius transformations play an important role in both geometry and spherical image processing - they are the group of conformal automorphisms of 2D surfaces and the spherical equivalent of homographies. Here we present…

Descriptive Image Segmentation Semantic Segmentation

Differential and integral invariants under Mobius transformation

2018-08-30 · He Zhang, Hanlin Mo, You Hao, Qi Li 외

One of the most challenging problems in the domain of 2-D image or 3-D shape is to handle the non-rigid deformation. From the perspective of transformation groups, the conformal transformation is a key part of the diffeo…

Data augmentation with Mobius transformations

2020-02-07 · Sharon Zhou, Jiequan Zhang, Hang Jiang, Torbjorn Lundh 외

Data augmentation has led to substantial improvements in the performance and generalization of deep models, and remain a highly adaptable method to evolving model architectures and varying amounts of data---in particular…

Data Augmentation Translation