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.
more »
« less
Distributed In-Network Processing of k-MaxRS in Wireless Sensor Networks
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.
more »
« less
- Award ID(s):
- 1646107
- NSF-PAR ID:
- 10040590
- Date Published:
- Journal Name:
- Proceedings of the 6th International Conference on Sensor Networks (SENSORNETS 2017), Porto, Portugal, February 19-21, 2017
- Page Range / eLocation ID:
- 108 to 117
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
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.more » « less
-
This work addresses a novel variant of the Maximum Range-Sum (MaxRS) query for settings in which spatial point objects occur dynamically and, upon occurrence, their significance (i.e., weight) decays over time. The objective of the original MaxRS query is to find a location to place (the centroid of) a fixed-size spatial rectangle so that the sum of the weights of the point objects in its interior is maximized. The unique aspect of the problem studied in this paper, which we call DDW-MaxRS (Dynamic and Decaying Weights MaxRS), is that the placement of its solution can vary over time due to the joint impact of the arrival of new objects and the change of the corresponding weights of the existing objects over time. To improve the efficiency of the DDW-MaxRS problem processing, we propose a memory-efficient approximate algorithmic solution that will naturally infuse uncertainty in the answer. We formally analyze the error bounds’ properties and provide experimental results to quantify the effectiveness of the proposed approach.more » « less
-
Evans, Robin ; Shpitser, Ilya (Ed.)We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: \SCSKC and \DiffC. Given two submodular functions $f$ and $g$ where $f$ is monotone, the objective of \SCSKC problem is to find a set $S$ of size at most $k$ that maximizes $f(S)$ under the constraint that $g(S)\leq \theta$, for a given value of $\theta$. The problem of \DiffC focuses on finding a set $S$ of size at most $k$ such that $h(S) = f(S)-g(S)$ is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of \SCSKC, we prove that the greedy algorithm produces a solution whose value is at least $(1-1/e)f(\OPT) - A$, where $A$ is the data-dependent additive error. For the \DiffC problem, we design an algorithm that uses the \SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least $(1-1/e)h(\OPT)-B$, where $B$ is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.5220/0006210701080117
