Mohammad Mahdian
ABSTRACT
We study the problem of selecting a set of points of interest (POIs) to show on a map. We begin with a formal model of the setting, noting that the utility of a POI may be discounted by (i) the presence of competing businesses nearby as well as (ii) its position in the set of establishments ordered by distance from the user. We present simple, approximately optimal selection algorithms, coupled with incentive compatible pricing schemes in case of advertiser supplied points of interest. Finally, we evaluate our algorithms on real data sets and show that they outperform simple baselines.
Supplemental Material
- Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, and Martin Pál. Sponsored search auctions with markovian users. In Christos Papadimitriou and Shuzhong Zhang, editors, Internet and Network Economics, volume 5385 of Lecture Notes in Computer Science, pages 621--628. Springer Berlin Heidelberg, 2008. Google Scholar
Digital Library
- Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. Diversifying search results. In Proceedings of the Second ACM International Conference on Web Search and Data Mining, WSDM '09, pages 5--14, 2009. Google ScholarDigital Library
- Aaron Archer and Éva Tardos. Truthful mechanisms for one-parameter agents. Proceedings of 42th Annual Symposium on Foundations of Computer Science (FOCS), pages 482--491, 2001. Google ScholarDigital Library
- Moshe Babaioff and Liad Blumrosen. Computationally-feasible truthful auctions for convex bundles. Games and Economic Behavior, 63(2):588--620, 2008.Google ScholarCross Ref
- Saeideh Bakhshi, Partha Kanuparthy, and Eric Gilbert. Demographics, weather and online reviews: A study of restaurant recommendations. In Proceedings of the 23rd International Conference on World Wide Web, WWW '14, pages 443--454, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- Tony Bradley. Google maps ads are a big opportunity for local businesses. PC World (August 9, 2013). www.pcworld.com/article/2046292/google-maps-ads-are-a-big-opportunity-for-local-businesses.html.Google Scholar
- Cartography and Geographic Information Society. Cagis map design competition. http://www.cartogis.org/awards/contest.php, 2013.Google Scholar
- Arpita Ghosh and Mohammad Mahdian. Externalities in online advertising. In Proceedings of the 17th international conference on World Wide Web, pages 161--168. ACM, 2008. Google ScholarDigital Library
- Arpita Ghosh and Amin Sayedi. Expressive auctions for externalities in online advertising. In Proceedings of the 19th international conference on World wide web, pages 371--380. ACM, 2010. Google ScholarDigital Library
- Sreenivas Gollapudi and Aneesh Sharma. An axiomatic approach for result diversification. In WWW '09: Proceedings of the 18th international conference on World wide web, pages 381--390, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- Renato Gomes, Nicole Immorlica, and Evangelos Markakis. Externalities in keyword auctions: An empirical and theoretical assessment. In Stefano Leonardi, editor, Internet and Network Economics, volume 5929 of Lecture Notes in Computer Science, pages 172--183. Springer Berlin Heidelberg, 2009. Google ScholarDigital Library
- Samuel Ieong, Mohammad Mahdian, and Sergei Vassilvitskii. Advertising in a stream. In Proceedings of the 23rd International Conference on World Wide Web, WWW '14, pages 29--38, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- David Kempe and Mohammad Mahdian. A cascade model for externalities in sponsored search. In Internet and Network Economics, pages 585--596. Springer, 2008. Google ScholarDigital Library
- Ravi Kumar, Mohammad Mahdian, Bo Pang, Andrew Tomkins, and Sergei Vassilvitskii. Modeling geographic choice. In Proceedings of the 8th International Conference on Web Search and Data Mining (WSDM), 2015. Google ScholarDigital Library
- Stephanie Meece. A bird's eye view of a leopard's spots. the Çatalhöyük 'map' and the development of cartographic representation in prehistory. https://www.repository.cam.ac.uk/handle/1810/195777, 2008.Google Scholar
- Roger Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981. Google ScholarDigital Library
- Anastasios Noulas, Salvatore Scellato, Renaud Lambiotte, Massimiliano Pontil, and Cecilia Mascolo. A tale of many cities: Universal patterns in human urban mobility. PLoS ONE, 7(5):e37027, 05 2012.Google ScholarCross Ref
- Anish Das Sarma, Hongrae Lee, Hector Gonzalez, Jayant Madhavan, and Alon Halevy. Consistent thinning of large geographical data for map visualization. ACM Trans. Database Syst., 38(4):22:1--22:35, December 2013. Google ScholarDigital Library
- Greg Sterling. Google introduces offline maps for mobile, claims a billion users globally for maps, earth. Search Engine Land weblog (June 6, 2012). http://searchengineland.com/live-blogging-the-google-maps-next-dimension-event-123617, 2012.Google Scholar
- Jennifer van Grove. Marissa Mayer: Google will connect the digital and physical worlds through mobile. Mashable weblog (March 11, 2011). http://mashable.com/2011/03/11/mayer-sxsw-talk/, 2011.Google Scholar
- Wikipedia. Babylonian map of the world. http://en.wikipedia.org/wiki/Babylonian_Map_of_the_World, 2014.Google Scholar
Index Terms
- Algorithmic Cartography: Placing Points of Interest and Ads on Maps
Recommendations
TimeMachine: Timeline Generation for Knowledge-Base Entities
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningWe present a method called TIMEMACHINE to generate a timeline of events and relations for entities in a knowledge base. For example for an actor, such a timeline should show the most important professional and personal milestones and relationships such ...
Efficient Algorithms for Public-Private Social Networks
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningWe introduce the public-private model of graphs. In this model, we have a public graph and each node in the public graph has an associated private graph. The motivation for studying this model stems from social networks, where the nodes are the users, ...
Unified and Contrasting Cuts in Multiple Graphs: Application to Medical Imaging Segmentation
KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data MiningThe analysis of data represented as graphs is common having wide scale applications from social networks to medical imaging. A popular analysis is to cut the graph so that the disjoint subgraphs can represent communities (for social network) or ...
Comments