The Florida AI Research Society · 2014 · 11 citations · 14 references
ComputingComputer ScienceData MiningInformation RetrievalMachine LearningDimension ReductionDimensionality ReductionNearest Neighbor SearchExact Nearest Neighbor SearchExecution Time AnalysisFilter EfficiencyHigh-dimensional Data ClusteringHigh-dimensional Nearest Neighbor SearchIndex StructuresK-nearest Neighbor SearchNearest Neighbor Retrieval
Efficient data indexing and exact k-nearest-neighbor (kNN) retrieval are still challenging tasks in high-dimensional spaces. This work highlights the difficulties of indexing in high-dimensional and tightly-clustered dataspaces by exploring several important tunable parameters for optimizing kNN query performance using the iDistance and iDStar algorithms. We experiment on real and synthetic datasets of varying size, cluster density, and dimensionality, and compare performance primarily through filter-and-refine efficiency and execution time. Results show great variability over parameter values and provide new insights and justifications in support of prior best-use practices. Local segmentation with iDStar consistently outperforms iDistance in any clustered space below 256 dimensions, setting a new benchmark for efficient and exact kNN retrieval in high-dimensional spaces. We propose several directions of future work to further increase performance in high-dimensional real-world settings.
14
Object recognition from local scale-invariant features
David Lowe · 1999 · 16.2K citations
Piotr Indyk, Rajeev Motwani · 1998 · 4.2K citations · Full text
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
H. V. Jagadish, Beng Chin Ooi, Kian‐Lee Tan et al. · ACM Transactions on Database Systems · 2005 · 596 citations