An official website of the United States government
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
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.
more »
« less
- Award ID(s):
- 1646107
- PAR ID:
- 10040694
- Date Published:
- Journal Name:
- Proceedings of the 29th International Conference on Scientific and Statistical Database Management, Chicago, IL, USA, June 27-29, 2017
- Page Range / eLocation ID:
- 1 to 12
- Format(s):
- Medium: X
- 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.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
-
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
-
How can we collect the most useful labels to learn a model selection policy, when presented with arbitrary heterogeneous data streams? In this paper, we formulate this task as a contextual active model selection problem, where at each round the learner receives an unlabeled data point along with a context. The goal is to output the best model for any given context without obtaining an excessive amount of labels. In particular, we focus on the task of selecting pre-trained classifiers, and propose a contextual active model selection algorithm (CAMS), which relies on a novel uncertainty sampling query criterion defined on a given policy class for adaptive model selection. In comparison to prior art, our algorithm does not assume a globally optimal model. We provide rigorous theoretical analysis for the regret and query complexity under both adversarial and stochastic settings. Our experiments on several benchmark classification datasets demonstrate the algorithm’s effectiveness in terms of both regret and query complexity. Notably, to achieve the same accuracy, CAMS incurs less than 10% of the label cost when compared to the best online model selection baselines on CIFAR10.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3085504.3085517
