\documentclass{article}
\usepackage{graphicx}
\usepackage[lmargin=3.5cm, rmargin=3.5cm,tmargin=3.30cm, bmargin=3.30cm]{geometry}
\pagenumbering{arabic}


\title{Query by Analogical Example\\Relational Search Using Web Search Engine Indices }
\author{Lohit Jain$^{1}$\\Advisor: Dr. Amitabha Mukerjee$^{1}$\\\{lohit,amit\}@iitk.ac.in\\
\scriptsize {$^{1}$ \emph{Dept. Of Computer Science and Engineering}}}
\date{\today}

\begin{document}
\maketitle

\section*{1. Introduction}

Relational Search is an effective way to obtain information in an unknown field for users. 
For example, if an \emph{Apple} user searches for \emph{Microsoft} products, similar \emph{Apple} products are important clues for the search.
\\As most proposed relational search requires a huge text corpus to be downloaded from the Web, the results are not upto 
date and the corpus has high construction cost.
I plan to implement methods for relational search by using Web search indices which ensures effeciency in terms of construction cost and relevance.

\section*{2. The Problem}
The problem is to find results based on relation between two named entities and discovering another named entity having similar relation
 to a third given entity.\\
For example, if the a person inputs \emph{chocolate} and \emph{cacao} as the first relation and gives \emph{Wine} as the third entity, the system should give \emph{grape} as result.\\
Another example, \emph{Youtube} is owned by \emph{Google} and \emph{Oracle} by \emph{Sun Microsystems}. If we input \emph{Youtube}, \emph{Google} and \emph{Oracle} we should get output \emph{Sun Microsystems}.\\


\section*{3. Proposed Solution}
My proposed solution involves two steps:
\begin{itemize}
\item[\bf Step 1:] Finding Relation Extractor.   
\item[\bf Step 2:] Extracting and ranking terms based on Relational Similarity.\\
\end{itemize}
I propose to implement the relation extractor based on \emph{Term Co-occurrence} and if possible on \emph{Lexico-Syntactic Patterns}.\\
The term co-occurrence method finds terms in search queries which represent the relation between the search querie's entities. For example for relation between \emph{Australia} and 
\emph{Parliament} may get term for its location, \emph{Canberra}.\\ 
The ranking will be based on method used by Kato and Ohshima in \cite{kato}. The ranking will generate ranked outputs for each input.\\
\\ \textbf {Formalising the problem:}\\
Let (\emph{a}, \emph{b}, \emph{c}) be the given named entities, the proposed system will involve querying the Web for extracting relation from \emph{a}, \emph{b} 
and finding a  \emph{d} which satisfies the same relation with \emph{c}.\\
The step 1 is finding relation between \emph{a} and \emph{b}.\\
The step 2 is generating \emph{d}'s having similar relation to \emph{c} and ranking them according to relevance.



\section*{4. Evaluation}

The evaluation will be based on the test corpus of Kato and Ohshime in \cite{kato}\\
For each pairs in test corpus, the input will be \emph{a}, \emph{b}, \emph{c} and expected output \emph{d}. The topmost suggestions which matches with the 
expected output will be an evaluation technique.
 
\section*{5. Ethics and Resourcing}
The proposed solution requires Web as a resource at computation stage and the test set used by Kato and Ohshime in \cite{kato} at the evaluation stage.\\ 
There are no additional data sets or corpus required.


\begin{thebibliography}{14}

\bibitem{kato}
Kato, Makoto P., et al. "Query by analogical example: relational search using web search engine indices." Proceedings of the 18th ACM conference on Information and knowledge management. ACM, 2009.
\bibitem{yao}
Yao, Limin, et al. "Structured relation discovery using generative models." Proceedings of the Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2011.
\end{thebibliography}

\end{document}