Pigeonring: A Principle for Faster Thresholded Similarity Search
Summary: Pigeonring strengthens pigeonhole-based filtering for thresholded similarity search by constraining item counts across multiple ring-organized partitions. A universal framework and minor algorithmic modifications deliver faster candidate generation and superior performance on real datasets. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Jianbin Qin (The University of Edinburgh)
- 2. Chuan Xiao (Nagoya University)
BibTeX Citation
@article{qin_vldb19,
title = {{Pigeonring: A Principle for Faster Thresholded Similarity Search}},
author = {Qin, Jianbin and Xiao, Chuan},
journal = {PVLDB},
series = {{VLDB} '19},
volume = {12},
number = {1},
pages = {28--44},
doi = {10.14778/3275536.3275539},
url = {https://doi.org/10.14778/3275536.3275539},
year = {2019}
}Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,310 | Similarity Query Processing for High-Dimensional Data | 2020 | VLDB | 7.5363562e-05 |
| 4,617 | Learned Cardinality Estimation for Similarity Queries | 2021 | SIGMOD | 6.604437e-05 |
| 5,011 | Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach | 2020 | SIGMOD | 6.4020848e-05 |
| 7,676 | Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts | 2021 | SIGMOD | 5.5686107e-05 |
| 9,702 | Towards a Unified Framework for String Similarity Joins | 2019 | VLDB | 5.2351259e-05 |
| 10,951 | Extensible and Robust Evaluation of Similarity Queries | 2025 | VLDB | 5.093636e-05 |
| 11,447 | A Two-Level Signature Scheme for Stable Set Similarity Joins | 2023 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 52 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,085 | Local Filtering: Improving the Performance of Approximate Queries on String Collections | 2015 | SIGMOD | 5.1559617e-05 |
| 10,086 | Efficient and Effective KNN Sequence Search with Approximate n-grams | 2014 | VLDB | 5.1559617e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,259 | Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search | 2025 | SIGMOD |
| 2 | 975 | Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search | 2012 | SIGMOD |
| 3 | 3,866 | Fast Parallel Similarity Search in Multimedia Databases | 1997 | SIGMOD |
| 4 | 10,638 | A Theoretical Framework for Distribution-Aware Dataset Search | 2025 | PODS |
| 5 | 6,906 | Efficient Similarity Join and Search on Multi-Attribute Data | 2015 | SIGMOD |
| 6 | 9,471 | Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement | 2024 | VLDB |
| 7 | 991 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB |
| 8 | 3,858 | A General and Efficient Querying Method for Learning to Hash | 2018 | SIGMOD |
| 9 | 7,942 | Efficient and Tunable Similar Set Retrieval | 2001 | SIGMOD |
| 10 | 8,791 | HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle | 2022 | SIGMOD |