Browsing by Subject "Spatial query processing"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Geometric search on point-tuples
    (2016-06) Agrawal, Akash
    Computational geometry is a branch of computer science that deals with the algorithmic aspects of geometric problems. Nearest neighbor search and range search are two fundamental geometric search problems in computational geometry. Despite the long history of these problems, the majority of the research until now has been focused on simple objects such as points. However, many applications such as trip planning under budget constraint, routing, task allocation, wireless sensor networks, etc. require querying more complex objects, such as point-tuples, that are created at the query time. Motivated by such considerations, this dissertation is devoted to the design of efficient algorithms and data structures for a relatively new class of geometric search problems where the goal is to report point-tuples that satisfy certain query constraints. Given several disjoint sets of points with an ordering of the sets, two fundamental search problems are addressed. The first problem is a point-tuple version of the nearest neighbor search problem, where the goal is to report the ordered sequence (i.e., tuple) of points (one per set and consistent with the given ordering of the sets) such that the total distance traveled starting from a query point q and visiting the points of the tuple in the specified order is minimum. The second problem is a point-tuple version of the range search problem, where, for a distance constraint δ, the goal is to report all the tuples of points (again, one per set and consistent with the given ordering of the sets) such that, for each tuple, the total distance traveled starting from q and visiting the points of the tuple is no more than δ. In many applications, the points also have feature attributes in addition to spatial attributes (coordinates). For such datasets, three extensions of the point-tuple version of the range search problem are also studied. These extensions differ in the type of constraint applied on the output tuples, as dictated by the underlying application. The first extension applies range constraints on the feature attribute values. The second extension applies a threshold constraint on the scores of the tuples, computed from the feature attribute values using an aggregation function (e.g., sum, product, etc.). Finally, the third extension seeks the so-called skyline of the output tuples based on the feature attribute values.