惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

雷峰网
雷峰网
博客园 - 聂微东
酷 壳 – CoolShell
酷 壳 – CoolShell
宝玉的分享
宝玉的分享
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
罗磊的独立博客
Hugging Face - Blog
Hugging Face - Blog
T
Tailwind CSS Blog
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
IT之家
IT之家
博客园_首页
博客园 - 三生石上(FineUI控件)
博客园 - 叶小钗
Apple Machine Learning Research
Apple Machine Learning Research
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
量子位
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
人人都是产品经理
人人都是产品经理
美团技术团队
小众软件
小众软件
Jina AI
Jina AI
S
SegmentFault 最新的问题
博客园 - Franky
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Pigeonring: A Principle for Faster Thresholded Similarity...
Jianbin Qin, Chuan Xiao · 2018-04-05 · via cs.DS updates on arXiv.org

The pigeonhole principle states that if $n$ items are contained in $m$ boxes, then at least one box has no more than $n / m$ items. It is utilized to solve many data management problems, especially for thresholded similarity searches. Despite many pigeonhole principle-based solutions proposed in the last few decades, the condition stated by the principle is weak. It only constrains the number of items in a single box. By organizing the boxes in a ring, we propose a new principle, called the pigeonring principle, which constrains the number of items in multiple boxes and yields stronger conditions. To utilize the new principle, we focus on problems defined in the form of identifying data objects whose similarities or distances to the query is constrained by a threshold. Many solutions to these problems utilize the pigeonhole principle to find candidates that satisfy a filtering condition. By the new principle, stronger filtering conditions can be established. We show that the pigeonhole principle is a special case of the new principle. This suggests that all the pigeonhole principle-based solutions are possible to be accelerated by the new principle. A universal filtering framework is introduced to encompass the solutions to these problems based on the new principle. Besides, we discuss how to quickly find candidates specified by the new principle. The implementation requires only minor modifications on top of existing pigeonhole principle-based algorithms. Experimental results on real datasets demonstrate the applicability of the new principle as well as the superior performance of the algorithms based on the new principle.