Method of storing and retrieving multi-dimensional data...

Details Method of storing and retrieving multi-dimensional data... Method of storing and retrieving multi-dimensional data...

2007-01-23

2007-01-23

Wong, Don (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

10139544

ABSTRACT:
A method of partitioning and indexing multi-dimensional data that maps data to one-dimensional values according to the sequence in which an approximation of a Hilbert space-filling curve passes through all of the points corresponding to potential multi-dimensional data in a data space. Data is partitioned into ordered pages, each corresponding to a length of Hilbert curve and identified by the sequence of the first point on it. Practical application of the indexing method is made viable and useful by the provision of an efficient querying algorithm enabling data lying within any given hyper-rectangular query region to be retrieved. This is achieved by successively calculating ever higher sequence numbers of potential data points lying within a query region and each being the lowest such value for a point lying on a different curve section. Thus a single calculation is performed to identify each page potentially containing data of interest.

REFERENCES:
patent: 5761916 (1998-06-01), Oswalt et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5963956 (1999-10-01), Smartt
patent: 6003036 (1999-12-01), Martin
patent: 6021406 (2000-02-01), Kuznetsov
patent: 6084595 (2000-07-01), Bach et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6154746 (2000-11-01), Berchtold et al.
patent: 6311181 (2001-10-01), Lee et al.
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6460026 (2002-10-01), Pasumansky
patent: 6470287 (2002-10-01), Smartt
patent: 6622141 (2003-09-01), Lee et al.
J K Lawder and P J H King, “Using Space-filling Curves for Multi-dimensional Indexing”, School of Computer Science and Information Systems, Mar. 2001, 16 pages.
J K Lawder and P J H King, “Querying Multi-dimensional Data Indexed Using the Hilbert Space-Filling Curve”, Birkbeck College, University of London, Mar. 2001, 5 pages.
H. Tropf, H. Herzog, “Multidimensional Range Search in Dynamically Balanced Trees”, Angewandte Informatik, Feb. 1981, pp. 71-77.
Tetsuo et al., “Space Filing Curves and Their Use in the Design of Geometric Data Structures”, Dept. of Applied Electronics, Osaka Electro-Communication University, Japan, vol. 181, Jul. 1997, 13 pages.
J. Alber and R. Neidermeier. On Multi-Dimensional Hilbert Indexings. Proc. of Computing and Combinatorics. vol. 1449 Lecture Notes in Computer Science. pp. 329-338, Springer Verlag 1998.
T. Asano et al. Space Filling Curves and Their Use in the Design of Geometric Data Structures. vol. 911 Lecture Note in Computer Science. pp. 36-48, Springer Verlag 1995.
C. Faloutsos. Gray Codes for Partial Match and Range Queries IEEE Transactions on Software Engineering. vol. 14(10) pp. 1381-1393, Oct. 1988.
C. Faloutsos and S. Roseman. Fractals for Secondary Key Retrieval. Proc. 8thSymposium on Principles of Database Systems. Mar. 1989 pp. 247-252 ACM Press.
C. Faloutsos and Yirong. Dot; A Spatial Access Method Using Fractals. Proc. 7thInt. Conf. on Data Engineering. Apr. 1991 pp. 152-159 IEEE Computer Society.
I. Kamel and C. Faloutsos. Hilbert R-Tree: An Improved R-Tree Using Fractals. Proc. Int. Conf VLOB 1994 pp. 500-509, Morgan Kaufmann.
H. Tropf and H. Herzog. Multi-Dimensional Range Search in Dynamically Balanced Trees. Angewandte Informatik vol. 23(2) pp. 71-77 1981.
J. Lawder and P. King. Using Space-Filling Curves for Multi-Dimensional Indexing. Proc. of British National Conf. on Databases vol. 1832 Lecture Notes in Computer Science p. 20-35, Jul. 2000 Springer Verlag.
J. Lawder and P. King. Querying Multi-Dimensional Data Indexed Using the Hilbert Space-Filling Curve. ACM Sigmod Record vol. 30(1) pp. 19-24 Mar. 2001.
J. K. Lawder. The Application of Space-Filling Curves to the Storage and Retrieval of Multi-Dimensional Data. PhD Thesis, University of London, Aug. 2000, pp. 1-330.

Affiliated with

Also associated with

Rating

Method of storing and retrieving multi-dimensional data... 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 of storing and retrieving multi-dimensional data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of storing and retrieving multi-dimensional data... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3805153