XNN Graph
Lecture notes in computer sciencePublished 1 January 2016
Pasi Fränti, Radu Mariescu-Istodor, Caiming Zhong
Citations22
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work introduces an alternative data structure called XNN, which has variable number of neighbors and guarantees connectivity of the graph, and demonstrates that the graph provides improvement over KNN in several applications including clustering, classification and data analysis.
Abstract
K-nearest neighbor graph (KNN) is a widely used tool in several pattern recognition applications but it has drawbacks. Firstly, the choice of k can have significant impact on the result because it has to be fixed beforehand, and it does not adapt to the local density of the neighborhood. Secondly, KNN does not guarantee connectivity of the graph. We introduce an alternative data structure called XNN, which has variable number of neighbors and guarantees connectivity. We demonstrate that the graph provides improvement over KNN in several applications including clustering, classification and data analysis.
Keywords
Computer SciencePhysics and Astronomy
IEEE Transactions on Information TheoryNearest neighbor pattern classification
16,134 Citations1967Thomas M. Cover, Peter E. Hart
The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
Systematic ZoologyA New Statistical Approach to Geographic Variation Analysis
1,291 Citations1969K. Ruben Gabriel, Robert R. Sokal
The authors discuss the problems of describing geographic variation data and develop statistical methods for categorizing sets of populations sampled from different localities and describe the approach of the simultaneous test procedures employed with these techniques.
Pattern RecognitionRobust path-based spectral clustering
573 Citations2007Hong Chang, Dit‐Yan Yeung
This paper develops a robust path-based spectral clustering method by defining a robust path-based similarity measure for spectral clustering under both unsupervised and semi-supervised settings and shows results that consistently outperforms other methods due to its higher robustness.
Geographical AnalysisProperties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane
373 Citations1980David W. Matula, Robert R. Sokal
Computer-Aided DesignDeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed
197 Citations1998Paolo Cignoni, C. Montani +1 more
The paper deals with Delaunay Triangulations (DT) in Ed space and proposes a new solution, based on an original interpretation of the well-known Divide and Conquer paradigm, which can be simply extended to triangulate point sets in any dimension.
IEEE Transactions on Knowledge and Data EngineeringSet Matching Measures for External Cluster Validity
187 Citations2016Mohammad Rezaei, Pasi Fränti
A new index called Pair Sets Index (PSI) is introduced based on the analytical comparisons of popular external indexes evaluated and compared when applied to clusterings of different data size, cluster size, and number of clusters.
Theoretical Computer ScienceOptimal construction of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-nearest-neighbor graphs for identifying noisy clusters
108 Citations2009Markus Maier, Matthias Hein +1 more
Using techniques from random geometric graph theory, this work proves bounds on the probability that clusters are identified successfully, both in a noise-free and in a noisy setting.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBuilding k edge-disjoint spanning trees of minimum total length for isometric data embedding
63 Citations2005Yang Li
An approach for constructing k-edge-connected neighborhood graphs is presented that works by finding k edge-disjoint spanning trees the sum of whose total lengths is a minimum and outperforms the nearest neighbor approach for geodesic distance estimation.
Computer-Aided DesignElliptic Gabriel graph for finding neighbors in a point set and its application to normal vector estimation
47 Citations2006Joon C. Park, Hayong Shin +1 more
This paper introduces a generalization of Gabriel graph, named elliptic Gabriel graph (EGG), which takes an elliptic influence region instead of the circular region in GG, and presents the analysis between the aspect ratio of the elliptic Influence region and the average valence of the resulting neighborhood.
Optical EngineeringOn the splitting method for vector quantization codebook generation
40 Citations1997Pasi Fränti
A new iterative splitting method is proposed, which is applicable to codebook generation without the GLA and outperforms both theGLA and the other existing splitting-based algorithms.
Pattern Recognition LettersAn adaptive neighbourhood construction algorithm based on density and connectivity
35 Citations2014Tülin İnkaya, Sinan Kayalıgil +1 more
A novel neighbourhood construction (NC) algorithm that extracts the density, connectivity and proximity relations among the data points in an adaptive manner, i.e. considering the local characteristics of points in the data set, is introduced.
Fast approximate similarity search based on degree-reduced neighborhood graphs
35 Citations2011Kazuo Aoyama, Kazumi Saito +2 more
The experimental results on a real data set verify the approximation scheme and high search performance of the proposed method and demonstrate that it is superior to E2LSH in terms of the expected search cost.
Incremental Delaunay Triangulation Construction for Clustering
1 Citations2014Octavio Razafindramanana, Frédéric Rayar +1 more
The proposed technique is based on a d-dimensional formulated Delaunay Triangulation (DT) construction algorithm and adapts it to the problem of cluster detection, and allows to label simplices as being inter - or intra cluster.