Chen Jason Zhang
Lei Chen
Abstract
With the widespread use of geo-positioning services (GPS), GPS-based navigation systems have become ever more of an integral part of our daily lives. GPS-based navigation systems usually suggest multiple paths for any given pair of source and target, leaving users perplexed when trying to select the best one among them, namely the problem of best path selection. Too many suggested paths may jeopardize the usability of the recommendation data, and decrease user satisfaction. Although existing studies have already partially relieved this problem through integrating historical traffic logs or updating traffic conditions periodically, their solutions neglect the potential contribution of human experience.
In this paper, we resort to crowdsourcing to ease the pain of the best path selection. The first step of appropriately using the crowd is to ask proper questions. For the best path selection problem, simple questions (e.g. binary voting) over compete paths cannot be directly applied to road networks due to their being too complex for crowd workers. Thus, this paper makes the first contribution by designing two types of questions, namely Routing Query (RQ) and Binary Routing Query (BRQ), to ask the crowd to decide which direction to take at each road intersection. Furthermore, we propose a series of efficient algorithms to dynamically manage the questions in order to reduce the selection hardness within a limited budget. Finally, we compare the proposed methods against two baselines, and the effectiveness and efficiency of our proposals are verified by the results from simulations and experiments on a real-world crowdsourcing platform.
- Ravindra K Ahuja, Kurt Mehlhorn, James Orlin, and Robert E Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM (JACM), 37(2):213--223, 1990. Google Scholar
Digital Library
- Carlos Guestrin Andreas Krause. A note on the budgeted maximization of submodular functions. Technical report, School of Computer Science, Carnegie Mellon University, March 2005.Google Scholar
- Michael S. Bernstein, Joel Brandt, Robert C. Miller, and David R. Karger. Crowds in two seconds: enabling realtime crowd-powered interfaces. In UIST, pages 33--42, 2011. Google ScholarDigital Library
- Michael S. Bernstein, David R. Karger, Robert C. Miller, and Joel Brandt. Analytic methods for optimizing realtime crowdsourcing. CoRR, abs/1204.2995, 2012.Google Scholar
- Daren C. Brabham. Crowdsourcing as a model for problem solving an introduction and cases. Convergence February 2008 vol. 14 no. 1 75--90, 2008.Google ScholarCross Ref
- Zaiben Chen, Heng Tao Shen, and Xiaofang Zhou. Discovering popular routes from trajectories. In ICDE, pages 900--911, 2011. Google ScholarDigital Library
- Thomas M. Cover and Joy Thomas. Elements of Information Theory. Wiley, 1991. Google ScholarDigital Library
- A. Philip Dawid. Conditional independence in statistical theory. Journal of the Royal Statistical Society. Series B (Methodological), 41(1):1--31, 1979.Google ScholarCross Ref
- M. H. DeGroot and M. J. Schervish. Probability and Statistics. Addison-Wesley series in statistics. Addison-Wesley, 2002.Google Scholar
- AnHai Doan, Raghu Ramakrishnan, and Alon Y. Halevy. Crowdsourcing systems on the world-wide web. Commun. ACM, 54(4):86--96, 2011. Google ScholarDigital Library
- Amber Feng, Michael J. Franklin, Donald Kossmann, Tim Kraska, Samuel Madden, Sukriti Ramesh, Andrew Wang, and Reynold Xin. Crowddb: Query processing with the vldb crowd. PVLDB, 4(12):1387--1390, 2011.Google ScholarDigital Library
- Jinyang Gao, Xuan Liu, Beng Chin Ooi, Haixun Wang, and Gang Chen. An online cost sensitive decision-making method in crowdsourcing systems. In SIGMOD Conference, pages 217--228, 2013. Google ScholarDigital Library
- Stephen Guo, Aditya G. Parameswaran, and Hector Garcia-Molina. So who won?: dynamic max discovery with the crowd. In SIGMOD Conference, pages 385--396, 2012. Google ScholarDigital Library
- Ming Hua and Jian Pei. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In EDBT, pages 347--358, 2010. Google ScholarDigital Library
- H. V. Jagadish, Adriane Chapman, Aaron Elkiss, Magesh Jayapandian, Yunyao Li, Arnab Nandi, and Cong Yu. Making database systems usable. In SIGMOD Conference, pages 13--24, 2007. Google ScholarDigital Library
- Haim Kaplan, Ilia Lotosh, Tova Milo, and Slava Novgorodov. Answering planning queries with the crowd. PVLDB, 6(9):697--708, 2013. Google ScholarDigital Library
- Long Liu, Jin Xu, Stephen Shaoyi Liao, and Huapin Chen. A real-time personalized route recommendation system for self-drive tourists based on vehicle to vehicle communication. Expert Syst. Appl., 41(7):3409--3417, 2014. Google ScholarDigital Library
- Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M. Ni. Finding time period-based most frequent path in big trajectory data. In SIGMOD Conference, pages 713--724, 2013. Google ScholarDigital Library
- T. W. Malone, R. Laubacher, and C. Dellarocas. Harnessing crowds: Mapping the genome of collective intelligence. Research Paper No. 4732-09, MIT, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, USA, February 2009. Sloan Research Paper No. 4732-09.Google Scholar
- Ariel Orda and Raphael Rom. Distributed shortest-path protocols for time-dependent networks. Distributed Computing, 10(1):49--62, 1996. Google ScholarDigital Library
- Aditya G. Parameswaran, Hector Garcia-Molina, Hyunjung Park, Neoklis Polyzotis, Aditya Ramesh, and Jennifer Widom. Crowdscreen: algorithms for filtering data with humans. In SIGMOD Conference, pages 361--372, 2012. Google ScholarDigital Library
- Aditya G. Parameswaran and Neoklis Polyzotis. Answering queries using humans, algorithms and databases. In CIDR, pages 160--166, 2011.Google Scholar
- Aditya G. Parameswaran, Anish Das Sarma, Hector Garcia-Molina, Neoklis Polyzotis, and Jennifer Widom. Human-assisted graph search: it's okay to ask questions. PVLDB, 4(5):267--278, 2011. Google ScholarDigital Library
- Hyunjung Park and Jennifer Widom. Query optimization over crowdsourced data. PVLDB, 6(10):781--792, 2013. Google ScholarDigital Library
- Han Su, Kai Zheng, Jiamin Huang, Hoyoung Jeung, Lei Chen, and Xiaofang Zhou. Crowdplanner: A crowd-based route recommendation system. In ICDE, 2014.Google Scholar
- Hao Su, Jia Deng, and Li Fei-Fei. Crowdsourcing annotations for visual object detection. In AAAI Technical Report, 4th Human Computation Workshop, 2012.Google Scholar
- Jiannan Wang, Tim Kraska, Michael J. Franklin, and Jianhua Feng. Crowder: Crowdsourcing entity resolution. PVLDB, 5(11):1483--1494, 2012. Google ScholarDigital Library
- Steven Euijong Whang, Peter Lofgren, and Hector Garcia-Molina. Question selection for crowd entity resolution. PVLDB, 6(6):349--360, 2013. Google ScholarDigital Library
- Xiaokui Xiao, Bin Yao, and Feifei Li. Optimal location queries in road network databases. In ICDE, pages 804--815, 2011. Google ScholarDigital Library
- Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis, and Yufei Tao. Reverse nearest neighbors in large graphs. IEEE Trans. Knowl. Data Eng., 18(4):540--553, 2006. Google ScholarCross Ref
- Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. Driving with knowledge from the physical world. In KDD, pages 316--324, 2011. Google ScholarDigital Library
- Ye Yuan, Lei Chen, and Guoren Wang. Efficiently answering probability threshold-based shortest path queries over uncertain graphs. In DASFAA (1), pages 155--170, 2010. Google ScholarDigital Library
- Chen Zhang, Yongxin Tong, and Lei Chen. Where to: Crowd-aided path selection. http://ihome.ust.hk/~czhangad/whereto_tr.pdf.Google Scholar
Recommendations
Numerical Analysis of Tractor Accidents using Driving Simulator for Autonomous Driving Tractor
ICMRE'19: Proceedings of the 5th International Conference on Mechatronics and Robotics EngineeringAutonomous driving of automobiles is a hot research topic in recent years. The autonomous driving tractor also has been studied in the agricultural field as well as an autonomous driving automobile. On the other hand, tractor accidents frequently occur ...
Design of Test System on Nighttime Driving Behavior and ECG Characteristics of Long-distance Bus Drivers (I) - Test Design
ICIE '10: Proceedings of the 2010 WASE International Conference on Information Engineering - Volume 03For the safety issues of night long-distance bus drivers, a test system that real-time continuously acquires vehicles driving parameter, traffic environmental images as well as ECG physiological state of drivers under night-time driving conditions is ...
Evaluation of ACC vehicles in mixed traffic: lane change effects and sensitivity analysis
Almost every automobile company is producing vehicles with adaptive cruise control (ACC) system onboard that enables a vehicle to do automatic vehicle following in the longitudinal direction. The ACC system is designed for driver's comfort and safety ...
Comments