File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Towards Efficient MaxBRNN Computation for Streaming Updates

TitleTowards Efficient MaxBRNN Computation for Streaming Updates
Authors
Issue Date2021
PublisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178
Citation
IEEE 37th International Conference on Data Engineering (ICDE) 2021, Chania, Greece, 19-22 April 2021, p. 2297-2302 How to Cite?
AbstractIn this paper, we propose the streaming MaxBRNNquery, which finds the optimal region to deploy a new service point when both the service points and client points are under continuous updates. The streaming MaxBRNN query has many applications such as taxi scheduling, shared bike placements, etc. Existing MaxBRNN solutions are insufficient for streaming updates as they need to re-run from scratch even for a small amount of updates, resulting in long query processing time. To tackle this problem, we devise an efficient slot partitioning-based algorithm (SlotP), which divides the space into equal-sized slots and processes each slot independently. The superiorities of our proposal for streaming MaxBRNN query are: (i) an update affects only a smaller number of slots and works done on the unaffected slots can be reused directly; (ii) the influence value upper bound of each slot can be derived efficiently and accurately, which facilitate pruning many slots from expensive computation. We conducted extensive experiments to validate the performance of the SlotP algorithm. The results show that SlotP is 2-3 orders of magnitude faster than state-of-the-art baselines.
Persistent Identifierhttp://hdl.handle.net/10722/305495
ISSN
2023 SCImago Journal Rankings: 1.306
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorNing, W-
dc.contributor.authorYan, X-
dc.contributor.authorTang, B-
dc.date.accessioned2021-10-20T10:10:12Z-
dc.date.available2021-10-20T10:10:12Z-
dc.date.issued2021-
dc.identifier.citationIEEE 37th International Conference on Data Engineering (ICDE) 2021, Chania, Greece, 19-22 April 2021, p. 2297-2302-
dc.identifier.issn1084-4627-
dc.identifier.urihttp://hdl.handle.net/10722/305495-
dc.description.abstractIn this paper, we propose the streaming MaxBRNNquery, which finds the optimal region to deploy a new service point when both the service points and client points are under continuous updates. The streaming MaxBRNN query has many applications such as taxi scheduling, shared bike placements, etc. Existing MaxBRNN solutions are insufficient for streaming updates as they need to re-run from scratch even for a small amount of updates, resulting in long query processing time. To tackle this problem, we devise an efficient slot partitioning-based algorithm (SlotP), which divides the space into equal-sized slots and processes each slot independently. The superiorities of our proposal for streaming MaxBRNN query are: (i) an update affects only a smaller number of slots and works done on the unaffected slots can be reused directly; (ii) the influence value upper bound of each slot can be derived efficiently and accurately, which facilitate pruning many slots from expensive computation. We conducted extensive experiments to validate the performance of the SlotP algorithm. The results show that SlotP is 2-3 orders of magnitude faster than state-of-the-art baselines.-
dc.languageeng-
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000178-
dc.relation.ispartofInternational Conference on Data Engineering. Proceedings-
dc.rightsInternational Conference on Data Engineering. Proceedings. Copyright © IEEE Computer Society.-
dc.rights©2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.titleTowards Efficient MaxBRNN Computation for Streaming Updates-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/ICDE51399.2021.00240-
dc.identifier.scopuseid_2-s2.0-85112869043-
dc.identifier.hkuros327022-
dc.identifier.spage2297-
dc.identifier.epage2302-
dc.identifier.isiWOS:000687830800232-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats