Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-04-09
1999-11-02
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 4, 707101, G06F 1700
Patent
active
059787945
ABSTRACT:
A method and system are disclosed for performing spatial similarity joins on high-dimensional points that represent data objects of a database. The method comprises the steps of: generating a data structure based on the similarity distance .epsilon. for organizing the high-dimensional points, traversing the data structure to select pairs of leaf nodes from which the high-dimensional points are joined, and joining the points from selected pairs of nodes according to a joining condition based on the similarity distance .epsilon.. An efficient data structure referred to as an .epsilon.-K-D-B tree is disclosed to provide fast access to the high-dimensional points and to minimize system storage requirements. The invention provides algorithms for generating the .epsilon.-K-D-B tree using biased splitting to minimize the number of nodes to be examined during join operations. The traversing step includes joining selected pairs of nodes and also self-joining selected nodes. Alternatively, the data structure is an R+tree generated using biased splitting.
REFERENCES:
patent: 5119323 (1992-06-01), Nickerson et al.
patent: 5590362 (1996-12-01), Baum et al.
patent: 5619713 (1997-04-01), Baum et al.
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5668897 (1997-09-01), Stolfo
patent: 5715468 (1998-02-01), Budzinski
patent: 5754701 (1998-05-01), Yokoyama
J. Nievergelt, H. Hinterberger, The Grid File: An Adaptable, Symmetric Multikey File Structure, Readings in Database Systems, 2nd Edition, Morgan Kaugmann Publishers, San Mateo, CA (book), 1984.
D. B. Lomet, B. Salzberg, The hB-Tree: a Multiattribute Indexing Method with Good Guaranteed Performance, Readings in Database Systems, Second Edition, Morgan Kaufmann Publishers, San Mateo, California (book), 1990.
N. Yazdani, M. Ozsoyoglu & G. Ozsoyoglu, A Framework for Feature-Based Indexing for Spatial Databases, Proceedings, 7th International Working Conf. on Scientific & Statistical Database Mng.(IEEE Computer Society Press) pp. 259-269, Sep. 28-30, 1994 Charlottesville, Virginia.
Brinkhoff, Kriegel, B. Seeger, Efficient processing of Spatial Joins Using R-trees, SIGMOD 5/93 Washington, DC, ACM 0-89791-592-5/93/0005/0237/1993.
K.I. Lin, H.V. Jagadish & C. Faloutsos, The TV-Tree: An Index Structure for High-Dimensional Data, VLDB Journal 3, pp. 517-542, 1994.
M.L. Lo & C. V. Ravishankar, Spatial Joins Using Seeded Trees, SIGMOD 94-5/94 Minneapolis, Minn, ACM 0-89791-639-5/94/0005, pp. 209-220, 1994.
T. Sellis, N. Roussopoulos, C. Faloutsos, The R+ -Tree: A Dynamic Index for Multi-Dimensional Objects, Dept. of Computer Science, Univ. of Maryland, College Park, MD 20742, Feb. 1987.
J. L. Bentley, Multidimensional Binary Search Trees Used for Associative Searching, ACM, vol. 18, No. 9, pp. 509-517, Sep. 1975.
H. V. Jagadish, A Retrieval Technique for Similar Shapes, ACM 0-89791-425-2/91/0005/0208, pp. 208-217, 1991.
R. Agrawal, K.I. Lin, H. S. Sawhney & K. Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995.
H. Samet, (Book) The Design and Analysis of Spatial Data Structures, Chapter 2, Point Data, pp. 43-80, 1989 (QA76.9 D35 S26 1990).
A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, ACM 0-89791-12808/84/006/0047, pp. 47-57, 1984.
C. Faloutsos & K. I (David) Lin, Fast Map: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets, ACM 0-89791-731-6/95/0005, pp. 163-174, 1995.
N. Beckman, H. P. Kriegel, R. Schneider, B. Seeger, The R* -tree: An Efficient and Robust Access Method for Points and Rectangles, ACM 089791-365/90/0005/0322 pp. 322-331, 1990.
J. T. Robinson, The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes, Proc. of ACM SIGMOD, Ann ARbor, Mi, Apr. 1981.
P. Mishra & M. H. Eich, Join Processing in Relational Databases, ACM Computing Surveys, vol. 24, No. 1, pp. 63-113, Mar. 1992.
M. Kitsuregawa, L. Harada and M. Takagi, Algorithms and performance Evaluation of Join Processing on KD-Tree Indexed Relations, Trans. Inst. Electron, Inf. Comm. Eng. D-I (Japan), vol. J76D-I, No. 4, pp. 172-183, Apr. 1993, 36 REF.
Jeffrey Ullman, Principles of Database And Knowledge-Base Systems, 1988, pp. 361-368, 375.
R.L. Graham et al., 3rd Edition, "Concrete Mathematics", Addison-Wesley Co., 1989, at pp. 67-78.
Agrawal Rakesh
Shim Kyuseok
Srikant Ramakrishnan
Black Thomas G.
International Business Machines - Corporation
Jung David Yiuk
Tran Khanh Q.
LandOfFree
Method and system for performing spatial similarity joins on hig does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing spatial similarity joins on hig, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing spatial similarity joins on hig will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2149761