Compact Spatial Joins (2008)

Brent Bryan, Frederick Eberhardt, Christos Faloutsos

Abstract

Similarity joins have attracted significant interest, with
applications in Geographical Information Systems, astronomy, marketing
analyzes, and anomaly detection.  However, all the past algorithms,
although highly fine-tuned, suffer an \emph{output explosion} if the
query range is even moderately large relative to the local data
density.  Under such circumstances, the response time and the search
effort are both almost quadratic in the database size, which is often
prohibitive.  We solve this problem by providing two algorithms that
find a {\em compact} representation of the similarity join result,
while retaining all the information in the standard join.  Our
algorithms have the following characteristics: (a) they are at least
as fast as the standard similarity join algorithm, and typically much
faster, (b) they generate significantly smaller output, (c) they
provably lose no information, (d) they scale well to large data sets,
and (e) they can be applied to any of the standard tree data
structures.  Experiments on real and realistic point-sets show that
our algorithms are up to several orders of magnitude faster.

Full text

Download (application/pdf, 178.2 kB)

Approximate BibTeX Entry

@inproceedings{compactjoins,
    Month = {April},
    Year = {2008},
    Journal = {Proceedings of the 24th International Conference on Data Engineering},
    Publisher = {IEEE},
    Booktitle = {ICDE},
    Author = { Brent Bryan, Frederick Eberhardt, Christos Faloutsos },
    Title = {Compact Spatial Joins}
}