We address the problem of efficient maintenance of the answer to a new type of query: Continuous Maximizing Range- Sum (Co-MaxRS) for moving objects trajectories. The traditional static/spatial MaxRS problem finds a location for placing the centroid of a given (axes-parallel) rectangle R so that the sum of the weights of the point-objects from a given set O inside the interior of R is maximized. However, moving objects continuously change their locations over time, so the MaxRS solution for a particular time instant need not be a solution at another time instant. In this paper, we devise the conditions under which a particular MaxRS solution may cease to be valid and a new optimal location for the query-rectangle R is needed. More specifically, we solve the problem of maintaining the trajectory of the centroid of R. In addition, we propose efficient pruning strategies (and corresponding data structures) to speed-up the process of maintaining the accuracy of the Co-MaxRS solution. We prove the correctness of our approach and present experimental evaluations over both real and synthetic datasets, demonstrating the benefits of the proposed methods.
Class-based Conditional MaxRS Query in Spatial Data Streams
We address the problem of maintaining the correct answer-sets to
the Conditional Maximizing Range-Sum (C-MaxRS) query in spatial
data streams. Given a set of (possibly weighted) 2D point objects,
the traditional MaxRS problem determines an optimal placement for
an axes-parallel rectangle r so that the number – or, the weighted
sum – of objects in its interior is maximized. In many practical
settings, the objects from a particular set – e.g., restaurants – can be
of distinct types – e.g., fast-food, Asian, etc. The C-MaxRS problem
deals with maximizing the overall sum, given class-based existential
constraints, i.e., a lower bound on the count of objects of interests
from particular classes. We first propose an efficient algorithm
to the static C-MaxRS query, and extend the solution to handle
dynamic (data streams) settings. Our experiments over datasets
of up to 100,000 objects show that the proposed solutions provide
significant efficiency benefits.
- Award ID(s):
- 1646107
- Publication Date:
- NSF-PAR ID:
- 10040694
- Journal Name:
- Proceedings of the 29th International Conference on Scientific and Statistical Database Management, Chicago, IL, USA, June 27-29, 2017
- Page Range or eLocation-ID:
- 1 to 12
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a system for efficient detection, continuous maintenance and visualization of range-constrained optimal density clusters of moving objects trajectories, a.k.a. Continuous Maximizing Range Sum (Co-MaxRS) queries. Co-MaxRS is useful in any domain involving continuous detection of “most interesting” regions involving mobile entities (e.g., traffic monitoring, environmental tracking, etc.). Traditional MaxRS finds a location of a given rectangle R which maximizes the sum of the weighted-points (objects) in its interior. Since moving objects continuously change their locations, the MaxRS at a particular time instant need not be a solution at another time instant. Our system solves two important problems: (1) Efficiently computing Co-MaxRS answer-set; and (2) Visualizing the results. This demo will present the implementation of our efficient pruning schemes and compact data structures, and illustrate the end-user tools for specifying the parameters and selecting datasets for Co-MaxRS, along with visualization of the optimal locations.
-
We consider a collection of distributed sensor nodes periodically exchanging information to achieve real-time situa- tional awareness in a communication constrained setting, e.g., collaborative sensing amongst vehicles to enable safety-critical decisions. Nodes may be both consumers and producers of sensed information. Consumers express interest in information about particular locations, e.g., obstructed regions and/or road intersections, whilst producers provide updates on what they are currently able to see. Accordingly, we introduce and explore optimizing trade-offs between the coverage and the space-time average of the “age” of the information available to consumers. We consider two settings that capture the fundamental character of the problem. The first addresses selecting a subset of producers which optimizes a weighted sum of the coverage and the average age given that producers provide updates at a fixed rate. The second addresses the minimization of the weighted average age achieved by a fixed subset of producers with possibly overlapping coverage by optimizing their update rates. The former is shown to be submodular and thus amenable to greedy optimization while the latter has a non-convex/non-concave cost function which is amenable to effective optimization using tools such as the Frank- Wolfe algorithm. Numerical results exhibit the benefits of context dependentmore »
-
We address the problem of in-network processing of k-Maximizing Range Sum (k-MaxRS) queries inWireless Sensor Networks (WSN). The traditional, Computational Geometry version of the MaxRS problem considers the setting in which, given a set of (possibly weighted) 2D points, the goal is to determine the optimal location for a given (axes-parallel) rectangle R to be placed so that the sum of the weights (or, a simple count) of the input points in R’s interior is maximized. In WSN, this corresponds to finding the location of region R such that the sum of the sensors’ readings inside R is maximized. The k-MaxRS problem deals with maximizing the overall sum over k such rectangular regions. Since centralized processing – i.e., transmitting the raw readings and subsequently determining the k-MaxRS in a dedicated sink – incur communication overheads, we devised an efficient distributed algorithm for in-network computation of k-MaxRS. Our experimental observations show that the novel algorithm provides significant energy/communication savings when compared to the centralized approach.
-
Next-generation distributed computing networks (e.g., edge and fog computing) enable the efficient delivery of delay-sensitive, compute-intensive applications by facilitating access to computation resources in close proximity to end users. Many of these applications (e.g., augmented/virtual reality) are also data-intensive: in addition to user-specific (live) data streams, they require access to shared (static) digital objects (e.g., im-age database) to complete the required processing tasks. When required objects are not available at the servers hosting the associated service functions, they must be fetched from other edge locations, incurring additional communication cost and latency. In such settings, overall service delivery performance shall benefit from jointly optimized decisions around (i) routing paths and processing locations for live data streams, together with (ii) cache selection and distribution paths for associated digital objects. In this paper, we address the problem of dynamic control of data-intensive services over edge cloud networks. We characterize the network stability region and design the first throughput-optimal control policy that coordinates processing and routing decisions for both live and static data-streams. Numerical results demonstrate the superior performance (e.g., throughput, delay, and resource consumption) obtained via the novel multi-pipeline flow control mechanism of the proposed policy, compared with state-of-the-art algorithms that lack integratedmore »
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Publisher's Version of Record
- https://doi.org/10.1145/3085504.3085517
