Algorithms for Querying by Spatial Structure
Published 24 August 1998
Dimitris Papadias, Nikos Mamoulis, Vasilis Delis
Citations71
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A flexible framework is described which permits the representation of configurations in different resolution levels and supports the automatic derivation of similarity measures and three algorithms for structural query processing which integrate constraint satisfaction with spatial indexing (R-trees) are proposed.
Abstract
: Structural queries constitute a special form of content-based retrieval where the user specifies a set of spatial constraints among query variables and asks for all configurations of actual objects that (totally or partially) match these constraints. Processing such queries can be thought of as a general form of spatial joins, i.e., instead of pairs, the result consists of n-tuples of objects, where n is the number of query variables. In this paper we describe a flexible framework which permits the representation of configurations in different resolution levels and supports the automatic derivation of similarity measures. We subsequently propose three algorithms for structural query processing which integrate constraint satisfaction with spatial indexing (R-trees). For each algorithm we apply several optimization techniques and experimentally evaluate performance using real data. 1. Introduction Several types of spatial queries have been the focus of active research in the database...
Keywords
Computer Science
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
Nearest neighbor queries
1,408 Citations1995Nick Roussopoulos, Stephen Kelley +1 more
This paper presents an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalizes it to finding the k nearest neighbors.
Artificial IntelligenceIncreasing tree search efficiency for constraint satisfaction problems
1,114 Citations1980Robert M. Haralick, Gordon L. Elliott
Analytically and experimentally show that a lookahead procedure called forward checking which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.
Artificial IntelligenceTemporal reasoning based on semi-intervals
670 Citations1992Christian Freksa
A generalization of Allen's interval-based approach to temporal reasoning is presented, with the notion of ‘conceptual neighborhood’ of qualitative relations between events is central and knowledge about relations between events can be represented much more compactly.
Efficient processing of spatial joins using R-trees
575 Citations1993Thomas Brinkhoff, Hans‐Peter Kriegel +1 more
This paper presents a first detailed study of spatial join processing using R-trees, particularly R*-tree, and presents several techniques for improving its execution time with respect to both, CPU- and I/O-time.
ACM SIGMOD RecordSpatial query processing in an object-oriented database system
398 Citations1986Jack Orenstein
ACM Transactions on Information SystemsDesign and evaluation of algorithms for image retrieval by spatial similarity
304 Citations1995Venkat N. Gudivada, Vijay V. Raghavan
An algorithm for computing the spatial similarity between two symbolic images that is robust in the sense that it can deal with translation, scale, and rotational variances in images, and has quadratic time complexity in terms of the total number of objects in both the database and query images.
IEEE Transactions on Knowledge and Data EngineeringSimilarity searching in medical image databases
266 Citations1997Euripides G. M. Petrakis, Christos Faloutsos
The proposed method to handle approximate searching by image content in medical image databases has several desirable properties: it is much faster than sequential scanning for searching in the main memory and on the disk, thus scaling-up well for large databases.
Topological relations in the world of minimum bounding rectangles
253 Citations1995Dimitris Papadias, Timos Sellis +2 more
The topological information that Minimum Bounding Rectangle-based data structures convey about the actual objects they enclose is studied, using the concept of projections, and the results are applied to R-trees and their variations, R+-t trees and R*-tree in order to minimise disk accesses for queries involving topological relations.
Multi-step processing of spatial joins
226 Citations1994Thomas Brinkhoff, Hans‐Peter Kriegel +2 more
This paper presents a complete approach of spatial join processing on complex spatial objects that is based on three steps and reduces the total execution time of the spatial join by factors.
Computational IntelligenceConstraint satisfaction algorithms1
214 Citations1989Bernard A. Nadel
A unified survey of tree search, arc consistency, and hybrid tree search/arc consistency algorithms, in terms of three classes, suggests several new algorithms to be the best algorithm so far.
Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations
162 Citations1997Yun-Wu Huang, Ning Jing +1 more
The experimental results indicate that BFRJ with global optimizations can outperform the competitor by a significant margin (up to 50%) and this work was supported in part by the University of Michigan ITS Research Center of Excellence grant.
Efficient computation of spatial joins
136 Citations2002Oliver Günther
A class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner are described.
The VLDB JournalQualitative representation of spatial knowledge in two-dimensional space
132 Citations1994Dimitris Papadias, Timos Sellis
The common concepts underlying qualitative spatial knowledge representation are identified, the representational properties of the different systems are compared, and the computational tasks involved in relation-based spatial information processing are outlined.
IEEE Transactions on Knowledge and Data EngineeringPicture similarity retrieval using the 2D projection interval representation
106 Citations1996Mohammad Nabil, Anne H. H. Ngu +1 more
A unified representation for spatial relationships, 2D Projection Interval Relationships (2D-PIR), that integrates both directional and topological relationships is proposed and techniques for similarity retrieval based on the 2D- PIR representation are developed.
Parallel processing of spatial joins using R-trees
106 Citations2002Thomas Brinkhoff, H.-P. Kriegel +1 more
It is shown that spatial joins are very suitable to be processed on a parallel hardware platform and the most efficient one shows an almost optimal speed up under the assumption that the number of disks is sufficiently large.
Spatial join indices
92 Citations2002Doron Rotem
Algorithms based on grid files as the underlying spatial index are presented for spatial joins in databases which store images, pictures, maps and drawings, and it is shown that the size of the index and its maintenance cost are relatively small.
Lecture notes in computer scienceDynamic variable ordering in CSPs
87 Citations1995Fahiem Bacchus, Paul Run
This work provides an implementation methodology for adding DVO to an arbitrary tree-search algorithm and investigates the popular reordering heuristic of next instantiating the variable with the minimum remaining values (MRV).
Lecture notes in computer scienceOn the forward checking algorithm
43 Citations1995Fahiem Bacchus, Adam J. Grove
The forward checking algorithm for solving constraint satisfaction problems is a popular and successful alternative to backtracking, but its success has largely been determined empirically, and there has been limited work towards a real understanding of why and when forward checking is the superior approach.
Assessing multimedia similarity
8 Citations1998Vasilis Delis, Dimitris Papadias +1 more
A binary string encoding for 1D relations which permits the automatic derivation of similarity measures is proposed and extended to various resolution levels and many dimensions and it is shown that reasoning on spatiotemporal structure is significantly facilitated in the new framework.