Dimensionality Reduction for Efficient Similarity Search in High Dimensional Spaces

高维空间中高效相似性搜索的降维

• 批准号: EP/E037402/1
• 负责人: Dawei Song
• 金额: $ 2.1万
• 依托单位: The Open University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2007
• 资助国家: 英国
• 起止时间: 2007 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FE037402%2F1
• 关键词: Dimensionality; Reduction; Efficient; Similarity; Search

This overseas travel grant proposal requests EPSRC's support for a two-month visit (January-February 2007) to my research collaborators Prof. Xiaofang Zhou and Dr. Heng Tao Shen at School of Information Technology and Electrical Engineering (ITEE), the University of Queensland, and Prof. Peter Bruza at School of Information Systems, Queensland University of Technology, both in Brisbane, Australia, to conduct joint research in dimensionality reduction for efficient similarity search in high dimensional spaces. There has been a pressing need of dealing with large scale multimedia and complex data to find required information efficiently and effectively. Data objects are represented by automatically extracted features (e.g., colour, texture, and geometry properties for images) as feature vectors, which are points in high dimensional space. Similarity query processing is to find the data objects similar to a query, i.e., the nearest K neighboring (K-NN) points of the query object in the high dimensional space, typically by measuring distances between the points. The similarity search is a common problem fundamental to a wide range of applications, such as multimedia search, molecular biology, digital libraries, medical imaging, video surveillance, and so on. Major challenges in this area are rooted on the curse of dimensionality , which is still an open problem remaining largely unsolved. The K-NN problem in a high dimensional space becomes meaningless with the increase of the number of dimensions, as the difference between the distances for a point in the space to its nearest neighbor and its farthest neighbor approaches to zero when the number of dimensions approaching infinity. Dimensionality reduction aims to reduce the impact of curse of dimensionality by exploring effective dimensionality reduction techniques. In the literature, a number of dimensionality reduction methods have been investigated. However, the suitability of an existing algorithm will largely depend on and have to be adapted to the type of data, similarity measure and query processing strategy. In this research, we will conduct a systematic investigation into how to adapt state-of-the-art linear and non-linear dimensionality reduction techniques to these aspects. We aim at significantly improving performance of similarity query processing. We have already done extensive grounding work related to this research. Some existing dimensionality reduction methods have been tested on large scale protein structure data. In addition, initial work in video sequence search is on-going. We have now reached the hard core of the research. A large amount of multimedia database aspects (such as indexing, query processing, etc.) that I am currently unfamiliar with, will get involved. As a consequence, intensive face-to-face interactions with my collaborators, who are top multimedia database researchers, are essential. It is important to meet and physically work together with them. This will help the research carried out at the Knowledge Media Institute of the Open University.This overseas travel grant will be highly cost-effective. The concrete outcomes will include papers, initial experimental results as proof-of-concept for an EPSRC proposal I am preparing, and a following-on regular student exchange program for my PhD students to visit the multimedia database group of the University of Queensland (fully supported by the host university). It will generate significant benefits to the UK in terms of knowledge transfer, training of high-quality personnel, and international collaboration. It will strengthen my existing link with these internationally recognized researchers. Through the joint research, I will learn advanced technologies on multimedia databases, which will broaden my vision and expertise as an information retrieval researcher. This will further enhance my department's and to my own research profile.

这项海外旅行拨款建议请EPSRC支持我为期两个月(2007年1月至2月)的访问，访问我的研究合作者，昆士兰大学信息技术与电气工程学院(ITEE)的周晓芳教授和衡涛博士，以及昆士兰科技大学信息系统学院的Peter Bruza教授，他们都位于澳大利亚布里斯班，在降维方面进行联合研究，以在高维空间中进行高效的相似性搜索。人们迫切需要处理大规模的多媒体和复杂的数据，以便高效、有效地找到所需的信息。数据对象由作为特征向量的自动提取的特征(例如，图像的颜色、纹理和几何属性)表示，特征向量是高维空间中的点。相似性查询处理通常是通过测量点之间的距离来找到与查询相似的数据对象，即查询对象在高维空间中最近的K个相邻(K-NN)点。相似性检索是多媒体检索、分子生物学、数字图书馆、医学成像、视频监控等广泛应用的基本问题。这一领域的主要挑战植根于维度的诅咒，这仍然是一个在很大程度上仍未解决的悬而未决的问题。高维空间中的K-NN问题随着维数的增加而变得没有意义，因为当维数接近无穷大时，空间中某一点到其最近邻点和最远邻点的距离之差趋于零。降维旨在通过探索有效的降维技术来降低降维灾难的影响。在文献中，已经研究了许多降维方法。然而，现有算法的适用性将在很大程度上取决于并必须适应数据类型、相似性度量和查询处理策略。在这项研究中，我们将对如何将最新的线性和非线性降维技术应用于这些方面进行系统的研究。我们的目标是显著提高相似查询处理的性能。我们已经做了与这项研究相关的广泛的基础工作。已有的一些降维方法已经在大规模蛋白质结构数据上进行了测试。此外，视频序列搜索的初步工作正在进行中。我们现在已经达到了研究的核心。大量的多媒体数据库方面(如索引、查询处理等)我现在不熟悉的，将会参与其中。因此，与我的合作者进行密集的面对面互动是必不可少的，他们都是顶尖的多媒体数据库研究人员。与他们见面并与他们一起实际工作是很重要的。这将有助于公开大学知识媒体研究所进行的研究。这笔海外旅行补助金将具有极高的成本效益。具体成果将包括论文、初步实验结果，作为我正在准备的EPSRC提案的概念验证，以及我的博士生访问昆士兰大学多媒体数据库小组的后续定期学生交换计划(由主办大学完全支持)。它将在知识转移、高素质人才培训和国际合作方面为英国带来重大好处。这将加强我与这些国际公认的研究人员的现有联系。通过联合研究，我将学习多媒体数据库的先进技术，这将开阔我作为一名信息检索研究员的视野和专业知识。这将进一步提高我的部门和我自己的研究形象。

项目成果

Towards a belief-revision-based adaptive and context-sensitive information retrieval system

• DOI: 10.1145/1344411.1344414
• 发表时间: 2008-03
• 期刊: ACM Trans. Inf. Syst.
• 作者: Raymond Y. K. Lau;P. Bruza;D. Song

Dimensionality reduction for dimension-specific search

特定维度搜索的降维

• DOI: 10.1145/1277741.1277940
• 发表时间: 2007
• 作者: Huang Z

Database Systems for Advanced Applications - 14th International Conference, DASFAA 2009, Brisbane, Australia, April 21-23, 2009. Proceedings

高级应用数据库系统 - 第 14 届国际会议，DASFAA 2009，澳大利亚布里斯班，2009 年 4 月 21-23 日。会议记录

• DOI: 10.1007/978-3-642-00887-0_60
• 发表时间: 2009
• 作者: Huang Z