On Low Dimensional Random Projections and Similarity Search

Add to your list(s) Download to your calendar using vCal

• Lu, Yu-En (Eric) (Univeristy of Cambridge)
• Friday 10 October 2008, 14:00-15:00
• SS03, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Eiko Yoneki.

Random projection (RP) is a common technique for dimensionality reduction under $L_2$ norm for which many significant space embedding results have been demonstrated. However, many similarity search applications often require very low dimension embeddings in order to reduce overhead and boost performance. For example, a good 1D embedding can enable complex queries over standard distributed hash tables.

Inspired by the use of symmetric probability distributions in previous work, we propose a novel RP algorithm, Beta Random Projection, and give its probabilistic analyses based on Beta and Gaussian approximations. We evaluate the algorithm in terms of standard similarity metrics with other RP algorithms as well as the singular value decomposition (SVD). Our experimental results show that BRP preserves both similarity metrics well and, under various dataset types including random point sets, text (TREC5) and images, provides sharper and consistent performance.

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• SS03, Computer Laboratory, William Gates Builiding
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.