%%class \documentclass{iaesarticle2} %%required package. add for your convenient, but do not remove the initial \usepackage{amsmath, amsfonts, amssymb, float, fancyhdr} \usepackage[figuresright]{rotating} \usepackage{authblk, graphicx, indentfirst, lastpage, lipsum} \setlength{\affilsep}{0cm} \renewcommand\Authfont{\normalsize} \renewcommand\Affilfont{\normalfont\small} \usepackage{subfig, caption, epstopdf} \usepackage[left=2.5cm, right=2cm, top=1.5cm, bottom=2cm, includehead, includefoot]{geometry} \usepackage{caption} \captionsetup{labelsep=period} \usepackage{titlesec} \titleformat{\section} {\normalfont\normalsize\bfseries\uppercase}{\thesection}{1em}{} \titlespacing*{\section}{0cm}{0.7cm}{0cm} %Uma \usepackage{tabularx} \newcolumntype{b}{X} \newcolumntype{s}{>{\hsize=.5\hsize}X} \usepackage[ruled]{algorithm2e} \renewcommand{\algorithmcfname}{ALGORITHM} \newcommand*\DNA{\textsc{dna}~} \DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax} \newcommand*{\argminl}{\argmin\limits} \newcommand*{\argmaxl}{\argmax\limits} \usepackage{mathtools} \newcommand\Myperm[2][n]{\prescript{#1\mkern-2.5mu}{}P_{#2}} \newcommand\Mycomb[2][n]{\prescript{#1\mkern-0.5mu}{}C_{#2}} \usepackage{graphicx}% Include figure files \usepackage{caption} %\usepackage{color}% Include colors for document elements \usepackage{dcolumn}% Align table columns on decimal point \usepackage{bm}% bold math \usepackage[numbers,super,comma,sort&compress]{natbib} \usepackage{float} %uma declaration over %%leave copyright info to the editor \CopyrightLine[Copyright]{201x}{Institute of Advanced Engineering and Science.} %%author \author[*]{\bfseries Uma Gajendragadkar} \author[**]{\bfseries Sarang Joshi} %%author's affiliation \affil[*]{COEP, Savitribai Phule Pune University, Pune, Maharshtra, India} \affil[**]{PICT, Savitribai Phule Pune University, Pune, Maharshtra, India} %%title and shortitle (for footer) \title{Context sensitive Search String Composition Algorithm using User Intention to handle Ambiguous Keywords} \shorttitle{Title of manuscript is short and clear, implies research results (First Author)} %%starting \begin{document} %%indentation. do not change \setlength{\parindent}{1.27cm} %%header and footer setting. do not change \pagestyle{fancy} \fancyhfoffset{0cm} %%journal info \journalname{International Journal of Electrical and Computer Engineering (IJECE)} \journalshortname{IJECE} \journalhomepage{http://iaesjournal.com/online/index.php/IJECE} \vol{x} \no{x} \months{October} \years{2016} \issn{2088-8708} %%build title \maketitle %%border setting. do not change \hrule \vspace{.1em} \hrule \vspace{.5em} \noindent \parbox[t][][s]{0.275\textwidth}{% \textbf{Article Info} \vspace{.5em} \hrule \vspace{.5em} \begin{history} %%article info. editor's privilege Received \today \par Revised \par Accepted \end{history} \vspace{.5em} \hrule \vspace{.5em} \begin{keyword} %%write keyword here. separate by \sep Context \sep User Intention \sep Search \sep Autocompletion \sep Data Mining \vspace{.5em} \end{keyword} \vspace{\fill} } \parbox{0.025\textwidth}{\hspace{0.5em}} \parbox[t][][s]{0.7\textwidth}{% \begin{abstract} %% Text of abstract Finding the required URL among the first few result pages of a search engine is still a challenging task. This may require number of reformulations of the search string thus adversely affecting user's search time. Query ambiguity and polysemy are major reasons for not obtaining relevant results in the top few result pages. Efficient query composition and data organization are necessary for getting effective results. Context of the information need and the user intent may improve the autocomplete feature of existing search engines. This research proposes a Funnel Mesh-5 algorithm (FM5) to construct a search string taking into account context of information need and user intention with three main steps 1) Predict user intention with user profiles and the past searches via weighted mesh structure 2) Resolve ambiguity and polysemy of search strings with context and user intention 3) Generate a personalized disambiguated search string by query expansion encompassing user intention and predicted query. Experimental results for the proposed approach and a comparison with direct use of search engine are presented. A comparison of FM5 algorithm with K Nearest Neighbor algorithm for user intention identification is also presented. The proposed system provides better precision for search results for ambiguous search strings with improved identification of the user intention. Results are presented for English language dataset as well as Marathi (an Indian language) dataset of ambiguous search strings. \end{abstract} } \parbox[l]{\textwidth}{% \rule{0.275\textwidth}{0.5pt} \hspace{0.5cm} \hrulefill \\ \emph{\textbf{Corresponding Author: }}\\ %% correspondence info. separate by \\ Name - Uma Gajendragadkar\\ Affiliation - COEP, SPPU, Pune, Maharashtra, India\\ Address - G7/9 Omkar Garden, Manikbaug, Pune, Maharshtra, India\\ Phone- +919822479128\\ Email - umagadkar@gmail.com } \vspace{.5em} \hrule \vspace{.1em} \hrule %% main text \section{Introduction} \label{} Current search engines churn a large volume of data to obtain meaningful information however, the main challenge is to get relevant results in the top few result pages \cite{UmaG2015}. Search engines check for the presence of keywords in documents. Mere presence of keywords in a document may not match the user's search intention and need. User satisfaction increases when more relevant and exact information is presented in the top few results. An appropriately composed query is the starting point for handling this challenge \cite{Bing2015}. Performance of search engines can be improved with the use of appropriate keywords or prediction of such keywords \cite{salton1990}\cite{croft2001}\cite{Harvey2015}. Search engines use search logs and most popular queries; however, these are not sufficient to predict the user's interests or intention \cite{Chirita2007}.\\ Users are of three types, first - Internet skilled users, second - Internet aware users and third - Internet unskilled users. Many times, users do not know the proper keywords for searching information and they cannot express their information need or intent of search\cite{spink1998}\cite{sergio2011}. This results in search results often not satisfying user's information need. This problem can be addressed by query expansion and reformulation \cite{Bing2015}. Search engines provide autocompletions of queries based on popularity \cite{chelaru2013}; however, they are inadequate\cite{Cao2008}\cite{Cai2016}. Although different users may use the same query keyword, their intent and context may be different. Current search engines provide the same results to all users using the same keywords at a given point in time. Personalization is desirable to better satisfy the needs of the user \cite{Sullivan2004}\cite{Ghorab2013}. The following experiment illustrates this further. If a user searches for 'Michael Jackson' then search engines return results for the famous singer Michael Jackson in majority of result pages. These results would be treated as irrelevant and incorrect if the user intent was to search for professor Michael Jackson. \begin{table}[] \small \centering \label{tab1} \begin{tabular}{|l|l|l|} \hline \textbf{Query String} & Michael Jackson & Michael Jackson professor \\ \hline \textbf{Total Results} & About 39,00,00,000 & About 7,89,00,000 \\ \hline \textbf{Search Results As Singer} & First 13 pages & Page 3 - 5th result \\ \hline \textbf{Search Results As Professor} & Page 17 - 8th result & First page \\ \hline \textbf{Search Results As S/W Development} & Page 13 - 10th result & Second page - 2nd result\\ \hline \textbf{Search Results As VP} & Page 16 - 4th result & Not present in the first 20 pages \\ \hline \end{tabular} \caption{Example search query done on Google on 29th May 2015} \end{table} As shown in Table 1, when one searches for the query string 'Michael Jackson', results for the singer 'Michael Jackson' are returned in the first 13 pages whereas no result is returned for the professor 'Michael Jackson'. With each page containing 10 results, the relevant results start appearing after 130 result rows. However, when a word 'professor' is added to the query string 'Michael Jackson', the results for professor Michael Jackson are seen in the first result page itself. This demonstrates that if keywords based on user intention are used then better hits can be obtained in the first few search result pages. \\ Query expansion based on user intention has shown to give better search results over large data sets like Web \cite{Chirita2007} \cite{Liu2011}. Thus user intention can be used to disambiguate a query \cite{Liu2002}. User context can include parameters such as 'gender', 'age', 'topic', location' etc. It can be short-term \cite{Cao2008} or long-term\cite{Liu2002}. \\ In the proposed method, user intention is identified with the help of user profile containing parameters like 'gender', 'profession', 'interests', 'location' and past searches. User intention identified with FM5 algorithm is used to reformulate the query. This paper brings together different IR(Information Retrieval) areas like QAC (Query autocompletion), Query Personalization and automatic query expansion.\\ Our contributions are\\ 1) A novel user intention identification algorithm is proposed to predict user intention.\\ 2) Query expansion is done using identified user intention to get improved precision for ambiguous search strings.\\ 3) Experimental evaluation of the method is conducted with dataset collected from users. The results reflect improvement in user intention identification and precision of search results.\\ \\ In this paper, Section 2 describes the related work. Section 3 explains data description and how it is used by the proposed system while Section 4 describes the FM5 user intention identification algorithm. Results and discussion are described in Section 5. Conclusion is presented in Section 6. \section{Related Work} \label{} \subsection{Autocompletions and Personalization} Bhatia et al.\cite{bhatia2011} present work where phrases and n-grams are mined from text collections and used for generating autocompletions. Most popular completions such as autocompletions based on past popularity of queries in query logs are modeled in Bar-Yossef and Kraus's work\cite{ziv2011}\cite{Cai2014}. Search engines use MPC (Most Popular Completion) for query autocompletion \cite{ziv2011}. Other query autocompletion methods include personalized autocompletion, context based autocompletion using previous queries by users \cite{ziv2011}, time based autocompletion \cite{Whiting2014}, time and context based autocompletion \cite{Cai2014}. Homologous queries and semantically related terms are used to generate autocompletions by Cai et. al.\cite{Cai2016}. Personalization of query results by using the interests of users has been done by many researchers \cite{chirita2005} \cite{Shen2005} \cite{Dou2007} \cite{teevan2008}. User preferences are collected by either implicit or explicit method. Gender and age are used for personalizing the results by Kharitonov and Serdyukov\cite{Kharitonov2012}. User context based on their recent queries is generated and used to rank the query results in a session by Xiang et al. \cite{Xiang2010}. \\ Most of the research conducted is for personalizing the query results by re ranking them using user profile rather than query autocompletion. This paper proposes an algorithm that uses personalization for query completion or autocompletions in search. An improvement in autocompletion ranking is claimed by personalization in Shokouhi's work\cite{shokouhi2013}. Shokouhi et al. also presented ranking of autocompletions with a time-sensitive approach as per their expected popularity \cite{Shokouhi2012}. Ambiguous queries are handled by Shoukhoi et al. by providing user context in terms of session context. Query suggestion is achieved by using click information along with previous queries in a session as context and then mining query log sessions for query reformulations \cite{Shokouhi2015}. This work is similar to our work; however, it doesn't consider longterm user context. It instead focuses on session based user context in terms of click information and previous queries. \subsection{User Intention} Many studies have tried to identify user intention in different ways. Most of them try to categorize the queries as informational, navigational and transactional as proposed by Jansen et. al. \cite{Jansen2010}. Given a query suggestion, efforts have been made to understand the user intention using different means like web search logs \cite{Baeza2006}\cite{Strohmaier2012}\cite{teevan2008}\cite{daxin2013}\cite{Kathuria2010}, previous user's search log for same query \cite{ParkJLJL12}, clicked pages \cite{Das2013}, user's search session history \cite{Fernandez2011}, Wikipedia \cite{Hu2009}, Wordnet and Google n-gram \cite{Hwang2013}. Using search query logs for existing users to identify intention can not guarantee the correctness of search results \cite{ParkJLJL12}. Search intent prediction along with query autocompletion is a less explored area. According to Cheng et al., many searches are triggered by browsed web pages \cite{Cheng2010}. Kong et al. tried to predict search intent using recently browsed news articles before search. A large number of queries are triggered by news articles daily \cite{Kong2015}. Predicting search intent using browsed pages is inadequate \cite{Kong2015}. Our proposed method uses live RSS news feed and other sources for query prediction. It makes use of user profiles to predict the search intent. \subsection{Query Expansion} Query expansion is often used to reformulate the original user query so as to improve retrieval of search results to better satisfy user needs. One of the methods is relevance feedback using the returned results and adding new terms related to the original query and selected documents \cite{Rocchio1971}. Other methods include adding relevant terms based on term frequency, document frequency from top ranked documents \cite{Adesina2001, Xu1996}, co occurrence based techniques \cite{Kim1999}, thesaurus based techniques \cite{Miller1995, Shah2004, Kim2004, Fogaras2005}, desktop specific techniques \cite{Chirita2007}, probability of terms over search logs \cite{Cui2002}. Another approach uses latent topic space derived from query log and uses social tagging data to generate query expansion patterns \cite{Bing2015}. Query modification conditioned to query verbosity detection and topic gisting is used to reformulate the queries \cite{DiBuccio2014}. Liu et al. generated a set of expanded queries from clustered results that provides a classification of the original query results \cite{Liu2011}. This research paper uses a user intention based keyword addition to expand the original query to handle ambiguous query terms. \section{Data Description} \subsection{Data collection Methodology and Data Resources} The system uses different types of data sources. Contextual corpus contains two elements. One is static contextual data based on current month and the other is dynamic contextual data based on daily current events. Based on the parameter 'period', a month-wise list of occasions from Hindu and Christian calendar is taken and their associated keywords list is built. Secondly based on daily current events, RSS news feed from Reuters\cite{reuters} is processed and a dataset of keywords is built \cite{UmaG2015}. The temporal data is refreshed everyday and also at restart of server. This contextual data is generated for both English and Marathi - an Indian language popularly used in the state of Maharashtra by more than 70 million people. Marathi n-gram dataset is created by crawling Marathi websites for about four months and processing the web pages. This Marathi n-gram dataset is made available \cite{Uma2015}. The system also uses data from various sources like Google n-gram \cite{norvig2009} and Wordnet \cite{wordnet06} for English and Marathi Wordnet data \cite{iitb}. How to use above described contextual data to mine possible query autocompletions is discussed by Uma Gajendragadkar et. al. \cite{UmaG2015}. Autocompletions for all sample test queries are collected from popular search engines for comparison. This is done for each character key press of all the test queries. \subsection{User Intention based query expansion} \textit{'K'} user profiles returned by KNN (K Nearest Neighbor) algorithm are as used as input to the FM5 algorithm. Let \begin{equation} Z' = \{Z, \bar{Z}\} \end{equation} be a set of user profiles such that \begin{equation} P(Z') = \sum P(Z) + \sum P(\bar{Z}) = 1 \end{equation} where $P(Z)$ is the probability of the known user profiles and $P(\bar{Z})$ is the probability of unknown user profiles. Let \begin{equation} A = \{a_i | 0 \leq i \leq n-1\} \end{equation} be the set of \textit{n} query words and let \begin{equation} B = \{b_j | 0 \leq j \leq m-1\} \end{equation} be the set of \textit{m} intentions. A trial is conducted by collecting random samples $$. For each sample query keyword $a_i$, there could be multiple user intentions $b_j$ stored in the intention matrix. Total 34 different user intentions are considered. For example consider keyword - 'Jaguar'. It can have two possible user intentions - 'Automobile' (the car) and 'Wildlife' (the animal). \subsection{Learning Method and Knowledge Generation} Association rule based learning method is used for user intention identification. Support and confidence for an intention are computed for the predicted keyword. Association rule learning is used to find interesting relations between different parameters in the data \cite{Agrawal1993}. It finds strong rules in data based on support and confidence measures. If a rule such as $$\{\mathrm{milk, sugar}\} \Rightarrow \{\mathrm{coffee}\} $$ is found in the data, it indicates that a customer is likely to buy coffee if the customer has bought both milk and sugar. Association rule is used in many applications like market analysis, bioinformatics, web usage mining etc. Minimum threshold values on support and confidence are used to find the interesting rules out of all possible rules. If $I = \{i_1, i_2, i_3,\dots, i_n\}$ is a set of items and $D_b = \{tr_1, tr_2, \dots, tr_m\} $ is a set of transactions in database $D_b$, then a rule can be defined as $U \to V$ where $U, V \subseteq I$ and $ U \cap V = \Phi$. Support can be calculated as proportion of transactions containing the item set U. For illustration, the item set \{milk,sugar\} has a support of 6/10 = 0.6 since it occurs in $60\%$ of all transactions. Confidence of rule $U \to V$ can be calculated as the proportion of the transactions that contain both U and V. \begin{equation} \mathrm{conf}(U \Rightarrow V) = \mathrm{supp}(U \cup V) / \mathrm{supp}(U) \end{equation} For illustration, the rule $$\{\mathrm{milk, sugar}\} \Rightarrow \{\mathrm{coffee}\}$$ has a confidence of $0.9$ which means in $90\%$ of the transactions that contain milk and sugar, the rule holds true. Other user intention identification methods have a few drawbacks. Using web search logs for intent identification lacks in correct outcomes as the same query responses have been provided to all the users. Using click pages \cite{Das2013} is not very effective as user clicks do not always translate to the result being relevant to search intent. User search session history \cite{Fernandez2011} works only for a session. Hu et. al. do not consider ambiguous queries in case of intent identification with Wikipedia \cite{Hu2009}.\\ % Please add the following required packages to your document preamble: % \usepackage{graphicx} \begin{table}[] \centering \resizebox{\textwidth}{!}{% \begin{tabular}{|l|l|l|l|l|l|} \hline \textbf{Word} & \textbf{Intent} & \textbf{Gender} & \textbf{Location} & \textbf{Profession} & \textbf{Interest} \\ \hline bond & legal & M & India & Lawyer & Cooking \\ \hline court & legal & M & India & Engineer & Gardening \\ \hline judge & legal & M & USA & Lawyer & Books \\ \hline law & legal & F & UK & Farmer & TV \\ \hline notary & legal & F & India & Doctor & Painting \\ \hline notice & legal & M & India & Lawyer & Poems \\ \hline search & legal & F & India & Engineer & Gardening \\ \hline java & political & F & USA & Doctor & Poems \\ \hline jaguar & Automobile & M & USA & Engineer & Art \\ \hline diabetes & health & M & UK & Doctor & Theater \\ \hline interest & social & M & India & Farmer & Photography \\ \hline apple & technological & F & India & Engineer & Wildlife \\ \hline java & technological & M & India & Engineer & Sports \\ \hline bond & movie & M & India & Engineer & Movies \\ \hline \end{tabular} } \caption{Example data for association rule mining} \label{tab2} \end{table} Table 2 shows a few records from training data used for learning user intent for a given keyword. From this data, all rules having a support and confidence more than the threshold value are considered. These rules are used to learn about the possible intention of a user for a keyword. Let \begin{equation} G = \{g_i | 1\leq i \leq m\} \end{equation} be the returned intentions and $g_i \in B$ in equation 4. Section 4 describes the method to select appropriate intention. The experimental setup considers two types of users - registered users and unregistered users. When a user creates a user profile in the system, she becomes a registered user and users using the system without creating profiles are considered unregistered users. It is assumed that registered users will always log into the system. Set Z consists of known user profiles whereas $\bar{Z}$ forms set of unknown user profiles as in equation 1. If a user does not log into the system then the user profile is not available. Hence no personalization can be done and no learning happens. User profile $'X_1'$ is created by obtaining user preferences for a set of questions. The values are filled in by an explicit questionnaire.Answers to questions like 'What is your Profession?', 'What is your Interest?' etc. will set the values. User preferences are stored in the user profile. Any searches done by the user will form the past searches component of user profile. A bit vector representing user profile is stored in the system for every registered user. \begin{equation} X_1= \{ X_{1_0}, X_{1_1}, X_{1_2}, \dots,X_{1_d} \} \end{equation} The system personalizes search strings based on these user preferences and learns from past searches. After pressing a key character in search box, the system tries to predict the next character by using the past searches of the registered user initially and later by using the pool of searches done by other users having similar profiles to the current user. Comparison of this method is done with KNN (K Nearest Neighbor) algorithm. The graphs in Figure 1 show the performance of KNN for user intention identification with different K values on sample data. \begin{figure}[htbp] \centering \subfloat{{\includegraphics[width=5cm]{KNNMatchedScurve.png} }} \qquad \subfloat{{\includegraphics[width=5cm]{KNNUnMatchScurve.png} }} \qquad \subfloat{{\includegraphics[width=6cm]{KNNwithK.png} }} \caption{Performance of KNN with sample data} \label{fig2:} \end{figure} As seen in Figure 1, KNN shows better performance with smaller k value for identifying the user intention but the accuracy of the identification is less (about 39\%). To better predict the user intention, we have proposed the FM5 algorithm. \section{Proposed Method} The objective is to find appropriate user intention for a search string being entered by a user in the search box. Existing user intention identification methods have a few shortcomings. Using web search logs for intent identification lacks in correct outcomes as the same query responses have been provided to the users. Using click pages \cite{Das2013} is not very effective as user clicks do not always translate to the result being relevant to search intent. User search session history \cite{Fernandez2011} works only for a session. No user intention prediction was done for ambiguous query in case of intent identification with Wikipedia \cite{Hu2009}.\\ In FM5 algorithm, user profiles are used to identify user intention for a search string being entered in the search box. As described in Section 3 a user profile is created during registration. FM5 implements a funnel filter consisting of different meshes mapped to the user profile parameters. Weights are applied to these meshes to disambiguate different user intentions of query word $a_i$ as given in equation 22. User can select a set of parameters to be applied. If user's current search intention is related to her \textit{'Interest'} rather than her \textit{'Profession'} then only parameters like \textit{'Interest, Gender, Location'} may be selected and other parameters like \textit{'Profession'} may be omitted. \\ Let \begin{equation} P_{Z_i} = {P_0, P_1, P_2, \dots, P_d} \end{equation} be the set of parameters considered for the experiment. For example, user profile consists of 5 parameters - 'Profession', 'Interests', 'Gender', 'Location' and 'Past searches'. For illustration purposes, higher weight is assigned to the parameter \textit{'Profession'} followed by \textit{'Gender', 'Interests', 'Location', 'Past searches'} respectively. This is configurable and more parameters can be added to the funnel shown in Figure 2. \begin{figure} \centering \includegraphics [width=8cm]{userfunnel.png} \caption{Personalization Funnel for User Intent} \label{fig3:} \end{figure} Let \begin{equation} W_z = {w_0, w_1, w_2, \dots, w_d} \end{equation} be the set of weights such that \begin{equation} f_x : P_{Z_i} \to W_z | w_i < w_{i+1} \end{equation} The computation of these weights is explained in equation 22. Let Q be the prefix query input string which is progressively attached with an alphanumeric character to complete the search string. \begin{equation} Q = \{q_i | 0 \leq i \leq n\} \end{equation} where $q_i , q_{i+1}, \dots$ are characters to compose the search string assuming \textit{n} character keypresses. Initial state of this set is empty. $q_i$ can be any character ranging from 'a to z' and '0 to 9' or characters like $ ':, ;, ~, \dots'$ etc. Let $q_{i+1}$ be a partial search string. The composition of search string and related selection of $q_i$ are done using elements of set $X_1$ as per equation 7. \subsection{Circular structure for User profile parameters} The user profiles are organized in a circular linked list as shown in Figure 3. A circular linked list is used as one can add or remove parameters from the list easily and it is easy to traverse the list to reach an object. Learning will add or subtract parameters from circular linked list. Size of the circular linked list will increase or decrease accordingly. Let 'r' be the radius of the circle on which various user profiles are arranged. \begin{figure} \centering \includegraphics [width=8cm]{CircularLink2.png} \caption{Circular structure used to detect User Intention} \label{fig4:} \end{figure} The pointer in the circular structure is placed as per the weight calculated by association rule in terms of support as shown in equation 20. Let $X_2$ be the cost \begin{equation} X_2 = \{ C_i | 0 \leq C_i \leq 1\} \end{equation} associated with elements of Q such that \begin{equation} f_1 : Q \to X_2 \end{equation} $C= 1$ when a partial or complete search string does not exist in the search set or the algorithm fails to predict the search string. $C = 0$ when the search string is distinctly known. In this case, no search string prediction and composition is required. The selection of search string is done such that it always has central tendency. Since the search string is computed and mapped in the range $[0,1]$, the central tendency predicts the most likely search string. Computation of logical search string is done with the various parameters of user profile. Greedy algorithm is used for intention selection using cost(weight). Each time we select the mesh (parameter) with largest weight and greater than or equal to threshold value as explained in equation 21. \subsection{Personalization Algorithm: (Funnel Mesh 5 - FM5)} The algorithm in pseudo code form is represented in the Algorithm 1. Rest of the section explains it in detail. % Algorithm \begin{algorithm}[htbp] \SetAlgoNoLine $U_C$ = Current user profile\; $U_N$ = Compute nearest User profile vector Matrix\; $q_i$ = Get prefix input\; $K_{w(q_i)}$ = Build set of query strings starting with $q_i$ from past searches $\in U_N$\; \For{each $searchkey$ \in $K_{w(q_i)}$ } { Rules = Compute association rules of type $searchkey \leftarrow parameter/s \in U_N$\; \For {each rule $R_i$ \in $Rules$ } { W = Compute support ($R_i$) where $Supp(X \to Y) = \fraction {\sigma (X \cup Y)}/ {N} $ \; \If {$W \geq THRESHOLD$} $P_j$ = Get user profile parameter $\in R_i$\; $X_4 =$ Build Mesh \; $Mesh = Mesh \cup P_j$\; \EndIf } \For {each $P_j$ \in Mesh } { % Apply filter meshes and filter user profiles \For {each user \in $U_N$ } { \If {$U_N.P_j$ = $U_C.P_j.value$} $X_6 = X_6 \cup user$\; \EndIf } } % Get list of intentions from filtered user profiles \For{each pastsearh \in $X_6$ } { \If {pastsearch = search key} $X_7 = X_7 \cup pastsearch.intention$\; \EndIf } % Compute matching intention Return User intention(searchkey) = $ \underset{mi \in X_7} \argmax$ f(mi) \; where f(mi) = frequencies of intentions in $X_7$ \; } \caption{FM5 User Intention Identification algorithm} \label{FMalgorithm} \end{algorithm} If $X_{1_i} = Profession$ then \begin{equation} X_{1_i} = \{ Engineer, Doctor, Lawyer, Architect, \dots\} \end{equation} or combination of these. The system assumes that one user has one profession. If 6 bits are used to store profession parameter then $2^6$ combinations are possible. For example, let the bit sequence '000001' indicate \textit{ profession = Engineer}. The probability of choosing the correct profession is \begin{equation} P(X_{1_i}) = \fraction {1}/{ 2 ^ t } \end{equation} where t = number of bits used to store the parameter.\\ Let \begin{equation} X_3 = \{ X_{3_0}, X_{3_1}, X_{3_2}, \dots, X_{3_n} \} \end{equation} be the past searches associated with the user profile vectors in circular linked list. \\ Let \begin{equation} X_{3_i} = \{ S_0, S_1, S_2, \dots, S_m \} \end{equation} be the past search strings associated with $X_{3_i}$. \\ Then \begin{equation} f_2 : S_i \to W_i \end{equation} where weight $W_i$ is the support value calculated using association rule for search string $S_i$ as shown in equation 20. $\forall S_i \in X_{3_i}$ a list of parameters is given by \begin{equation} X_4 = \{ X_{4_0}, X_{4_1}, X_{4_2}, \dots, X_{4_k} \} \end{equation} Weight is computed using association rule of the form $X \to Y$ having value $\geq 0.5$ (threshold) as we are calculating the central tendency as discussed in Section 4.1. Here $\exists X_{1_i} \in X $ and $\exists S_i \in Y $ and support value is given by \begin{equation} Supp(X \to Y) = \fraction {\sigma (X \cup Y)}/ {N} \end{equation} where N = total number of records in the circular linked list and X is a combination of parameters from $X_1$ whose $support \geq 0.5$. Then for current user, \forall S_i $ (search strings) starting with the prefix Q, \begin{equation} X_4 = \{ X_{4_0}, X_{4_1}, X_{4_2}, \dots, X_{4_k} \} | W_i \geq 0.5 \end{equation} \begin{equation} W_i = Supp(X \to Y) \end{equation} \begin{table}[] \small \begin{tabular}{|l|l|l|l|l|l|} \hline \textbf{Intention} & \textbf{ Example} & \textbf{Intention} & \textbf{Example} & \textbf{Intention} & \textbf{Example } \\ \hline Social & Christmas & Agriculture & Crop & Movies & Actor \\ \hline Technical & Apple & Bad Meaning words & Bloody & Theater & Plot \\ \hline Research & Literature & Music & Notes & Art & Singing \\ \hline Political & Economy & Cooking & Pie & Craft & Craft \\ \hline Philosophy & Thinking & Sports & Football & Painting & Paint \\ \hline Medical & Heart & Gardening & Seed & Travel & Distance \\ \hline Military & Attack & Health & Exercise & Hiking & Everest \\ \hline Religious & Holy & Books & Novel & Social work & NGO \\ \hline Scientific & Lab & Writing & Publisher & Sculpting & Sculpture \\ \hline Legal & Offense & Poems & Stanza & Photography & Photo \\ \hline New Generation & Selfie & TV & Soap & Literature & Article \\ \hline & & & & Wildlife & Tiger \\ \hline \end{tabular} \caption {User intention categories and examples} \end{table} For $ S_i \in X_{3_i} $ let \begin{equation} X_5= \{ X_{5_0}, X_{5_1}, X_{5_2}, \dots, X_{5_h} \} \end{equation} be the set of possible user intentions. Total 34 intentions are considered for the experimental setup. Table 3 shows user intention taxonomy and example keywords for each of the intentions. For example, the keyword 'Seed' falls under intention 'Gardening' whereas 'Stanza' belongs to 'Poems'. For $a_i$ as in equation 3, all search strings starting with prefix Q would be considered. Let the set of search strings starting with prefix be \begin{equation} X_6 = \{ S_{6_0}, S_{6_1}, S_{6_2}, \dots, S_{6_k} \} \end{equation} Initial probability of choosing the next character is \begin{equation} P(q_{i+1})= \fraction {1} / {| X_6|} \end{equation} \begin{figure} \centering \includegraphics [width=4in]{Refinedkey2.png} \caption{User Intention Identification} \label{fig5:} \end{figure} With each character keypress $q_{i+1}$, this probability increases as $| X_6 | $(count of possible search strings) keeps on reducing as shown in Figure 4. As in Figure 4, with every parameter having weight (support) greater than the threshold, a mesh filtering is done and user intention list keeps on reducing and the algorithm makes use of the central tendency to identify matching intentions. From equation 23, we know there are 'h' intentions. Initially there are 'h' intentions. Hence probability of choosing matching intention will be \begin{equation} P(MI)= 1/h \end{equation} where MI = matching intention. Based on weights calculated in equation 22, we choose parameters from set $X_5_i$ for each past search string and a further function {\bf $f_{n_3} : Q \to MI$ } is applied. $f_{n_3}$ gives a reduced set of matching intentions from initial \textit{’h’} intentions as shown in Figure 4. Let the returned multiset be given as \begin{equation} X_7 = \{ X_{7_0}, X_{7_1}, X_{7_2}, \dots, X_{7_r} \} | r | a_i \in A, c_j \in C\} \end{equation} Let \begin{equation} f : MI \to Q' \end{equation} \begin{table*}[] \centering \begin{tabularx}{\linewidth}{|b|b|s|s|} \hline \textbf{ Keyword \hspace{1cm}\{User - Gender, Profession,\hspace{1cm} Interest, Location \}} & \textbf{Cost – Mesh selected} & \textbf{Intentions of final user set after filtering} & \textbf{Matching Intention} \\ \hline \textbf{Jaguar \hspace{2cm} \{User – Female,\hspace{1cm} Engineer, Music, India\}} & {0.6 - Profession $\rightarrow $ Jaguar 0.7 - Location $\rightarrow $ Jaguar} & {Automobile Wildlife Automobile Automobile Automobile} & Automobile \\ \hline \textbf{Java \hspace{2cm} \{User – Female,\hspace{1cm} Engineer, Sports, India\}} & {0.63 - Profession $\rightarrow $ Java 0.6 - Gender $\rightarrow $ Java \hspace{1cm} 0.7 - Location $\rightarrow $ Java} & {Research Technology Technology} & Technology \\ \hline \textbf{Bond \hspace{2cm} \{User – Male,\hspace{2cm} Engineer, Movies, India\}} & {0.76 - Location $\rightarrow $ Bond} & {Movie \hspace{1cm} Legal\hspace{1cm} Movie\hspace{1cm} Movie \hspace{1cm} Legal \hspace{1cm} Movie} & Movie \\ \hline \end{tabularx} \caption{Example test cases for FM5 algorithm} \label{tab88} \end{table*} be the function which maps the identified matching user intention to an expansion pattern from $Q'$. Then the original query is modified as \begin{equation} Q = Q \cup Q' \end{equation} and given to search engine. Table 4 lists 3 sample test cases for FM5 algorithm. The first column lists a test keyword and the profile of the user entering test keyword. The second column lists the association rule/s (mesh parameter/s) selected and its cost.The third column lists possible intentions obtained after filtering through chosen meshes.The fourth column lists the matching intention generated as output for the keyword. The first keyword 'Jaguar' is entered by a user who is 'female' and an 'engineer' having 'music' as her interest and is located in 'India'. After computing the support (cost) for all possible association rules with user profile parameters on LHS and keyword on RHS, only two rules are found having support greater than or equal to threshold of 0.5. Hence two meshes – profession and location are applied. After filtering, a set of 5 users is obtained. From the past searches of these 5 users, intentions for keyword ‘Jaguar’ are selected and are displayed in the third column. Out of these 5, the most frequently occurring intention – ‘Automobile’ is returned as the matching intention. \section{ Results and Discussion} Authors developed a questionnaire to collect the user profiles and the desired intents for the search strings as Shown in Figure 5. For first English dataset, 25 users and 15 ambiguous queries per user and their desired intent for each query were collected. Thus, 375 queries and intentions were evaluated for first dataset. For second English dataset, 100 users and 20 ambiguous queries per user and their desired intent for each query were collected. For second dataset overall 2000 queries and intentions were evaluated. For Marathi dataset, 25 users and 18 ambiguous queries per user were evaluated. Thus Marathi dataset contained overall 360 queries and intentions. The survey was designed as a paper-and-pencil-based field survey to approach a large number of users and a digital survey was also designed on the same line. The paper-based questionnaire was designed in two languages i.e. English and Marathi. To validate the proposed model, the questionnaire was distributed to collect the user profile information and desired intention while searching for various ambiguous queries. Population of the study comprises of Engineers, Doctors, Farmers and Lawyers. Samples of 170 users were selected randomly. After scrutiny of filled questionnaire 150 were found to be fit for the analysis. The users are third year Engineering students from different streams of College of Engineering Pune \cite{COEP} as well as doctors, farmers and lawyers from different locations in India. \begin{figure}[htbp] \centering \includegraphics [width= 12cm]{UserSurvey.png} \caption{User Survey Questionnaire designed to collect user profile and intentions } \label{fig8:} \end{figure} The system is evaluated for 25 users for English dataset-1 with about 15 ambiguous queries each. The training data consists of about 55 user profiles and their past searches. Table 5 shows user intention identification results for FM5 algorithm and KNN algorithm with different 'k' values like 5 (KNN5), 10 (KNN10) and 15 (KNN15). Matched intention indicates the total number of ambiguous test queries for all test users where the algorithm gave matching intention to the desired intention of user. Unmatched intentions indicate the number of cases where algorithm failed to identify desired intention. The results for user intention identification, obtained with FM5 are encouraging. For English ambiguous dataset-1, accuracy of about 75\% is observed with FM5 whereas with KNN an accuracy of about 38.4\% is observed for KNN5 and 29.8\% with KNN10 and 27\% with KNN15. \begin{table}[] \centering \begin{tabular}{|l|l|l|l|l|} \hline \textbf{ Intention/Method} & \textbf{FM5} & \textbf{KNN15} & \textbf{KNN10} & \textbf{KNN5} \\ \hline \textbf{Matched} & 282 & 102 & 112 & 144 \\ \hline \textbf{Unmatched} & 93 & 273 & 263 & 231 \\ \hline \textbf{Total} & 375 & 375 & 375 & 375 \\ \hline \textbf{Accuracy} & 0.752 & 0.272 & 0.298 & 0.384 \\ \hline \end{tabular} \caption{English Ambiguous Dataset-1 Results} \label{tab4} \end{table} \begin{figure}[htbp] \centering \subfloat{{\includegraphics[width=7cm]{IntentionEnglish.png} }} \qquad \subfloat{{\includegraphics[width=7cm]{IntCompEnglish.png} }} \caption{Results for Ambiguous English Dataset-1} \label{fig6:} \end{figure} First graph in Fig 6 shows Matched intentions obtained for FM5 and KNN for different users with various queries on English dataset-1. 'Matched' is the legend used for cases where appropriate user intention is obtained and 'Unmatched' is the legend showing cases where the algorithm failed to identify appropriate user intention. The second graph in Figure 6 shows comparison of FM5 with KNN algorithm for different values of 'K'. FM5 gives better results than KNN. \begin{table}[] \centering \begin{tabular}{|l|l|l|l|l|} \hline \textbf{ Intention/Method} & \textbf{FM5} & \textbf{KNN15} & \textbf{KNN10} & \textbf{KNN5} \\ \hline \textbf{Matched} & 279 & 87 & 102 & 132 \\ \hline \textbf{Unmatched} & 81 & 273 & 258 & 228 \\ \hline \textbf{Total} & 360 & 360 & 360 & 360 \\ \hline \textbf{Accuracy} & 0.775 & 0.242 & 0.283 & 0.367 \\ \hline \end{tabular} \caption{Marathi Ambiguous Dataset Results} \label{tab5} \end{table} For Marathi ambiguous dataset evaluation, the system is evaluated with 20 users with 18 ambiguous queries each as shown in Table 6. The training dataset consists of 40 user profiles and their past searches. Accuracy of about 77.5\% is observed with FM5 algorithm whereas with KNN an accuracy of about 36.7\% is observed for KNN5 and 28.3\% with KNN10 and 24.2\% with KNN15. User intention identification for search string with FM5 algorithm gives encouraging results. Figure 7 depicts the results for Marathi dataset. First graph in Figure 7 shows the total number of Matched intentions obtained with FM5 and KNN for each user. The second graph in Figure 8 shows total number of matched and unmatched intentions for all users with FM5 and KNN. \begin{figure}[htbp] \centering \subfloat{{\includegraphics[width=7cm]{IntentionMarathi.png} }} \qquad \subfloat{{\includegraphics[width=7cm]{IntCompMarathi.png} }} \caption{Results for Ambiguous Marathi Dataset} \label{fig7:} \end{figure} The accuracy observed with FM5 and KNN algorithm for English dataset-1 is plotted in Figure 8. \begin{figure} \centering \includegraphics [width= 8cm]{FM5AccuracyEnglish.png} \caption{Accuracy observed with FM5 User Intention Identification for English} \label{fig9:} \end{figure} The accuracy observed with FM5 and KNN algorithm for Marathi dataset are plotted in Figure 9. \begin{figure} \centering \includegraphics [width= 8cm]{FM5AccuracyMarathi.png} \caption{Accuracy observed with FM5 User Intention Identification for Marathi} \label{fig9:} \end{figure} Further testing of the FM5 algorithm was done using English ambiguous dataset-2. The system is further evaluated for 100 users for English dataset-2 with 20 ambiguous queries each. A user survey was conducted to collect the user profiles as well as the desired intentions for a set of ambiguous queries. The users are third year Engineering students from different streams of College of Engineering Pune \cite{COEP} as well as doctors, farmers and lawyers from different locations in India. The training dataset consists of 50 user profiles and their past searches. \\ Table 7 shows user intention identification results for FM5 algorithm and KNN algorithm with different 'k' values like 5 (KNN5), 10 (KNN10) and 15 (KNN15). Matched intention indicates the total number of ambiguous test queries for all test users where the algorithm gave matching(correct) intention to the desired intention of user. Unmatched intentions indicate the number of cases where algorithm failed to identify desired intention. The results obtained for English dataset-2 with FM5 shows improvement of 0.7\% as compared to English dataset-1. This may be because of increased number of past searches available while computing the parameters to build the mesh. For English ambiguous dataset-2, accuracy of a 75.9\% is observed with FM5 whereas with KNN an accuracy of about 39.3\% is observed for KNN5 and 29.05\% with KNN10 and 28.3\% with KNN15. \begin{table}[] \centering \begin{tabular}{|l|l|l|l|l|} \hline \textbf{ Intention/Method} & \textbf{FM5} & \textbf{KNN15} & \textbf{KNN10} & \textbf{KNN5} \\ \hline \textbf{Matched} & 1518 & 566 & 581 & 786 \\ \hline \textbf{Unmatched} & 482 & 1434 & 1419 & 1214 \\ \hline \textbf{Total} & 2000 & 2000 & 2000 & 2000 \\ \hline \textbf{Accuracy} & 0.759 & 0.283 & 0.2905 & 0.393 \\ \hline \end{tabular} \caption{English Ambiguous Dataset-2 Results} \label{tab4} \end{table} First graph in Fig 10 shows Matched intentions obtained for FM5 and KNN for different users with various queries on English dataset-2. 'Matched' is the legend used for cases where appropriate user intention is obtained and 'Unmatched' is the legend showing cases where the algorithm failed to identify appropriate user intention. The second graph in Figure 10 shows comparison of FM5 with KNN algorithm for different values of 'K' for English dataset-2. \begin{figure}[htbp] \centering \subfloat{{\includegraphics[width=8cm]{IntentionEngDataset2.png} }} \qquad \subfloat{{\includegraphics[width=8cm]{IntCompEngDataset2.png} }} \caption{Results for Ambiguous English Dataset-2} \label{fig6:} \end{figure} \begin{table}[] \centering \begin{tabular}{|l|l|} \hline \textbf{Query Results} & \textbf{Average Precision} \\ \hline Top 5 & 1 \\ \hline Top 10 & 0.988 \\ \hline Top 15 & 0.983 \\ \hline Top 20 & 0.990 \\ \hline Top 25 & 0.985 \\ \hline Top 30 & 0.981 \\ \hline Top 35 & 0.980 \\ \hline Top 40 & 0.978 \\ \hline Top 45 & 0.978 \\ \hline Top 50 & 0.970 \\ \hline \end{tabular} \caption{Average Precision after Query Expansion} \label{tab6} \end{table} Table 8 shows the results of query expansion after user intention identification is done. Top 50 URLS returned by Google API were collected for each query after query expansion. The web pages of these URLS were evaluated as either relevant or not relevant to the query under consideration. Table 9 shows average precision values obtained for test queries after query expansion based on identified user intention. Metric used for evaluation of search results returned after query expansion is \begin{equation} P@K= relevant queries / K \end{equation} It indicates how many valuable or relevant results are present in top K search results. \begin{figure} \centering \includegraphics [width=3in]{AvgPrecisionBaseline.png} \caption{Precision Improvement with FM5 and Query Expansion} \label{fig9:} \end{figure} Graph in Figure 11 shows average precision values for top 5, top 10, up to top 50 results obtained with the proposed FM5 and query and to our proposed system and without using the algorithm. On X-axis, 1,2,3,.. indicate the top 5, top 10, top 15, .. etc. ; the average precision values for all the queries given by the user for the first 5 results or 10 results etc. From the observed values, the system shows significant improvement in the average precision values. The results are compared to the results obtained using Google search engine and the results obtained for ambiguous queiries by Chirita et. al \cite{Chirita2007}. About 60.47 \% improvement is seen in average precision with FM5 and query expansion as compared to the results obtained using Google. This is our first baseline comparison. Second baseline comparison is with the results obtaind by Chirita et.al. and an improvement of 40\% is observed with the proposed method. \\ \section{Conclusion} Composing the search string by providing better autocompletions to the user that will result in more relevant and less redundant results is the goal of this research. In this algorithm, personalization is used to add context and user intention to the search string composition. The algorithm selects the most appropriate intention out of possible intentions for a keyword by using support as weight. The FM5 algorithm of intent identification via funneling builds upon the advantages of simple k-nearest neighbor algorithm. The approach consists of identification of user intention with FM5 and then expanding original the query based on this intention to obtain more relevant search results in the first few pages. FM5 user intention identification algorithm uses association rule mining with user profiles and shows improvement in performance as compared to KNN. This FM5 when extended with query expansion patterns shows improvement in average precision values for ambiguous queries giving better search results. The system does not use explicit feedback or other strategies like using click pages or session history for determining user intention or for query expansion. Proposed User intention identification algorithm - FM5 showed improvement in accuracy as compared to KNN. Proposed query expansion approach using identified user intention with FM5 showed improvement in average precision values for ambiguous queries giving better search results in top 50 pages. Experimental results for the proposed approach and a comparison with direct use of search engine showed that performance was improved significantly. The proposed system provides better precision for search results for ambiguous search strings with improved identification of the user intention for English language dataset as well as Marathi (an Indian language) dataset of ambiguous search strings. \section*{Acknowledgement} \label{} The acknowledgment section is optional. The funding source of the research can be put here. %% The Appendices part is started with the command \appendix; %% appendix sections are then done as normal sections %% \appendix %% \section{} %% \label{} %% References %% %% Following citation commands can be used in the body text: %% Usage of \cite is as follows: %% \cite{key} ==>> [#] %% \cite[chap. 2]{key} ==>> [#, chap. 2] %% %% References with BibTeX database: \bibliographystyle{IEEEtran} %\bibliography{} \bibliography{bibtexrefs} %% Authors are advised to use a BibTeX database file for their reference list. %% The provided style IEEEtran.bst formats references is generally used. %% For references without a BibTeX database: \section*{BIOGRAPHY OF AUTHORS} \begin{biography}[{\includegraphics[width=3cm,height=4cm,clip,keepaspectratio]{Author's_Photo}}] \textbf{Uma Gajendragadkar} %% Affiliation and educational background. is a PhD Scholar at COEP, Savitribai Phule Pune University, Pune, Maharashtra, India. She completed Masters in Computer Engineering from Mumbai University, India in 2004 and Bachelors in Electronics Engineering in 1993 from Shivaji University, Kolhapur, India. She worked as a TEQIP Research Fellow for past 4 years at COEP,SPPU, Pune, Maharashtra, India. She has 8 years of experience in Software Industry and 13 years of experience in Academics where she taught Undergraduate and Postgraduate Engineeing students. She is member of IEEE and ACM for past eight years. \end{biography} \begin{biography}[{\includegraphics[width=3cm,height=4cm,clip,keepaspectratio]{Author's_Photo}}] \textbf{Dr. Sarang Joshi} %% Affiliation and educational background. is a Professor at PICT, Savtribai Phule Pune University, Pune, Maharashtra, India. He completed his PhD in Computer Science and Engineering from Bharati Vidyapeeth, Pune, India. He completed Masters in Computer Engineering and Bachelors in Computer Engineering from University of Pune, India. He works as a Professor in Computer Engineering at PICT, SPPU, Pune, Maharshtra, India for last 27 years. He was the Chairman of Board of Studies of Computer Engineering at Savitribai Phule Pune University for past 3 years. He has written a book on Big Data Mining -Application Perspective ISBN: 978-81-203-5116-5. \end{biography} \end{document} %% %% End of file `iaesarticle2.tex'.