@inproceedings{06b20ba4d36f4d7fb8378a802ce5c28a,
title = "BACR: Set similarities with lower bounds and application to spatial trajectories",
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.",
keywords = "Big data, Moving objects, Multi-modal trajectory, Trajectory",
author = "Martin Werner",
note = "Publisher Copyright: Copyright 2015 ACM.; 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2015 ; Conference date: 03-11-2015 Through 06-11-2015",
year = "2015",
month = nov,
day = "3",
doi = "10.1145/2820783.2820802",
language = "English",
series = "GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems",
publisher = "Association for Computing Machinery",
editor = "Yan Huang and Mohamed Ali and Jagan Sankaranarayanan and Matthias Renz and Michael Gertz",
booktitle = "23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2015",
}