Fast algorithm for anchor graph hashing
| Autor: | Sekitoshi Kanai, Naonori Ueda, Yasutoshi Ida, Yasuhiro Fujiwara, Atsutoshi Kumagai |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Theoretical computer science
Computer science Hash function General Engineering 02 engineering and technology Cancer detection Fast algorithm Matrix (mathematics) 020204 information systems Web page 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing Eigenvalues and eigenvectors |
| Zdroj: | Proceedings of the VLDB Endowment. 14:916-928 |
| ISSN: | 2150-8097 |
| Popis: | Anchor graph hashing is used in many applications such as cancer detection, web page classification, and drug discovery. It computes the hash codes from the eigenvectors of the matrix representing the similarities between data points and anchor points; anchors refer to the points representing the data distribution. In performing an approximate nearest neighbor search, the hash codes of a query data point are determined by identifying its closest anchor points. Anchor graph hashing, however, incurs high computation cost since (1) the computation cost of obtaining the eigenvectors is quadratic to the number of anchor points, and (2) the similarities of the query data point to all the anchor points must be computed. Our proposal, Tridiagonal hashing , increases the efficiency of anchor graph hashing because of its two advances: (1) we apply a graph clustering algorithm to compute the eigenvectors from the tridiagonal matrix obtained from the similarities between data points and anchor points, and (2) we detect anchor points closest to the query data point by using a dimensionality reduction approach. Experiments show that our approach is several orders of magnitude faster than the previous approaches. Besides, it yields high search accuracy than the original anchor graph hashing approach. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|