Product Split Trees
In this work, we introduce a new kind of spatial partition trees for efficient nearest-neighbor search. Our approach first identifies a set of useful data splitting directions, and then learns a codebook that can be used to encode such directions. We use the product-quantization idea in order to make the effective codebook large, the evaluation of scalar products between the query and the encoded splitting direction very fast, and the encoding itself compact. As a result, the proposed data srtucture (Product Split tree) achieves compact clustering of data points, while keeping the traversal very efficient. In the nearest-neighbor search experiments on high-dimensional data, product split trees achieved state-of-the-art performance, demonstrating better speed-accuracy tradeoff than other spatial partition trees.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringQuantizationSimilar Papers 제목 키워드 기반
Hoeffding adaptive splitting trees for data stream classification with concept drift and ensemble learning
Ensembles of decision trees are well-established methods for data stream classification. In ensemble learning, Hoeffding Trees are widely adopted as base learners, performing periodic split attempts according to the Hoef…
Ensemble LearningChange DetectionJacobian Aligned Random Forests
Axis-aligned decision trees are fast and stable but struggle on datasets with rotated or interaction-dependent decision boundaries, where informative splits require linear combinations of features rather than single-feat…
Node Splitting SVMs for Survival Trees Based on an L2-Regularized Dipole Splitting Criteria
This paper proposes a novel, node-splitting support vector machine (SVM) for creating survival trees. This approach is capable of non-linearly partitioning survival data which includes continuous, right-censored outcomes…
Learning Choice Model Trees for Feature-Based Multi-Product Pricing: Exact Optimization and Field Evidence
Feature-based multi-product pricing uses customer characteristics to identify demand heterogeneity and tailor prices across products. Choice model trees segment customers through interpretable feature rules and fit a dem…
When does Subagging Work?
We study the effectiveness of subagging, or subsample aggregating, on regression trees, a popular non-parametric method in machine learning. First, we give sufficient conditions for pointwise consistency of trees. We for…