Approximate spatio-temporal retrieval

ABSTRACT

This paper proposes a framework for the handling of spatio-temporal queries with inexact matches, using the concept of relation similarity. We initially describe a binary string encoding for 1D relations that permits the automatic derivation of similarity measures. We then extend this model to various granularity levels and many dimensions, and show that reasoning on spatio-temporal structure is significantly facilitated in the new framework. Finally, we provide algorithms and optimization methods for four types of queries: (i) object retrieval based on some spatio-temporal relations with respect to a reference object, (ii) spatial joins, i.e., retrieval of object pairs that satisfy some input relation, (iii) structural queries, which retrieve configurations matching a particular spatio-temporal structure, and (iv) special cases of motion queries. Considering the current large availability of multidimensional data and the increasing need for flexible query-answering mechanisms, our techniques can be used as the core of spatio-temporal query processors.

REFERENCES

• 1: Nabil Adam , Yelena Yesha, Strategic directions in electronic commerce and digital libraries: towards a digital agora, ACM Computing Surveys (CSUR), v.28 n.4, p.818-835, Dec. 1996 [doi>10.1145/242223.246871]
• 2: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 3: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 4: Fahiem Bacchus , Adam J. Grove, On the Forward Checking Algorithm, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.292-308, September 19-22, 1995
• 5: Fahiem Bacchus , Paul van Run, Dynamic Variable Ordering in CSPs, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.258-275, September 19-22, 1995
• 6: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, ACM SIGMOD Record, v.19 n.2, p.322-331, Jun. 1990
• 7: Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Fast Nearest Neighbor Search in High-Dimensional Space, Proceedings of the Fourteenth International Conference on Data Engineering, p.209-218, February 23-27, 1998
• 8: BUREAU OF THE CENSUS. 1994. TIGER/Line files. Bureau of the Census, Washington DC.
• 9: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, ACM SIGMOD Record, v.23 n.2, p.197-208, June 1994
• 10: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, ACM SIGMOD Record, v.22 n.2, p.237-246, June 1, 1993
• 11: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996
• 12: BRUNS,T.AND EGENHOFER, M. 1996. Similarity of spatial scenes. In Proceedings of the Conference on Spatial Data Handling (Delft, The Netherlands), M.-J. Kraak and M. Molenaar, Eds. 31-42.
• 13: CHANG, S., JUNGERT, E., AND LI, T. 1989. Representation and retrieval of symbolic pictures using generalized 2D strings. In Proceedings of the Conference on SPIE Visual Communications and Image Processing IV. 1360-1372.
• 14: CHANG, S. -F., CHEN, W., MENG,H.J.,SUNDARAM, H., AND ZHONG, D. 1998. A fully automatic content-based video search engine supporting multi-object spatio-temporal queries. IEEE Trans. Circuits Syst. Video Technol. 8, 5 (Sept.), 602-615.
• 15: S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987 [doi>10.1109/TPAMI.1987.4767923]
• 16: Max J. Egenhofer , Khaled K. Al-Taha, Reasoning about Gradual Changes of Topological Relationships, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.196-219, September 21-23, 1992
• 17: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 18: Christian Freksa, Temporal reasoning based on semi-intervals, Artificial Intelligence, v.54 n.1-2, p.199-227, March 1992 [doi>10.1016/0004-3702(92)90090-K]
• 19: Venkat N. Gudivada , Vijay V. Raghavan, Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Transactions on Information Systems (TOIS), v.13 n.2, p.115-144, April 1995 [doi>10.1145/201040.201041]
• 20: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 21: HARALICK,R.M.AND ELLIOTT, G. L. 1980. Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14, 263-313.
• 22: Daniel Hernandez, Qualitative Representation of Spatial Knowledge, Springer-Verlag New York, Inc., Secaucus, NJ, 1994
• 23: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 24: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• 25: Suh-Yin Lee , Fang-Jung Hsu, Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation, Pattern Recognition, v.25 n.3, p.305-318, March 1992 [doi>10.1016/0031-3203(92)90112-V]
• 26: LEE, S., YANG, M., AND CHEN, J. 1992. Signature file as a spatial filter for iconic image database. J. Visual Lang. Comput. 3, 4, 373-397.
• 27: Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, ACM SIGMOD Record, v.23 n.2, p.209-220, June 1994
• 28: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, ACM SIGMOD Record, v.25 n.2, p.247-258, June 1996
• 29: Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, ACM SIGMOD Record, v.28 n.2, p.1-12, June 1999
• 30: Mark T. Maybury, Intelligent multimedia information retrieval, MIT Press, Cambridge, MA, 1997
• 31: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 32: Mohammad Nabil , Anne H. H. Ngu , John Shepherd, Picture Similarity Retrieval Using the 2D Projection Interval Representation, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.533-539, August 1996 [doi>10.1109/69.536246]
• 33: Bernard A. Nadel, Constraint satisfaction algorithms, Computational Intelligence, v.5 n.4, p.188-224, Nov. 1990 [doi>10.1111/j.1467-8640.1989.tb00328.x]
• 34: Virginia E. Ogle , Michael Stonebraker, Chabot: Retrieval from a Relational Database of Images, Computer, v.28 n.9, p.40-48, September 1995 [doi>10.1109/2.410150]
• 35: Jack A. Orenstein, Spatial query processing in an object-oriented database system, ACM SIGMOD Record, v.15 n.2, p.326-336, June 1986
• 36: PAPADIAS,D.AND THEODORIDIS, Y. 1997. Spatial relations, minimum bounding rectangles, and spatial data structures. Int. J. Geograph. Inf. Syst. 11, 2, 111-138.
• 37: Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303981]
• 38: Dimitris Papadias , Marios Mantzourogiannis , Panos Kalnis , Nikos Mamoulis , Ishfaq Ahmad, Content-based retrieval using heuristic search, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312673]
• 39: Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States
• 40: Ho-Hyun Park , Guang-Ho Cha , Chin-Wan Chung, Multi-way Spatial Joins Using R-Trees: Methodology and Performance Evaluation, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.229-250, July 20-23, 1999
• 41: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, ACM SIGMOD Record, v.25 n.2, p.259-270, June 1996
• 42: Euripides G. M. Petrakis , Christos Faloutsos, Similarity Searching in Medical Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.435-447, May 1997 [doi>10.1109/69.599932]
• 43: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 44: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• 45: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 46: Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
• 47: SMITH,J.AND CHANG, S. 1996. Searching for images and videos on the world-wide web. CU/CTR 459-96-25.
• 48: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 49: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 50: Michael Vazirgiannis , Yannis Theodoridis , Timos Sellis, Spatio-temporal composition and indexing for large multimedia applications, Multimedia Systems, v.6 n.4, p.284-298, July 1998 [doi>10.1007/s005300050094]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Multimedia databases