skip to main content
10.1145/2433396.2433485acmconferencesArticle/Chapter ViewAbstractPublication PageswsdmConference Proceedingsconference-collections
research-article

Learning to rank for spatiotemporal search

Published: 04 February 2013 Publication History

Abstract

In this article we consider the problem of mapping a noisy estimate of a user's current location to a semantically meaningful point of interest, such as a home, restaurant, or store. Despite the poor accuracy of GPS on current mobile devices and the relatively high density of places in urban areas, it is possible to predict a user's location with considerable precision by explicitly modeling both places and users and by combining a variety of signals about a user's current context. Places are often simply modeled as a single latitude and longitude when in fact they are complex entities existing in both space and time and shaped by the millions of people that interact with them. Similarly, models of users reveal complex but predictable patterns of mobility that can be exploited for this task. We propose a novel spatial search algorithm that infers a user's location by combining aggregate signals mined from billions of foursquare check-ins with real-time contextual information. We evaluate a variety of techniques and demonstrate that machine learning algorithms for ranking and spatiotemporal models of places and users offer significant improvement over common methods for location search based on distance and popularity.

References

[1]
foursquare API. http://developer.foursquare.com.
[2]
Geonames.org reverse geocoding services. http://www.geonames.org/export/reverse-geocoding.html.
[3]
Ranklib. http://people.cs.umass.edu/~vdang/ranklib.html.
[4]
The World in 2011 -- ICT Facts and Figures. http://www.itu.int/ITU-D/ict/facts/2011/material/ICTFactsFigures2011.pdf.
[5]
E. Amitay, N. Har'El, R. Sivan, and A. Soffer. Web-a-where: geotagging web content. In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 273--280. ACM, 2004.
[6]
D. Ashbrook and T. Starner. Learning significant locations and predicting user movement with gps. In Proceedings of the Sixth International Symposium on Wearable Computers. (ISWC 2002)., pages 101--108. IEEE, 2002.
[7]
D. Ashbrook and T. Starner. Using gps to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing, 7(5):275--286, 2003.
[8]
Lars Backstrom, Eric Sun, and Cameron Marlow. Find me if you can: improving geographical prediction with social and spatial proximity. In Proceedings of the 19th international conference on World wide web, WWW'10, pages 61--70, New York, NY, USA, 2010. ACM.
[9]
Z. Cheng, J. Caverlee, and K. Lee. You are where you tweet: a content-based approach to geo-locating twitter users. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, pages 759--768. ACM, 2010.
[10]
K. Church and B. Smyth. Who, what, where & when: a new approach to mobile search. In Proceedings of the 13th International Conference on Intelligent User Interfaces, pages 309--312. ACM, 2008.
[11]
C. Fink, C. Piatko, J. Mayfield, T. Finin, and J. Martineau. Geolocating blogs from their textual content. In Working Notes of the AAAI Spring Symposium on Social Semantic Web: Where Web 2.0 Meets Web 3.0. AAAI Press, 2009.
[12]
J. Fürnkranz and E. Hüllermeier. Pairwise preference learning and ranking. Machine Learning: ECML 2003, pages 145--156, 2003.
[13]
M.C. Gonzalez, C.A. Hidalgo, and A.L. Barabási. Understanding individual human mobility patterns. Nature, 453(7196):779--782, 2008.
[14]
K. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR'00, pages 41--48. ACM, 2000.
[15]
T. Joachims, L. Granka, Bing Pan, H. Hembrooke, F. Radlinski, and G. Gay. Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search. ACM Transactions on Information Systems (TOIS), 25(2), April 2007.
[16]
T. Joachims, L. Granka, B. Pang, H. Hembrooke, and G. Gay. Accurately interpreting clickthrough data as implicit feedback. In Proceedings of the 28th International ACM SIGIR Conference on Research and Development in Information, pages 154--161, 2005.
[17]
N.D. Lane, D. Lymberopoulos, F. Zhao, and A.T. Campbell. Hapori: context-based local search for mobile phones using community behavioral modeling and similarity. In Proceedings of the 12th ACM International Conference on Ubiquitous Computing, pages 109--118. ACM, 2010.
[18]
D. Lian and X. Xie. Learning location naming from user check-in histories. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 112--121. ACM, 2011.
[19]
L. Liao, D. Fox, and H. Kautz. Extracting places and activities from gps traces using hierarchical conditional random fields. The International Journal of Robotics Research, 26(1):119--134, 2007.
[20]
A. Lima M. De~Domenico and M/~Musolesi. Interdependence and predictability of human mobility and social interactions. Proceedings of the Nokia Mobile Data Challenge Workshop, June 2012.
[21]
N. Marmasse and C. Schmandt. Location-aware information delivery with commotion. In Handheld and Ubiquitous Computing, pages 361--370. Springer, 2000.
[22]
Donald Metzler and W. Bruce~Croft. Linear feature-based models for information retrieval. Information Retrieval, 10(3):257--274, June 2007.
[23]
T.K. Moon. The expectation-maximization algorithm. Signal Processing Magazine, IEEE, 13(6):47--60, 1996.
[24]
M. Odersky, P. Altherr, V. Cremet, B. Emir, S. Maneth, S. Micheloud, N. Mihaylov, M. Schinz, E. Stenman, and M. Zenger. An overview of the scala programming language. Technical report, Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.
[25]
C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. Pig latin: a not-so-foreign language for data processing. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD'08. ACM, 2008.
[26]
F. Radlinski and T. Joachims. Minimally invasive randomization for collecting unbiased preferences from clickthrough logs. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 1406--1412, 2006.
[27]
M. Richardson, A. Prakash, and E. Brill. Beyond pagerank: machine learning for static ranking. In Proceedings of the 15th International World Wide Web Conference (WWW), pages 707--715. ACM, 2006.
[28]
Adam Sadilek, Henry Kautz, and Jeffrey~P. Bigham. Finding your friends and following them to where you are. In Proceedings of the fifth ACM international conference on Web search and data mining, WSDM'12, pages 723--732, New York, NY, USA, 2012. ACM.
[29]
P. Serdyukov, V. Murdock, and R. Van~Zwol. Placing flickr photos on a map. In Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 484--491. ACM, 2009.
[30]
M. Terry, E.D. Mynatt, K. Ryall, and D. Leigh. Social net: using patterns of physical proximity over time to infer shared interests. In CHI'02 Extended Abstracts on Human Factors in Computing Systems, pages 816--817. ACM, 2002.
[31]
M. A. Vasconcelos, S. Ricci, J. Almeida, F. Benevenuto, and V. Almeida. Tips, dones and todos: uncovering user profiles in foursquare. In Proceedings of the Fifth ACM International Conference on Web Search and Data Mining, WSDM'12, pages 653--662, New York, NY, USA, 2012. ACM.
[32]
Petros Venetis, Hector Gonzalez, Christian~S. Jensen, and Alon Halevy. Hyper-local, directions-based ranking of places. Proc. VLDB Endow., 4(5):290--301, February 2011.
[33]
Q. Wu, C. J. Burges, K. M. Svore, and J. Gao. Adapting boosting for information retrieval measures. Information Retrieval, 13(3):254--270, June 2010.
[34]
J. Yi, F. Maghoul, and J. Pedersen. Deciphering mobile search patterns: a study of yahoo! mobile search queries. In Proceeding of the 17th International World Wide Web Conference (WWW), pages 257--266. ACM, 2008.
[35]
P.A. Zandbergen. Accuracy of iPhone locations: A comparison of assisted GPS, WiFi and cellular positioning. Transactions in GIS, 13:5--25, 2009.

Cited By

View all
  • (2024)Privacy Leakage From Dynamic Prices: Trip Purpose Mining as an ExampleIEEE Transactions on Mobile Computing10.1109/TMC.2024.340841923:12(12378-12395)Online publication date: Dec-2024
  • (2024)BERT-Based Movie Keyword Search Leveraging User-Generated Movie Rankings and Reviews2024 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BigComp60711.2024.00046(246-256)Online publication date: 18-Feb-2024
  • (2023)Lambretta: Learning to Rank for Twitter Soft Moderation2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179392(311-326)Online publication date: May-2023
  • Show More Cited By

Index Terms

  1. Learning to rank for spatiotemporal search

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining
    February 2013
    816 pages
    ISBN:9781450318693
    DOI:10.1145/2433396
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 04 February 2013

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. data mining
    2. foursquare
    3. geocoding
    4. human mobility
    5. information retrieval
    6. learn to rank
    7. location data
    8. machine learning
    9. mobile devices
    10. spatial search
    11. spatiotemporal models

    Qualifiers

    • Research-article

    Conference

    WSDM 2013

    Acceptance Rates

    Overall Acceptance Rate 498 of 2,863 submissions, 17%

    Upcoming Conference

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Privacy Leakage From Dynamic Prices: Trip Purpose Mining as an ExampleIEEE Transactions on Mobile Computing10.1109/TMC.2024.340841923:12(12378-12395)Online publication date: Dec-2024
    • (2024)BERT-Based Movie Keyword Search Leveraging User-Generated Movie Rankings and Reviews2024 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BigComp60711.2024.00046(246-256)Online publication date: 18-Feb-2024
    • (2023)Lambretta: Learning to Rank for Twitter Soft Moderation2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179392(311-326)Online publication date: May-2023
    • (2023)On-device Deep Learning Location Category Inference ModelArtificial Intelligence and Machine Learning10.1007/978-3-031-39144-6_7(96-111)Online publication date: 4-Aug-2023
    • (2021)Seasonal Relevance in E-Commerce SearchProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3481951(4293-4301)Online publication date: 26-Oct-2021
    • (2021)Object Tracking by the Least Spatiotemporal SearchesIEEE Internet of Things Journal10.1109/JIOT.2021.30637798:16(12934-12946)Online publication date: 15-Aug-2021
    • (2021)Validating Gravity-Based Market Share Models Using Large-Scale Transactional DataBig Data10.1089/big.2020.01619:3(188-202)Online publication date: 1-Jun-2021
    • (2021)Getting Your Package to the Right Place: Supervised Machine Learning for GeolocationMachine Learning and Knowledge Discovery in Databases. Applied Data Science Track10.1007/978-3-030-86514-6_25(403-419)Online publication date: 13-Sep-2021
    • (2020)Learning to rank spatio-temporal event hotspotsCrime Science10.1186/s40163-020-00112-x9:1Online publication date: 20-Mar-2020
    • (2020)End-to-End Neural Matching for Semantic Location Prediction of TweetsACM Transactions on Information Systems10.1145/341514939:1(1-35)Online publication date: 5-Sep-2020
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media