Show simple item record

dc.contributor.author
Tong, Yongxin
dc.contributor.author
Wang, Libin
dc.contributor.author
Zimu, Zhou
dc.contributor.author
Ding, Bolin
dc.contributor.author
Chen, Lei
dc.contributor.author
Ye, Jieping
dc.contributor.author
Xu, Ke
dc.date.accessioned
2018-01-30T11:29:26Z
dc.date.available
2017-12-05T07:59:24Z
dc.date.available
2018-01-10T08:46:34Z
dc.date.available
2018-01-10T09:30:52Z
dc.date.available
2018-01-10T13:43:55Z
dc.date.available
2018-01-30T11:29:26Z
dc.date.issued
2017-08
dc.identifier.issn
2150-8097
dc.identifier.other
10.14778/3137628.3137643
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/217177
dc.identifier.doi
10.3929/ethz-b-000217177
dc.description.abstract
The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem Flexible Two-sided Online task Assignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers’ movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, Prediction-oriented Online task Assignment in Real-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Association of Computing Machinery
en_US
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.title
Flexible Online Task Assignment in Real-Time Spatial Data
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
ethz.journal.title
Proceedings of the VLDB Endowment
ethz.journal.volume
10
en_US
ethz.journal.issue
11
en_US
ethz.journal.abbreviated
Proc. VLDB Endow.
ethz.pages.start
1334
en_US
ethz.pages.end
1345
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03429 - Thiele, Lothar / Thiele, Lothar
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03429 - Thiele, Lothar / Thiele, Lothar
en_US
ethz.date.deposited
2017-12-05T07:59:26Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-01-10T08:46:38Z
ethz.rosetta.lastUpdated
2018-11-06T07:39:17Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Flexible%20Online%20Task%20Assignment%20in%20Real-Time%20Spatial%20Data&rft.jtitle=Proceedings%20of%20the%20VLDB%20Endowment&rft.date=2017-08&rft.volume=10&rft.issue=11&rft.spage=1334&rft.epage=1345&rft.issn=2150-8097&rft.au=Tong,%20Yongxin&Wang,%20Libin&Zimu,%20Zhou&Ding,%20Bolin&Chen,%20Lei&rft.genre=article&
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record