Discovering co-located queries in geographic search logs

ABSTRACT

A geographic search request contains a query consisting of one or more keywords, and a search-location that the user searches for. In this paper, we study the problem of discovering co-located queries, which are geographic search requests for nearby search-locations. One example co-located query pattern is {"shopping mall", "parking"}. This pattern indicates that people often search "shopping mall" and "parking" over locations close to one another. Co-located queries have many applications, such as query suggestion, location recommendation, and local advertisement. We formally define co-located query patterns and propose two approaches to mining the patterns. Our basic approach is based on an existing spatial mining algorithm. To find more specific co-located queries that only appear in specific regions, we propose a lattice based approach. It divides the geographic space into regions and mines patterns in each region. We also define a locality measure to categorize patterns into local and global. Experimental results show that the lattice based approach outperforms the basic approach in the number of patterns, the quality of patterns, and the proportion of local patterns.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: N. Cressie. Statistics for Spatial Data. 1991.
• 4: Silviu Cucerzan , Ryen W. White, Query suggestion based on user landing pages, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277953]
• 5: B. Davison, D. Deschenes, and D. Lewanda. Finding Relevant Website Queries. Proc. of WWW'2003, 2003.
• 6: Federico Michele Facca , Pier Luca Lanzi, Mining interesting knowledge from weblogs: a survey, Data & Knowledge Engineering, v.53 n.3, p.225-241, June 2005 [doi>10.1016/j.datak.2004.08.001]
• 7: B. Fonseca, P. Golgher, E. de Moura, B. Possas, and N. Ziviani. Discovering search engine related queries using association rules. Journal of Web Engineering, 2(4):215--227, 2004.
• 8: Jaiwei Han , Krzysztof Koperski , Nebojsa Stefanovic, GeoMiner: a system prototype for spatial data mining, ACM SIGMOD Record, v.26 n.2, p.553-556, June 1997
• 9: Yan Huang , Jian Pei , Hui Xiong, Mining Co-Location Patterns with Rare Events from Spatial Data Sets, Geoinformatica, v.10 n.3, p.239-260, September 2006 [doi>10.1007/s10707-006-9827-8]
• 10: Yan Huang , Shashi Shekhar , Hui Xiong, Discovering Colocation Patterns from Spatial Data Sets: A General Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1472-1485, December 2004 [doi>10.1109/TKDE.2004.90]
• 11: Lee Wang , Chuang Wang , Xing Xie , Josh Forman , Yansheng Lu , Wei-Ying Ma , Ying Li, Detecting dominant locations from search queries, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076107]
• 12: Yasuhiko Morimoto, Mining frequent neighboring class sets in spatial databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.353-358, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502564]
• 13: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 14: Y. S. J. D. S. Asadi, J. Xu and X. Zhou. Calculation of Target Locations for Web Resources. Proc. of WISE, pages 277--288, 2006.
• 15: M. Sanderson and J. Kohler. Analyzing geographic queries. In Proc. of the ACM SIGIR Workshop on GIR, 2004.
• 16: Jaideep Srivastava , Robert Cooley , Mukund Deshpande , Pang-Ning Tan, Web usage mining: discovery and applications of usage patterns from Web data, ACM SIGKDD Explorations Newsletter, v.1 n.2, January 2000 [doi>10.1145/846183.846188]
• 17: Xuanhui Wang , ChengXiang Zhai, Learn from web search logs to organize search results, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277759]
• 18: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 19: Xin Zhang , Nikos Mamoulis , David W. Cheung , Yutao Shou, Fast mining of spatial collocations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014095]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
co-location pattern, log mining, spatial data mining