Fast Algorithm for Anchor Graph Hashing

Summary: Tridiagonal Hashing accelerates anchor-graph hashing by deriving eigenvectors from a clustered tridiagonal similarity matrix and identifying query-nearest anchors after dimensionality reduction. It achieves orders-of-magnitude speedups while improving search accuracy. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12794
Venue: VLDB
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,738 | 19.47%
DOI: 10.14778/3447689.3447696

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yasuhiro Fujiwara (Nippon Telegraph and Telephone)
2. Sekitoshi Kanai (Keio University; Nippon Telegraph and Telephone)
3. Yasutoshi Ida (Nippon Telegraph and Telephone)
4. Atsutoshi Kumagai (Nippon Telegraph and Telephone)
5. Naonori Ueda (Nippon Telegraph and Telephone)

BibTeX Citation

@article{fujiwara_vldb21,
        title = {{Fast Algorithm for Anchor Graph Hashing}},
        author = {Fujiwara, Yasuhiro and Kanai, Sekitoshi and Ida, Yasutoshi and Kumagai, Atsutoshi and Ueda, Naonori},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {6},
        pages = {916--928},
        doi = {10.14778/3447689.3447696},
        url = {https://doi.org/10.14778/3447689.3447696},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934
1,430	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.0001080902
12,153	Scaling Manifold Ranking Based Image Retrieval	2015	VLDB	5.093636e-05
13,538	Fast Algorithm for the Lasso based L1-Graph Construction	2017	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,477	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
2	262	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB
3	10,364	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
4	2,673	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD
5	6,597	Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories	2010	SIGMOD
6	10,226	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD
7	3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
8	7,240	Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search	2018	SIGMOD
9	4,927	Neighbor-Sensitive Hashing	2016	VLDB
10	21	Similarity Search in High Dimensions via Hashing	1999	VLDB