A unified approach for indexed and non-indexed spatial joins

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Vitter Scott

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly index construction. In this paper, we develop a simple plane-sweeping algorithm that unifies the index-based and non-index based approaches. This algorithm processes indexed as well as non-indexed inputs, extends naturally to multi-way joins, and can be built easily from a few standard operations. We present the results of a comparative study of the new algorithm with several index-based and non-index based spatial join algorithms. We consider a number of factors, including the relative performance of CPU and disk, the quality of the spatial indexes, and the sizes of the input relations. An important conclusion from our work is that using an index-based approach whenever indexes are available does not always lead to the best execution time, and hence we propose the use of a simple cost model to decide when to follow an index-based approach.

    Original languageEnglish (US)
    Title of host publicationAdvances in Database Technology - EDBT 2000 - 7th International Conference on Extending Database Technology, Proceedings
    EditorsCarlo Zaniolo, Peter C. Lockemann, Marc H. Scholl, Torsten Grust
    PublisherSpringer Verlag
    Number of pages17
    ISBN (Electronic)3540672273, 9783540672272
    StatePublished - 2000
    Event7th International Conference on Extending Database Technology, EDBT 2000 - Konstanz, Germany
    Duration: Mar 27 2000Mar 31 2000

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other7th International Conference on Extending Database Technology, EDBT 2000

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'A unified approach for indexed and non-indexed spatial joins'. Together they form a unique fingerprint.

    Cite this