英语论文网

留学生硕士论文 英国论文 日语论文 澳洲论文 Turnitin剽窃检测 英语论文发表 留学中国 欧美文学特区 论文寄售中心 论文翻译中心 我要定制

Bussiness ManagementMBAstrategyHuman ResourceMarketingHospitalityE-commerceInternational Tradingproject managementmedia managementLogisticsFinanceAccountingadvertisingLawBusiness LawEducationEconomicsBusiness Reportbusiness planresearch proposal

英语论文题目英语教学英语论文商务英语英语论文格式商务英语翻译广告英语商务英语商务英语教学英语翻译论文英美文学英语语言学文化交流中西方文化差异英语论文范文英语论文开题报告初中英语教学英语论文文献综述英语论文参考文献

ResumeRecommendation LetterMotivation LetterPSapplication letterMBA essayBusiness Letteradmission letter Offer letter

澳大利亚论文英国论文加拿大论文芬兰论文瑞典论文澳洲论文新西兰论文法国论文香港论文挪威论文美国论文泰国论文马来西亚论文台湾论文新加坡论文荷兰论文南非论文西班牙论文爱尔兰论文

小学英语教学初中英语教学英语语法高中英语教学大学英语教学听力口语英语阅读英语词汇学英语素质教育英语教育毕业英语教学法

英语论文开题报告英语毕业论文写作指导英语论文写作笔记handbook英语论文提纲英语论文参考文献英语论文文献综述Research Proposal代写留学论文代写留学作业代写Essay论文英语摘要英语论文任务书英语论文格式专业名词turnitin抄袭检查

temcet听力雅思考试托福考试GMATGRE职称英语理工卫生职称英语综合职称英语职称英语

经贸英语论文题目旅游英语论文题目大学英语论文题目中学英语论文题目小学英语论文题目英语文学论文题目英语教学论文题目英语语言学论文题目委婉语论文题目商务英语论文题目最新英语论文题目英语翻译论文题目英语跨文化论文题目

日本文学日本语言学商务日语日本历史日本经济怎样写日语论文日语论文写作格式日语教学日本社会文化日语开题报告日语论文选题

职称英语理工完形填空历年试题模拟试题补全短文概括大意词汇指导阅读理解例题习题卫生职称英语词汇指导完形填空概括大意历年试题阅读理解补全短文模拟试题例题习题综合职称英语完形填空历年试题模拟试题例题习题词汇指导阅读理解补全短文概括大意

商务英语翻译论文广告英语商务英语商务英语教学

无忧论文网

联系方式

Audio Fingerprinting:Nearest Neighbor Search in High Dimensional [2]

论文作者:留学生论文论文属性:案例分析 Case Study登出时间:2011-02-22编辑:anterran点击率:11581

论文字数:4125论文编号:org201102220946588380语种:英语 English地区:美国价格:免费论文

关键词:Audio FingerprintingNearest Neighbor Searchin High Dimensional

h value. Although each subvector
is non-overlapping, the concatenated fingerprints have
substantial overlap. Assuming that the duration of the average
song is 3 minutes, then the number of fingerprints per song is
3  60  256=5 = 9216  10; 000.
Given this 8192-dimensional representation, the focus of our
work has been to develop an efficient search algorithm. This
search can be characterized as a nearest neighbor search in a
very high dimensional space. Of course, this assumes that the
nearest fingerprint in the database to the query is the correct
match. However, under some distortions, this assumption may
not be valid. Interestingly, it is less important to correctly
match the query to its corresponding fingerprint as it is to
match the fingerprint to its corresponding song. Since a song is
composed of many fingerprints, incorrectly matching a query
to a fingerprint does not necessarily lead to a song recognition
error. This issue is discussed in more detail in the experimental
evaluation of Section III.
High dimensional nearest neighbor search is a very well
studied problem. Proposed solutions generally create a tree
structure, the leaf nodes representing the known datum (fingerprints)
and searching becomes a traversal of the tree. Specific
algorithms differ in how this tree is constructed and traversed.
Two related data structures, kd-trees and vantage point or
vp-trees, have been extensively studied. However, both data
structures succumb to the curse of dimensionality, that is, as
the dimension of the datum increases, an increasing percentage
of the tree must be searched in order to locate the nearest
neighbor to a query.
1
Recent work [2], [3], [4], [5] appears to acknowledge
the fact that a perfect search that guarantees to find the
nearest neighbor in a high dimensional space is not feasible.
However, the curse of dimensionality can be removed if the
search is approximate. For example, Yianilos [5] describes
an algorithm that, with probability, p, will find a neighbor
within a Euclidean distance r of the query when the datum
are uniformly distributed within an n-dimensional hypercube.
Unfortunately, this work has not been extended to the binary
case and Hamming rather than Euclidean distance.
In this paper, we develop an approximate search algorithm
for high dimensional binary vectors. Section II first describes
the algorithm. Section III then presents experimental results on
a database of 1000 songs and 12,217,111 fingerprints. Finally,
Section IV summarizes our results and discusses possible
avenues of future work.
II. ALGORITHM
In the following subsections, we describe an approximate
search algorithm for binary vectors in a high dimension space.
Given the set of known fingerprints, we first construct a 256-
ary tree. Each 8192-bit fingerprint is represented as 1024 8-bit
bytes. The value of each consecutive byte in the fingerprint
determines which of the 256 possible children to descend. A
path from the root node to a leaf defines a fingerprint.
As the depth of the tree increases, in is common to find
nodes with only a single child. This is because the number
of actual fingerprints is very much less than the total possible
number. For efficiency purposes, we compress suchsequences
of nodes with only one child into a single node that represents
multip论文英语论文网提供整理,提供论文代写英语论文代写代写论文代写英语论文代写留学生论文代写英文论文留学生论文代写相关核心关键词搜索。
英国英国 澳大利亚澳大利亚 美国美国 加拿大加拿大 新西兰新西兰 新加坡新加坡 香港香港 日本日本 韩国韩国 法国法国 德国德国 爱尔兰爱尔兰 瑞士瑞士 荷兰荷兰 俄罗斯俄罗斯 西班牙西班牙 马来西亚马来西亚 南非南非