|
 |
On nearest neighbor indexing of nonlinear trajectories
Written by:
Charu C Aggarwal and
Dakshi Agrawal.
Citation:
Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, pages 252-259. ACM Press, 2003.
Copyright © (2003) by Association for Computing Machinery,
Inc. Permission to make digital or hard copies of part of all of this
work for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage. To
copy otherwise, to republish, to post on servers, or to redistribute to
lists, requires prior specific permission and/or a fee.
Abstract:
In recent years, the problem of indexing mobile objects has
assumed great importance because of its relevance to a wide variety
of applications. Most previous results in this area have proposed
indexing schemes for objects with linear trajectories in one or two
dimensions. In this paper, we present methods for indexing objects with
nonlinear trajectories. Specifically, we identify a useful condition
called the convex hull property and show that any trajectory satisfying
this condition can be indexed by storing a careful representation
of these objects in a traditional index structure. Since a wide
variety of relevant nonlinear trajectories satisfy this condition,
our result significantly expands the class of trajectories for which
nearest neighbor indexing schemes can be devised. We also show that
even though many non-linear trajectories do not satisfy the convex
hull condition, an approximate representation can often be found which
satisfies it. We discuss examples of techniques which can be utilized
to find representations that satisfy the convex hull property. We
present empirical results to demonstrate the effectiveness of our
indexing method.
|
|
United States
