Scheduling queries to moving entities to certify many are distant from a region
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Zheng, Da Wei
issued: 2020-08-20T21:49:59Z
issued: 2020
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: Let e1, e2, . . . , en be a set of entities moving with bounded speed in d-dimensional space. At each time step, we can choose one entity to query to obtain its actual location. Our goal is to establish via these queries that many of the entities could not be at a fixed point called a beacon. By failing to query an entity, the set of its potential locations, called its uncertainty region, grows over time. We want to query to keep the number of uncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) as large as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neither can any query schedule. We describe query schedules that establish that the number of entities away from the beacon is a constant fraction of the maximum number that can be shown to be away from the beacon in the case where each entity is static that is, every query reveals that the entity has not moved. In the general setting we show additive upper and lower bounds on what can be attained by a query schedule.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/75616
note: Scheduling Queries to Moving Entities to Certify Many AreDistant From a RegionbyDa Wei ZhengB.Sc. University of British Columbia, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THEDEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)August 2020c© Da Wei Zheng, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduate andPostdoctoral Studies for acceptance, the thesis entitled:Scheduling Queries to Moving Entities to Certify Many Are Distant From a Regionsubmitted by Da Wei Zheng in partial fulfillment of the requirements for the degree of Master of Sciencein Computer Science.Examining Committee:Will Evans, Professor, Computer Science, UBCSupervisorDavid Kirkpatrick, Professor Emeritus, Computer Science, UBCSupervisory Committee MemberiiAbstractLet e1, e2, . . . , en be a set of entities moving with bounded speed in Rd. At each time step, we can chooseone entity to query to obtain its actual location. Our goal is to establish via these queries that many ofthe entities could not be at a fixed point in Rd called a beacon. By failing to query an entity, the set of itspotential locations, called its uncertainty region, grows over time. We want to query to keep the number ofuncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) aslarge as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neithercan any query schedule. We describe query schedules that establish that the number of entities away fromthe beacon is a constant fraction of the maximum number that can be shown to be away from the beacon inthe case where each entity is static that is, every query reveals that the entity has not moved. In the generalsetting we show additive upper and lower bounds on what can be attained by a query schedule.iiiLay SummaryConsider a radio network…
has type: Thesis/Dissertation
date issued: 2020-11
is shown at: 10.14288/1.0392883
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/75616