BACR: Set similarities with lower bounds and application to spatial trajectories

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

8 Zitate (Scopus)

Abstract

This paper proposes a length-independent feature representation of sets of strings based on Bloom filters called BACR for similarity search in databases. Further, we show how a Z-curve-based discretization of geospatial trajectories can be used in order to search for similar trajectories in large databases. Additionally to the already-known estimation of the size of the union and the intersection of sets from Bloom filters, we propose a way to calculate an upper bound for the intersection and a lower bound for the union of sets. Consequently, we show that the Jaccard distance and many other similarity measures allow for a lower bound. This makes exact similarity search on large databases of this type feasible. Finally, we show that the Jaccard distance is incompatible with the union of sets and replace the Jaccard distance appropriately in a way such that even collections of sets of strings can be represented with a single BACR feature vector at least for similarity search applications. The algorithms are thoroughly evaluated and motivated by real-world examples.

OriginalspracheEnglisch
Titel23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2015
Redakteure/-innenYan Huang, Mohamed Ali, Jagan Sankaranarayanan, Matthias Renz, Michael Gertz
Herausgeber (Verlag)Association for Computing Machinery
ISBN (elektronisch)9781450339674
DOIs
PublikationsstatusVeröffentlicht - 3 Nov. 2015
Extern publiziertJa
Veranstaltung23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2015 - Seattle, USA/Vereinigte Staaten
Dauer: 3 Nov. 20156 Nov. 2015

Publikationsreihe

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Band03-06-November-2015

Konferenz

Konferenz23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2015
Land/GebietUSA/Vereinigte Staaten
OrtSeattle
Zeitraum3/11/156/11/15

Fingerprint

Untersuchen Sie die Forschungsthemen von „BACR: Set similarities with lower bounds and application to spatial trajectories“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren