High-dimensional index structure

Details High-dimensional index structure High-dimensional index structure

1998-04-22

2000-11-28

Breene, John

Data processing: database and file management or data structures

Database design

Data structure types

707101, 707102, 707 2, 707 3, G06F 1730

Patent

active

061547468

ABSTRACT:
A method for transforming multi-dimensional data points into 1-dimensional values which are stored in a 1-dimensional index structure is disclosed. The data space is divided into a first plurality of pyramids each having a center point of the data space as a top and a (d-1) dimensional surface of the data space as a base, wherein the first plurality of pyramids is equal to twice the number of dimensions of the data space. Each pyramid is then divided into a second plurality of partitions. A Pyramid-value for each partition is then computed. Finally, each partition is stored in the index structure using the Pyramid-value as an index key.

REFERENCES:
patent: 5701467 (1997-12-01), Freeston
patent: 5778354 (1998-07-01), Leslie et al.
Berchtold, S., Bohm, C., Braunmuller, B.,Keim, D.A., Kriegel, H-P. "Fast Parallel Similarity Search in Multimedia Databases"--Proc. ACM SIGMOD, Int. Conf. On Management of Data, Jan. 1997, Tucson, Arizona--pp. 1 thru 12.
Berchtold, S., Bohm, C., Keim, D., Kriegel, H-P.: "A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space"--ACM PODS Symposium on Principles of Database Systems, Jan. 1997, Tucson, AZ--PP. 78 thru 86.
Berchtold, S., Ertl, B., Keim, D., Kriegel, H-P.: Fast Neighbor Search in High-dimensional Space--Proc. 14th Int. Conf. On Data Engineering, Orlando, Jan. 1998--pp. 209 thru 218.
Comer, D., "The Ubiquitos B-tree "--ACM Computing Surveys 11 (2), Jan. 1979, pp. 121 thru 137.
Chaudhuri, S., Dayal, U "Data Warehousing and OLAP for Decision Support", Tutorial, Proc., ACM SIGMOD Int. Conf. On Management of Data, Jan. 1997, Tucson, AZ--pp. 507-508.
Faloustsos, C., Barber, R., Flickner, M., Hafner, J., et al., "Efficient and Effective Querying by Image Content", Journal of Intelligent Information Systems, Jan. 1994, vol. 3--pp. 231 thru 262.
Faloutsos, C., Bhagwat, P. "Declustering Using Fractals", PDIS Journal of Parallel and Distributed Information Systems, Jan. 1993,--pp. 18 thru 34.
Friedman, J.H., Bently, J.L., Finkel, R.A., "An Algorithm for Finding Best Matches in Logarithmic Expected Time" ACM Transactions on Mathematical Software., vol. 3, No. 3, Sep. 1977--pp. 209 thru 226.
Hjaltason, G.R., Samet, H., "Ranking in Spatial Databases", Proc. 4th In. Symp. On Large Spatial Databases, Portland, ME Jan. 1995, pp. 1 thru 13.
Jagadish, H.V., "A Retrieval Technique for Similar Shapes", Proc. ACM SIGMOD Int. Conf. On Management of Data, Jan. 1991--pp. 208 thru 217.
Jain, R., White, D.A., "Similarity Indexing: Algorithms and Performance", Proc. SPIE Storage and Retrieval for Image and Video Databses IV, vol. 2670, San Jose, CA., Jan. 1996--pp. 62 thru 73.
Katayama, N., Satoh, S., "The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries", Proc. ACM SIGMOD Int. Conf. On Management of Data, Jan. 1997--pp. 369 thru 380.
Lin, K., Jagadish, H.V., Faloutsos, C., "The TV-tree--an index structure for high-dimensional data", VLDB Journal, vol. 3, Jan. 1995--pp. 1 thru 30.
Mehrotra, R., Gary J., "Feature-Based retrieval of Similar Shapes", Proc. 9th Int. Conf. On Data Engineering, Apr. 1993--pp. 108 thru 115.
Robinson, J.T., "The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes", Proc. ACM SIGMOD Int. Conf. On Management of Data, Jan. 1981,--pp. 10 thru 18.
Seidl, T., Kriegel, H.P. "Efficient User-Adaptable Similarity Search in Large Mutlimedia Databases", Proc. 23rd. Int. Conf., on Very Large Databases (VLDB 97), Athens, Greece, Jan. 1997.
White, D.A., Jain, R., "Similarity Indexing with the SS-tree", Proc. 12th Int. Conf. On Data Engineering, New Orleans, LA., Jan. 1996--pp. 516 thru 523.
Beckmann, N., Kriegel, H-P., Schneider, R., Seeger, B.,: The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Jan. 1990 ACM SIGMOD Int. Conf. On Management of Data, Atlantic City, NJ 1990-pp. 322 thru 331.
Berchtold, S., Keim, D., Kriegel, H-P.: The X-tree: An Index Structure for High-Dimensional Data. Proceedings ot the 22nd VLDB Conference, Mumbai (Bombay), India, Jan. 1996--pp. 1 thru 12.
Berchtold, S., Bohm, C., Kriegel, H-P.: Improving the Query Performance of High-Dimensional Index Structures by Bulk Load Operations--submitted, no date.
Berchtold, S., Bohm, C., Braunmuller, B., Keim, D.A., Kriegel, H-P. "Fast Parallel Similarity Search in Multimedia Databases"--Pro. ACM SIGMOD, Int. Conf. On Management of Data, Tucson, Arizona--pp. 1 thru 12, 1997.

Affiliated with

Also associated with

Rating

High-dimensional index structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-dimensional index structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-dimensional index structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1735209