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
Towards Efficient Maintenance of Continuous MaxRS Query for Trajectories
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
- Award ID(s):
- 1646107
- NSF-PAR ID:
- 10040589
- Date Published:
- Journal Name:
- Proceedings of the 20th International Conference on Extending Database Technology, {EDBT} 2017, Venice, Italy, March 21-24, 2017
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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 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
-
A region \(\mathcal {R} \) is a dwell region for a moving object O if, given a threshold distance r q and duration τ q , every point of \(\mathcal {R} \) remains within distance r q from O for at least time τ q . Points within \(\mathcal {R} \) are likely to be of interest to O , so identification of dwell regions has applications such as monitoring and surveillance. We first present a logarithmic-time online algorithm to find dwell regions in an incoming stream of object positions. Our method maintains the upper and lower bounds for the radius of the smallest circle enclosing the object positions, thereby greatly reducing the number of trajectory points needed to evaluate the query. It approximates the radius of the smallest circle enclosing a given subtrajectory within an arbitrarily small user-defined factor, and is also able to efficiently answer decision queries asking whether or not a dwell region exists. For the offline version of the dwell region problem, we first extend our online approach to develop the ρ -Index, which indexes subtrajectories using query radius ranges. We then refine this approach to obtain the τ -Index, which indexes subtrajectories using both query radius ranges and dwell durations. Our experiments using both real-world and synthetic datasets show that the online approach can scale up to hundreds of thousands of moving objects. For archived trajectories, our indexing approaches speed up queries by many orders of magnitude.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.5441/002/edbt.2017.36
