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
Technical University of Munich
Contact
Maryam Pirmoradi

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.

Talk to an expert

Interested in learning more about this technology offer, exploring potential applications or discussing a possible collaboration? Get in touch to learn more.

Maryam Pirmoradi