Efficient position-independent iconic search using an R-theta index

ABSTRACT

An iconic image database is a collection of symbolic images where each image is a collection of labeled point features called icons. A method is presented to support fast position-independent similarity search in an iconic database for symbolic images where the similarity condition involves finding icon pairs that satisfy a specific spatial relationship. This is achieved by introducing an index data structure based on r-θ space, which corresponds to the Cartesian product of separation (i.e., inter-icon distance) and (some representation of) relative spatial orientation. In this space, each pairing of two icons is represented by a single point, and all pairs with the same separation and relative orientation (regardless of absolute position) map to the same point. Similarly, all icon pairs with the same separation but different relative orientations map to points on a line parallel to the θ axis, while all pairs with different separations but the same relative orientation map to points on a line parallel to the r axis. Using such an index, database search for icon pairs with a given spatial relationship or range is accomplished by examining the subarea of the index space into which desired pairs would map. This r-θ index space can be organized using well-known spatial database techniques, such as quadtrees or R-trees. Although the size of such an index grows only linearly with respect to the number of images in the collection, it grows quadratically with the average number of icons in an image. A scheme is described to reduce the size of the index by pruning away a subset of the pairs, at the cost of incurring additional work when searching the database. This pruning is governed by a parameter φ, whose variation provides a continuous range of trade-offs between index size and search time.

REFERENCES

• 1: D. Arkoumanis, M. Terrovitis, and E. Stamatogiannakis. Heuristic algorithms for similar configuration retrieval in spatial databases. In Proceedings of the 2nd Hellenic Conference on Artificial Intelligence (SETN), pages 141--152, Thessalonica, Greece, 2002.
• 2: Stefano Berretti , Alberto Del Bimbo , Enrico Vicario, Efficient Matching and Indexing of Graph Models in Content-Based Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1089-1105, October 2001 [doi>10.1109/34.954600]
• 3: 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]
• 4: M. J. Egenhofer. Query processing in spatial-query-by-sketch. Journal of Visual Languages and Computing, 8(4):403--424, August 1997.
• 5: Jost Enderle , Matthias Hampel , Thomas Seidl, Joining interval data in relational databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007645]
• 6: Christos Faloutsos, Tri-cell—a data structure for spatial objects, Information Systems, v.14 n.2, p.131-139, March 1989 [doi>10.1016/0306-4379(89)90041-0]
• 7: Roop K. Goyal , Max J. Egenhofer, Similarity of Cardinal Directions, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.36-58, July 12-15, 2001
• 8: Venkat N. Gudivada, TR$\Re$-String: A Geometry-Based Representation for Efficient and Effective Retrieval of Images by Spatial Similarity, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.504-512, May 1998 [doi>10.1109/69.687982]
• 9: 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]
• 10: 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
• 11: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 12: K. Hinrichs and J. Nievergelt. The grid file: a data structure designed to support proximity queries on spatial objects. In M. Nagl and J. Perl, editors, Proceedings of WG'83, International Workshop on Graphtheoretic Concepts in Computer Science, pages 100--113, Haus Ohrbeck (near Osnabrück), West Germany, 1983. Trauner Verlag.
• 13: A. Holt. Spatial similarity and GIS: the grouping of spatial kinds. In P. A. Whigham, editor, Eleventh Annual Colloquium of the Spatial Information Research Center (SIRC05), pages 241--250, Dunedin, New Zealand, December 1999. University of Otago.
• 14: P. W. Huang and Y. R. Jean. Using 2D C+-strings as spatial knowledge representation for image database systems. The Journal of the Pattern Recognition Society, 27(9):1249--1257, September 1994.
• 15: U. Lauther. 4-dimensional binary search trees as a means to speed up associative searches in design rule verification of integrated circuits. Journal of Design Automation and Fault-Tolerant Computing, 2(3):241--147, July 1978.
• 16: Suh-Yin Lee , Fang-Jung Hsu, 2D C-string: a new spatial knowledge representation for image database systems, Pattern Recognition, v.23 n.10, p.1077-1087, 1990 [doi>10.1016/0031-3203(90)90004-5]
• 17: D. Papadias, N. Karacapilidis, and D. Arkoumanis. Processing fuzzy spatial queries: A configuration similarity approach. International Journal of Geographic Information Science, 13(2):93--128, 1999.
• 18: D. Papadias, M. Mantzourogiannis, and I. Ahmad. Fast retrieval of similar configurations. IEEE Transactions on Multimedia, 5(2):210--222, June 2003.
• 19: J. B. Rosenberg. Geographical data structures compared: a study of data structures supporting region queries. IEEE Transactions on Computer-Aided Design, 4(1):53--67, January 1985.
• 20: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Hanan Samet , Aya Soffer, MARCO: MAp Retrieval by COntent, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.783-798, August 1996 [doi>10.1109/34.531799]
• 22: Bernhard Seeger , Hans-Peter Kriegel, Techniques for Design and Implementation of Efficient Spatial Access Methods, Proceedings of the 14th International Conference on Very Large Data Bases, p.360-371, August 29-September 01, 1988
• 23: A. Prasad Sistla , Clement T. Yu , R. Haddad, Reasoning About Spatial Relationships in Picture Retrieval Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.570-581, September 12-15, 1994
• 24: Spiros Skiadopoulos, Christos Giannoukos, Panos Vassiliadis, Timos K. Sellis, and Manolis Koubarakis. Computing and handling cardinal direction information. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT), volume 2992 of Lecture Notes in Computer Science, pages 329--347, Heraklion, Crete, Greece, March 2004.
• 25: A. Soffer and H. Samet. Pictorial query specification for browsing through spatially referenced image databases. Journal of Visual Languages and Computing, 9(6):567--596, December 1998. Also an abbreviated version in Proceedings of the Second International Conference on Visual Information Systems (VISUAL97), pages 117--124, San Diego, CA, December 1997.
• 26: Ju-Won Song , Kyu-Young Whang , Young-Koo Lee , Min-Jae Lee , Sang-Wook Kim, Spatial Join Processing Using Corner Transformation, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.688-695, July 1999 [doi>10.1109/69.790844]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms

Keywords:
iconic database, position-independent, spatial indexing