Variants of MaxRS Queries for Trajectories, Shapes and Spatial Data Streams

Mas-ud Hussain, Muhammed

doi:https://doi.org/10.21985/n2-t6k6-ev36

Work

Variants of MaxRS Queries for Trajectories, Shapes and Spatial Data Streams

Public

Download PDF

Download All Files (.zip)

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 dissertation work, 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. As in many real-world applications, trajectories data sets need to reside on a secondary storage or even on cloud, a sequential access to the whole trajectories is inefficient. To resolve this, we devise a hierarchical grid-based index structure which can be built on-the-fly and maintained via KDS. Moreover, there are many scenarios where a fast response to the query is necessary, and an approximate solution that is closer to the current MaxRS solution is preferred. Thus, we present a novel approximation algorithm (with a bound on the approximation ratio) for the Co-MaxRS problem using the grid-based partitioning system. We prove the correctness of our approach and present experimental evaluations over both real and synthetic datasets, demonstrating the benefits of the proposed methods. Moreover, we also address the problem of maintaining the correct answer-sets to the \textit{Conditional Maximizing Range-Sum} (C-MaxRS) query in spatial data streams. In many practical settings, the objects from a particular set -- e.g., restaurants -- can be of different types -- e.g., fast-food, Asian, etc. The C-MaxRS problem deals with maximizing the overall sum -- however, it also incorporates class-based constraints, i.e., placement of $r$ such that a lower bound on the count/weighted-sum of objects of interests from particular classes is ensured. We first propose an efficient algorithm to handle the static C-MaxRS query and then extend the solution in an event-based manner to handle dynamic (data streams) settings. Subsequently, we turn our attention to the case of bursty streaming inputs, which is common in many applications, -- e.g., thousands of users go online (or, offline) at (or, nearly) the same time in large social networks such as Facebook. We show that dealing with events one by one is not efficient when processing bursty inputs and present a novel technique to cater to such scenarios, by creating an index over the bursty data on-the-fly and processing the collection of events in an aggregate manner. Our experiments over datasets of up to 100,000 objects show that the proposed solutions provide significant efficiency benefits over the na{\"i}ve approaches. Finally, we investigate another novel variant of the well-known MaxRS (Maximizing Range Sum) problem -- namely, the MAxRS$^3$ (Maximizing Area-Range Sum for Spatial Shapes). As we've already mentioned, the MaxRS problem amounts to detecting a location where a fixed-size rectangle $R$ should be placed, so that it covers a maximum number of points -- or sum of weights, if the points are weighted -- from a given input set of 2D points. While variants have tackled the settings in which the input set to MaxRS problem consists of polygons instead of points -- the solution is still based on (weighted) count. We postulate that in many practical applications it is of interest to determine where to place the input rectangle so that the total area-coverage in its interior is maximized. In this work, we formalize the MAxRS$^3$ problem and propose (to our knowledge) the first solution to this new problem.

Creator