Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study
We focus on low-dimensional non-metric search, where tree-based approaches permit efficient and accurate retrieval while having short indexing time. These methods rely on space partitioning and require a pruning rule to avoid visiting unpromising parts. We consider two known data-driven approaches to extend these rules to non-metric spaces: TriGen and a piece-wise linear approximation of the pruning rule. We propose and evaluate two adaptations of TriGen to non-symmetric similarities (TriGen does not support non-symmetric distances). We also evaluate a hybrid of TriGen and the piece-wise linear approximation pruning. We find that this hybrid approach is often more effective than either of the pruning rules. We make our software publicly available.
Code (0)
등록된 구현이 없습니다.
Tasks
RetrievalMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Combined Pruning for Nested Cross-Validation to Accelerate Automated Hyperparameter Optimization for Embedded Feature Selection in High-Dimensional Data with Very Small Sample Sizes
Background: Embedded feature selection in high-dimensional data with very small sample sizes requires optimized hyperparameters for the model building process. For this hyperparameter optimization, nested cross-validatio…
feature selectionHyperparameter OptimizationGeometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series
We consider the problem of detecting multiple changes in multiple independent time series. The search for the best segmentation can be expressed as a minimization problem over a given cost function. We focus on dynamic p…
Change Point DetectionComputational EfficiencyTime SeriesApproximate learning of high dimensional Bayesian network structures via pruning of Candidate Parent Sets
Score-based algorithms that learn Bayesian Network (BN) structures provide solutions ranging from different levels of approximate learning to exact learning. Approximate solutions exist because exact learning is generall…
Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms
The reliable fraction of information is an attractive score for quantifying (functional) dependencies in high-dimensional data. In this paper, we systematically explore the algorithmic implications of using this measure …
Heuristic SearchKoopman Subspace Pruning in Reproducing Kernel Hilbert Spaces via Principal Vectors
Data-driven approximations of the infinite-dimensional Koopman operator rely on finite-dimensional projections, where the predictive accuracy of the resulting models hinges heavily on the invariance of the chosen subspac…