The invention provides a backend method for fast pruning of range queries on trajectories and other geometric objects. Database objects are encoded as compact Bloom-filter-based signatures, while the query object is first expanded by a configurable distance buffer and converted into the same representation. This enables efficient bitwise elimination of incompatible candidates before exact similarity measures are evaluated. As a backend feature for processing motion data, its broad range of applications include mobility services, logistics, aviation, shipping, agriculture, and Industry 4.0.
Physical Sciences
Reference
b82034
IP right year
2022
IP status
EP and US Patent Applications Filed
Applicant

Challenge and innovation

The rapid growth of trajectory and geospatial data (e.g. navigation, traffic management, logistics and autonomous driving) is increasing the need for efficient similarity search and range query processing. However, exact distance measures such as Fréchet distance are computationally expensive, while conventional prefiltering methods based on minimum bounding rectangles or start/end points often fail when trajectories share similar spatial extent but differ in their actual path.

The invention introduces a scalable method for efficiently filtering and comparing geometric objects, particularly trajectories. Spatial objects are rasterized and encoded as compact Bloom-filter-based signatures. For a query, the reference trajectory is first expanded by a configurable distance buffer and converted into the same representation. Bitwise comparison then eliminates database objects whose indexed footprint is incompatible with the buffered query, before exact distance measures such as Fréchet distance are computed.