Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2008-01-22
2008-01-22
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
10781488
ABSTRACT:
A database system and method for organizing data elements according to a Hilbert curve, said data elements being representable by a plurality of coordinates, said database system comprising:first means for generating a plurality of bitblocks by bitwise interleaving the coordinates of the data elements;second means for applying a fliprot transformation to a first bitblock;said fliprot transformation comprising a flip transformation and a rot transformation, said flip transformation inverting bits of said bitblock, said rot transformation interchanging bits of said bitblock;third means for obtaining, for each further bitblock, a fliprot transformation by a concatenation of two or more fliprot transformations; andfourth means for applying fliprot transformations to their corresponding bitblock;whereby the bitblock bits determine the organization of said data elements according to said Hilbert curve.
REFERENCES:
patent: 4837845 (1989-06-01), Pruett et al.
patent: 6154746 (2000-11-01), Berchtold et al.
patent: 6460026 (2002-10-01), Pasumansky
patent: 6510435 (2003-01-01), Bayer
patent: 2002/0095412 (2002-07-01), Lee et al.
patent: 2003/0004938 (2003-01-01), Lawder
patent: 2003/0187867 (2003-10-01), Smartt
patent: 196 35 429 (1998-03-01), None
Jagadish, H V “Linear clustering of objects with multiple attributes”, 1990, ACM Press, “Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data”.
J.K. Lawder. “Using State Diagrams for Hilbert Curve Mappings”. Technical Report JL2/00, Birkbeck College, University of London, 2000.
Bially, T. “Space-Filling Curves: Their generation and their application to bandwidth reduction”. Information Theory, IEEE Transactions on, Nov. 1969. vol. 15, Issue 6. pp. 658-664.
Xian Liu, et al. “An Algorithm for encoding and decoding the 3-D Hilbert Order”. Sep. 1997, IEEE Transactions on Image Processing, vol. 6, Issue 9, pp. 1333-1337.
Tropf, et al., “Multidimensional Range Search in Dynamically Balanced Trees.” Angewandte Informatik, Feb. 1981, pp. 71-77, Wiesbaden, Germany.
Orenstein, “Spatial Query Processing in an Object-Oriented Database System.” ACM SIGMOD Intnl. Conf. on Management of Data, 1986, pp. 326-336, vol. 15, No. 2.
Markl, “MISTRAL: Processing Relational Queries Using a Multidimensional Access Technique.” Doctoral Thesis, Techn. Univ. Munich, 1999, Germany.
Faloutsos, “Multiattribute Hashing Using Gray Codes.” ACM SIGMOD Intnl. Conf. on Management of Data, 1986, pp. 227-238, vol. 15, No. 2.
Lawder, et al., “Querying Multi-Dimensional Data Indexed Using the Hilbert Space-Filling Curve.” ACM SIGMOD Record, 2001, pp. 19-24, vol. 3, No. 1.
Lawder, “Calculation of Mappings Between One and n-Dimensional Values Using the Hilbert Space-Filling Curve.” Technical Report No. JL1/00, Aug. 15, 2000, pp. 1-13, www.Citeseer.com, accessed Jul. 8, 2003.
Butz, “Alternative Algorithm for Hilbert's Space-Filling Curve.” IEEE Transactions on Computers, Apr. 1971, pp. 424-426, vol. 20.
“Literature Collection of Tree Index.” www.comp.nus.edu.sg/˜liaojiro/tree.htm, accessed Apr. 6, 2004.
Gaede, et al., “Multidimensional Access Methods.” ACM Computing Surveys, Jun. 1998, pp. 170-231, vol. 30, No. 2.
Ramsak, et al., “Integrating the UB-Tree into a Database System Kernel.” Proc. of the 26th Intnl. Conf. on Very Large Databases, 2000, pp. 263-272, Cairo, Egypt.
Adams Charles D
IP Strategies
Rones Charles
LandOfFree
Database and method for organizing data elements does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database and method for organizing data elements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database and method for organizing data elements will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3959917