Dissertation > Excellent graduate degree dissertation topics show

Research on Locality Sensitive Hashing-Based Similarity Search

Author: LingKang
Tutor: WuGangShan
School: Nanjing University
Course: Computer Software and Theory
Keywords: Similarity Search LSH high-dimensional index k-means clustering
CLC: TP391.3
Type: Master's thesis
Year: 2012
Downloads: 310
Quote: 2
Read: Download Dissertation

Abstract


Similarity Search is a fundamental problem in Computer Science, and it has been widely used in many fields, including data mining, machine learning, signal processing, information retrieval and so on. Originally, people tried to solve Similarity Search problem by finding the Nearest Neighbor (NN) of the query object and proposed a lot of indexing methods based on Branch and Bound techniques, which have good performance in low-dimensional space. However, when it comes to high-dimensional space, these algorithms for NN search are proved to be no better than linear search, which is known as "curse of dimensionality". Some researchers proposed to improve the time efficiency by applying Approximate Nearest Neighbors (ANN) search in recent years, because ANN can act as good as the exact one in many applications.Locality Sensitive Hashing (LSH) is one of the most popular ANN algorithms, which not only has solid theoretical foundation but also can achieve good performance in high-dimensional space. However, there is a trade-off between search efficiency and memory usage. To achieve high search efficiency, LSH requires quite a lot of memory due to a large number of hash tables used. What’s more, for search time cost, LSH still has room for improvement. Although some researchers have done a lot of work to improve LSH, these improvements are all based on generic LSH scheme. However, generic LSH scheme has some limitations. Besides, these methods can not provide satisfying search efficiency in large data sets.To propose new algorithms which can solve Similarity Search problem better, the following work has been done in this paper:1. We analyze the idea for LSH to solve Similarity Search problem and point out the drawbacks of generic LSH scheme:it requires a large number of hash tables to achieve high search efficiency; the ability to filter points far away from query point is bad; it does not make full use of the properties of hash functions.2. We propose a new LSH-based algorithm called Frequency Based Locality Sensitive Hashing (FBLSH). FBLSH can make full use of the properties of hash functions based on p-stable distributions, and it can filter points far away from query point better with a small number of hash tables by counting the collisions. We prove the correctness of this algorithm and give a simple analysis of the computational complexity of it. Through experiments, we show that FBLSH outperforms LSH based on p-stable distributions.3. To deal with large-scale data efficiently, we propose a hybrid index structure called HKF tree which can reduce the search time cost in large data sets with small amounts of memory. HKF tree uses hierarchical k-means tree as its main structure and builds FBLSH index in each leaf node. We prove the correctness of HKF tree and analyze the computational complexity of it. Through experiments, we show that the performance of it in large data sets is better than hierarchical k-means tree, FBLSH and Posteriori Multi-Probe LSH.

Related Dissertations

  1. Research on Clustering Algorithm Based on Mutation Particle Swarm Optimization,TP18
  2. Research on Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization and Shuffled Frog Leaping Algorithm,TP18
  3. Research on Clustering Algorithm Based on Genetic Algorithm and Rough Set Theory,TP18
  4. Vehicle detection based on machine vision and vehicle distance measuring method,TP274
  5. Graph-based similarity search scientific literature key technology research,TP391.3
  6. Research and System Implementation of Image Retrieval Method Based on Fuzzy Clustering,TP391.41
  7. An Improvement of Cluster on Phylogenetic Profiling Method,TP311.13
  8. Improved Fuzzy C Means Clustering Algorithm and Its Application,O159
  9. Study on Similarity Analysis of Event Streams in Real-time Monitored Applications,TP311.13
  10. Research on the Platform for Clustering Graph Data and Its Implementation,TP311.13
  11. The Research on Object Matching Based on Major Color Spectrum and Spatial Distribution Entropy,TP391.41
  12. Research on Local Feature Based Image Copy Detection,TP391.41
  13. Research and Application of Similarity-based Mining of Financial Data Analysis System,TP311.13
  14. Research and Implementation of K- means clustering of remote sensing images and watershed segmentation algorithm,TP751
  15. Research of Intrusion Detection System Based on Fuzzy Comprehensive Evaluation,TP393.08
  16. Content-based video copy detection research,TP391.41
  17. Graphical Mining Based on Time-series,TP311.13
  18. Technique Research of Web Chinese Event Automatic Detection,TP393.09
  19. Research and Implementation of Web Service Registry and Similarity Searching,TP393.09
  20. Two-step Similarity Search of Time Series Based on DTW Distance,TP391.3
  21. Audio-only educational game virtual acoustic positioning,G434

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Retrieval machine
© 2012 www.DissertationTopic.Net  Mobile