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!
|
| _version_ | 1841539512784650240 |
|---|---|
| author | Xin-pan YUAN Can-fei WANG Jun LONG Cheng-yuan ZHANG Jun-feng MAN |
| author_facet | Xin-pan YUAN Can-fei WANG Jun LONG Cheng-yuan ZHANG Jun-feng MAN |
| author_sort | Xin-pan YUAN |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7419f48acf8d452bb56dcba52252a339 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2017-10-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-7419f48acf8d452bb56dcba52252a3392025-01-14T07:13:43ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2017-10-013812713459714717FGBC-iDistance:fine-grained bit-code filter based high-dimensional indexXin-pan YUANCan-fei WANGJun LONGCheng-yuan ZHANGJun-feng MANIn 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.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017245/distance computationmore fine-grainediDistancerange query |
| spellingShingle | Xin-pan YUAN Can-fei WANG Jun LONG Cheng-yuan ZHANG Jun-feng MAN FGBC-iDistance:fine-grained bit-code filter based high-dimensional index Tongxin xuebao distance computation more fine-grained iDistance range query |
| title | FGBC-iDistance:fine-grained bit-code filter based high-dimensional index |
| title_full | FGBC-iDistance:fine-grained bit-code filter based high-dimensional index |
| title_fullStr | FGBC-iDistance:fine-grained bit-code filter based high-dimensional index |
| title_full_unstemmed | FGBC-iDistance:fine-grained bit-code filter based high-dimensional index |
| title_short | FGBC-iDistance:fine-grained bit-code filter based high-dimensional index |
| title_sort | fgbc idistance fine grained bit code filter based high dimensional index |
| topic | distance computation more fine-grained iDistance range query |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017245/ |
| work_keys_str_mv | AT xinpanyuan fgbcidistancefinegrainedbitcodefilterbasedhighdimensionalindex AT canfeiwang fgbcidistancefinegrainedbitcodefilterbasedhighdimensionalindex AT junlong fgbcidistancefinegrainedbitcodefilterbasedhighdimensionalindex AT chengyuanzhang fgbcidistancefinegrainedbitcodefilterbasedhighdimensionalindex AT junfengman fgbcidistancefinegrainedbitcodefilterbasedhighdimensionalindex |