Highlighting relevant snippet in document search

Problem Statement

Let X be a set of documents. Let Q be a set of query keywords.  A search for query Q ranks the document as per relevance and returns the most relevant document. A common practice is to highlight the relevant snippets in the document. A snippet is a part of the document that is most relevant to the query. Usually, a snippet will consists query keywords and other contextual words. For a given document D and query Q, design an algorithm to find and highlight the most relevant snippet.

Example

Document =>
Java provides built-in support for multithreaded programming. A multithreaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution. A multithreading is a specialized form of multitasking. Multitasking threads require less overhead than multitasking processes.
  
Query => "Multithreading Java"


Output=>
[Start-Highlight] Java provides built-in support for multithreaded programming. A multithreaded program[End-Highlight] contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution. A multithreading is a specialized form of multitasking. Multitasking threads require less overhead than multitasking processes.

Source code

Java source code with test cases. 

Instructions for executing the program

1. BRIEF DESCRIPTION

This program performs exact case sensitive matching of given query words to doc words.
It does not perform any stemming, spell check, synonym matching, and  has no support
for regular expressions and logical conditions in query.

Following characters are used as delimeters:
{' ','?','!',',','.',';',':','+','*','-','/','{', '}','[',']','(',')'}
Whenever, the program find a matching query keyword in the program, it
extracts a snippet of character length 150. Thus, a list of snippets are
generated. Snippets are ranked using a score based technique.
The highest snippet is returned as a result with the query keywords highlighted.
If there is no exact match in the page/document for any of the query keywords, NO
result is returned

2. CODE FILES IN THE APPLICATION
Constants.java
Controller.java
ErrorMessages.java
RenderOutput.java
SnippetMaker.java
SnippetRanker.java
Tokenizer.java

TestCases.java


3. ENVIRONMENT REQUIREMENT
Language: Java
Need JRE 1.4 or higher


4. COMPILATION
   a) create a folder snippetHighlight  (case sensitive)
   b) copy all the *.java files into it
   c) change to  snippetHighlight  directory
   d) type command
      javac Constants.java  ErrorMessages.java  Tokenizer.java SnippetMaker.java SnippetRanker.java  RenderOutput.java Controller.java TestCases.java


If the system fails to compile giving error that a class is not found than please fix the classpath as described in following article: http://download.oracle.com/javase/1.3/docs/tooldocs/win32/javac.html


5. EXECUTION WITH TEST CASES
   a) change to parent directory of snippetHighlight folder
   b) Type command
       java snippetHighlight.TestCases 0
       java snippetHighlight.TestCases 1
       java snippetHighlight.TestCases 2
       java snippetHighlight.TestCases 3
       These are four test cases to run the program.
     

6. PROVIDING OWN TEST CASES

   1) Look into file TestCases.java for details
 
   Each test method creates an instance of class  Controller
   Then it passes two strings.
   First string is doc string
   Second string is list of query keywords
 
   Here is the code snippet
 
   Controller  control = new Controller();
   control.snippetHighlight(pageStr, queryStr);    


7. NON SUPPORTED  FUNCTIONALITIES
a. This program does not provide functionality for spell checking on query or page.
  This can be included using edit distance check using dictionary and character sampling.
b. This program has no support for operators like OR, AND, REGEX, etc. for query.
c. This program does not perform stemming.
d. This program does not use synonyms of query word.
  This can be done using word graph like WORDNET or a Dictionary. This program provides framework in the code to plug this service.

Nearest Neighbor Search Using Data Projections and Hashing

1. Introduction

Random data projection with hash-based index structures has come to be the state-of-the-art method for both an efficient near neighbor search and a scalable cluster analysis for very high-dimensional data.  Data of very high dimensions pose serious computational challenge because of curse-of-dimensionality [Slide]. Random projections are also commonly used for dimension reduction.  An instance of random projection, Locality sensitive hashing, has widely attracted the attention of research community and is an active area of further research. This article gives resources for detailed reading on projection method.

2. Near Neighbor Search  

    a)  Types of queries

       1. Nearest neighbor queries

       2. Top-k nearest neighbors queries

       3. Range queries

       4. r-Near neighbor queries or ball-queries

       5. Approximate nearest neighbor queries (ANN )

       6. All nearest-neighbor queries  or Group queries or multi-object queries
       7. Reverse nearest neighbor queries
       8. List of other queries
       

   b) Hashing functions for different distance metrics

      1. Stable distributions for L1 Norm and L2 Norm (Euclidean distance)       

      2. Bit sampling for Hamming distance

      3. Min-Hash for Jaccard Similarity Coefficient

      4. Random Hyperplane for Cosine Similarity 

      5. Earth Mover's Distance

      6.

   c) References 

   
      2012

              1. SIMP: Accurate and Efficient Near Neighbor Search in High Dimensional Spaces ( Note: Method shown to yield very efficient search result on more than 100 million 128-dimensional vectors.  This is one of the largest dataset used for measuring the performance of a high-dimensional search algorithm). 

     
      2011
      2010
             1. Kernelized Locality-Sensitive Hashing for Scalable Image Search
             2. An Algorithm and Hardware Design for Very Fast Similarity Search in High Dimensional Space

      2009

            1. LSB Tree: Efficient and Accurate Nearest Neighbor and Closest Pair Search in High Dimensional Space

      2008

              1.  A Posteriori Multi-Probe Locality Sensitive Hashing 

              2.  Modeling LSH for Performance Tuning
              3.  Lecture Notes

      2007

               1. Multi-probe LSH: efficient indexing for high-dimensional similarity search ( Caveat : )

      2006

           1. Lower bounds on Locality Sensitive Hashing

           2.   Entropy based Nearest Neighbor Search in High Dimensions

           3.   Near-Optimal Hashing Algorithms for Near Neighbor Problem in High Dimensions

           4.   Nearest Neighbor Methods in Learning and Vision: Theory and Practice

      2005

           1. LSH Forest: Self-Tuning Indexes for Similarity Search

          

      2004
 
            1. Locality-sensitive hashing scheme based on p-stable distributions

     2003
     2002
            1. Similarity Estimation Techniques from Rounding Algorithms

     2001
            1. Random projection in dimensionality reduction: Applications to image and text data
            2. Database-friendly Random Projections
            3. Database-friendly random projections: Johnson-Lindenstrauss with binary coins

     2000
            1. Experiments with Random Projections

     1999
           1.  Similarity Search in High Dimensions via Hashing
           2.  A Small Approximately Min-Wise Independent Family of Hash Functions

     1998
           1.  Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality
           2.  Min-Wise Independent Permutations

     1997
            1. Two algorithms for nearest-neighbor search in high dimensions

     1984
            1.  W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space

  

  d) Implementations

          1.  Implementation of p-Stable LSH
          2.  LSHKit
          3.  SIMP
          4.  LSB

3. Image Search using Random Projections and LSH 

1. Random projection in dimensionality reduction: Applications to image and text data
2. Efficient Near-duplicate detection and sub-image retrieval
3. Near Duplicate Image Detection: min-Hash and tf-idf Weighting
4. Geometric min-Hashing: Finding a (Thick) Needle in a Haystack
5. Caltech Work

4. Scalable Cluster Analysis using Min-Hash

1.  Scalable technique for clustering the web
2.  Random Projection for High Dimensional Data Clustering: A Cluster Ensemble Approach
3.  Dimensionality Reduction by Random Mapping: Fast Similarity Computation for Clustering

Spelling Correction Methods

Following references give naive method for spell correction.  
References:
Introduction to Information Retrieval
Peter Norvig's Page