Dept. of Comp.Engg
,Savitribai Phule Pune university,Pune-411041
Dept. of Comp.Engg
,Savitribai Phule Pune university,Pune-411041
In today’s world, Keyword suggestion in web search is a very important
feature to be considered. The main problem for search engine is that the
queries provided by user are sometime very short and short queries are
ambiguous .Then result provided by search engine do not satisfy user’s
requirements. User do not know how to express in the form of query or he may
have less knowledge about the thing that he wants to search .To solve his
problem search engine provide a set of keywords as query suggestion. To
increase the experience of user’s search
engine query suggestion is provided. Query suggestion helps user to specify
query in the form of set of keywords and
provide appropriate result to the user, But today’s query suggestion do not
consider location of user and the distance factor between user location and
document’s location. If location of user is considered for query suggestion
then user will get more relevant document. The location aware keyword query
suggestion (LKS) takes the location of user and retrieve the document to the
user which are close to user’s location. In this paper we will discuss the LKS
framework and discuss the research work that has been done previously.
Bipartite graph,Document proximity, Location-based
Location-based search, Keyword
search, Nearest neighbors Spatial databases
Search engine is
a tool to find the information .However many a times user unable to locate
required document to their problems. This process is also known as “struggling search”
.In struggling search to achieve required result user struggles a lot to
formulate query. For example user wants to search “apple” then this single word query is a
challenge for search engine to provide relevant document for query .In this
case search engine face the problem to show result as Apple as fruit or Apple
also looking for information on a topic which is new for user as per his needs
hence he also faces problem to construct appropriate query. And there are
billions of web pages and user have to search from that information. If the
relevant document for user’s query are very deep in result list then at that
point user’s query will fail.
suggestion has become a very important feature of today’s Web search engines.
Query suggestion’s aim is to refine user’s experience of search engine by
suggesting alternate query for his first query so that he can get more
information and get more relevant document. Many times even literate user of
web faces the problem to formulate a query. After submitting a query, if
expected result were not retrieved then user may not be satisfied with the
results as he was expecting some other results. Major problem of current search
engine is that the queries are short. The biggest problem for search engine is
short query. Sometime user have very less knowledge about topic hence user
submit short queries. To provide relevant result for such query search engine
should be very smart to understand user’s requirement. Query suggestion helps user to construct a query. Many query suggestion technique has
proved that they fulfill user’s needs.
set of keywords provided by query suggestion is not a good descriptor of user’s
needs. None of query suggestion methods are location based. User’s location is
not considered during query suggestion .The location aware keyword query
suggestion (LKS) provides result which are relevant to user’s need also located
near user’s location.
aware keyword suggestion (LKS) provide
the queries and retrieve documents which are near to user’s location and at the
same time relevant to his needs, LKS will construct keyword document bipartite
graph(KD graph) that will connect to
keyword queries to their relevant document. LKS adjust weight on each edge of
KD graph to get semantic relevance between document location and user’s
location .To calculate distance Personalized Page Rank (PPR) algorithm is used
. In PPR it uses random walk with restart on KD graph .The state of art of Bookmark
Coloring Algorithm for RWR is extended calculate Location-aware suggestion. In
addition to this Partition algorithm is used to reduce the computational cost
of research work is done on query suggestion previously Table 1 contains the related
work of different research paper
recommendation using query logs in search engines
R. Baeza-Yates, C. Hurtado,
and M. Mendoza
recommendation using query logs
Advantage : Query recommendation Disadvantage :
Keywords are not recommended
clustering of a search engine query log
D. Beeferman and A. Berger
of Search Engine is used for result.
Advantage: Easy to use because clustering is
implemented. Disadvantage: Search
engine is used but In clustering selection query is not logged easily.
suggestion by mining click-through and session data
H. Cao, D. Jiang, J. Pei,
Q. He, Z. Liao, E. Chen, and H. Li
Context aware query and used as parallel mining
Advantage: Context aware query is applied on the
text format. Disadvantage: It does not
show any application of location.
using hitting Time.
Q. Mei, D. Zhou, and K.
are suggested using time Hitting Time
Advantage: Query suggestion using time hitting
Disadvantage: time is reinstated.
Optimal rare query
suggestion with implicit user feedback
Y. Song and L.-W. He,
query suggestion with implicit user feedback “Feedback” are given as the recommendation.
Advantage: optimal suggestion with feedback
Disadvantage: Only recommendation are
used & does not show any location
Time-aware structured query
T. Miyanishi and T. Sakai
Time is important point where
query is suggested with time aware
Time aware query and data is structured suggested.
Disadvantage: Time taken is more to execute
The query-flow graph: Model and applications
P. Boldi, F. Bonchi, C. Castillo, D. Donato, A.
Gionis, and S. Vigna
Query flow graph mainly model
based structure and model are based on the application
Disadvantage: Model based application that
is not used as the structure
keyword queries: Formulation, methods, and analysis
D. Wu, M. L. Yiu, and C. S. Jensen
Moving Spatial are used as the top-k spatial keyword (MkSK) queries over
spatial text data
Advantage: Top k Spatial keyword is used.
Disadvantage: GPS is used & when no internet
the system cannot be used.
A framework for
efficient spatial web object retrieval
D. Wu, G. Cong, and C. S. Jensen
In this system spatial web are used which are top k query
with R Tree concepts
Advantage: R-tree for spatial proximity querying
Disadvantage: DIR-tree techniques are old.
P. Bouros, S. Ge, and N. Mamoulis
Our work is related to spatial distance joins, set-similarity
joins, and spatio-textual search.
Advantage: batch processing technique is used and
our methods exploit spatial indexing and pruning techniques to reduce the
space where the (more expensive) textual similarity predicate needs to be
verified; for the latter, they adapt the state-of-the-art algorithm for set
Disadvantage: It formally defines the ST-SJOIN
operation which are slow in processing
Table 1: Related work of different
Random walks on the click
craswell ,Martin Szummer
we have applied Markov random walk model to the click graph.
Advantage : 1.Easy to implement
2.No knowledge of underlying graph required
Disadvantage : 1.Unpredictable cover and
2.Worst case of infinite
Path Rank: A Novel Node Ranking Measure on a
Graph for Recommender Systems
S.Park ,M.kahng,and S.G. Lee
Advantage:It works on heterogeneous graph by extending personalize page
1.Complexity is more.
2.Worst case of infinite
LKS framework provides query suggestion
based on user’s current location and retrieve document that are close to user’s
location and retrieve relevant document. BA is extended from BCA to solve the problem. And also PA is used to
reduce the Computational cost of BCA .
It is my great pleasure to express my deep sense of
gratitude and specially thanks to my project guide Prof.M.R.Patil for her valuable
guidance inspiration and whole hearted involvement during every stage of this
survey. Her experience, perception and through professional Knowledge, being
available, Beyond the stipulated period of time for all kind of guidance and
supervision and ever-willing attitude to help, have greatly influenced the
timely and successful completion of this survey.
Baeza-Yates, C. Hurtado, and M. Mendoza, “Query recommendation using query logs
in search engines,”in Proc. . Int. Conf. Current Trends Database Technol,
Beeferman and A. Berger, “Agglomerative clustering of a search engine query
log,” in Proc. 6th ACM SIGKDD Int.Conf. Knowl. Discovery Data Mining, 2000,pp.
Cao, D. Jiang, J. Pei, Q. He, Z. Liao, E. Chen, and H.Li, “Context-aware query
suggestion by mining click-through and session data,” in Proc. 14th ACM SIGKDD
Int. Conf. Knowl. Discovery Data Mining, 2008, pp. 875–883.
Mei, D. Zhou, and K. Church, “Query suggestion using hitting time,” in Proc.
17th ACM Conf. Inf. Knowl Manage., 2008, pp. 469–478.
Song and L.-W. He, “Optimal rare query suggestion with implicit user feedback,”
in Proc. 19th Int. Conf. World Web, 2010, pp. 901–910.
6 T. Miyanishi and T. Sakai,
“Time-aware structured query
in Proc. 36th Int. ACM SIGIR Conf. Res.Develop Inf. Retrieval, 2013, pp.
7 P. Boldi, F. Bonchi, C.
Castillo, D. Donato, A. Gionis, and S. Vigna, “The query-flow graph: Model and
applications,” in Proc. 17th ACM
Conf. Inf. Knowl. Manage, 2008, pp. 609–618.
8 D. Wu, M. L. Yiu, and C. S. Jensen, “Moving
spatial keyword queries:
Formulation, methods, and analysis,” ACM Trans. Database Syst., vol. 38, no. 1, pp. 7:1–7:47, 2013.
D. Wu, G. Cong,
and C. S. Jensen, “A framework for efficient spatial web object retrieval,”
VLDB J., vol. 21, no. 6, pp. 797–822, 2012. J. Fan, G. Li, L. Zhou, S. Chen,
and J. Hu, “SEAL: Spatio-textual similarity search,” Proc. VLDB Endowment, vol.
5, no. 9, pp. 824 835, 2012.
10 P. Bouros, S. Ge, and N. Mamoulis,
“Spatio-textual similarity joins,” Proc. VLDB Endowment, vol. 6, no. 1, pp.
Lee, S. Park, M. Kahng, and S.-G. Lee, “PathRank: A novel node ranking measure
on a heterogeneous graph for recommender systems,”in Proc. 21st ACM Int. Conf.
Inf. Knowl. Manage., 2012, pp. 1637–1641
Craswell and M. Szummer, “Random walks on the click graph,” in Proc. 30th Annu.
Int. ACM SIGIR Conf. Res. Develop. Inf. Retrieval, 2007, pp. 239–246.