FGBC-iDistance:fine-grained bit-code filter based high-dimensional index
In the high-dimensional vector retrieval,distance computation is a very time-consuming operation,the current research trend is to reduce the distance computation using divide and conquer algorithm.iDistance algorithm divides the vector space into subspace of clustering by pivot,BC-iDistance algorith...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2017-10-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017245/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In the high-dimensional vector retrieval,distance computation is a very time-consuming operation,the current research trend is to reduce the distance computation using divide and conquer algorithm.iDistance algorithm divides the vector space into subspace of clustering by pivot,BC-iDistance algorithm divides the subspace into 2 partitions in each dimension.A more fine-grained partition algorithm and index structure was proposed,each part corresponded with a unique FGBC code (fine-grained bit code),which realized the candidate sets filtered more precisely.The distance computation times of FGBC-iDistance can be reduced to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML"> <mfrac> <mn>1</mn> <mrow> <msup> <mn>2</mn> <mrow> <mn>2</mn><mi>d</mi></mrow> </msup> </mrow> </mfrac> </math></inline-formula> of iDistance.The distance computation frequency comparison:FGBC-iDistance≤BC-iDistance≤iDistance.The experiment results show that when the scope radius of the range query is 0.08,FGBC-iDistance distance computation times is about 20,000,which is far less than other algorithms,the running time is also reduced. |
|---|---|
| ISSN: | 1000-436X |