Multidimensional data object searching using bit vector indices

Details Multidimensional data object searching using bit vector indices Multidimensional data object searching using bit vector indices

2008-01-29

2008-01-29

Corrielus, Jean M. (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07325001

ABSTRACT:
Prior to searching a multidimensional feature space populated with data objects, each dimension in the feature space is divided into a number of intervals. When a query is received, a single interval that is overlapped by the query is selected from each dimension. A reduced set of data objects is then selected that includes only those data objects that overlap the selected intervals. This reduced set of data objects, rather than the entire set of data objects in the feature space, is then used to determine matches for the query.

REFERENCES:
patent: 5499360 (1996-03-01), Barbara et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6490532 (2002-12-01), Hogue et al.
patent: 6778981 (2004-08-01), Lee et al.
patent: 2003/0061213 (2003-03-01), Yu et al.
patent: 2003/0097356 (2003-05-01), Lee et al.
patent: 2003/0236789 (2003-12-01), Agrawal et al.
patent: 2004/0024738 (2004-02-01), Yamane
Katayama, Norio; Satoh, Shin'Ichi; “The SR-Tree: An Indes Structure for High-Dimensional nearest Neighbor Queries” Apr. 1997; ACM Arizona, USA; pp. 369-380.
Gaede, Voker; Gunther, Oliver; “Multidimensional Access Methods”; ACM Computing Surveys, vol. 30, No. 2, Jun. 1998; pp. 170-231.
Goldstein, Johnathan; Ramakrishnan, Raghu; “Contrast Plots and P-Shere Trees: Space vs. Time in Nearest Neighbor Searches”; VLDB Conference, Cairo, Egypt, 2000; 12 pages.
Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter; “The X-tree: An Index for High-Dimensional Data”; VLDB Conference, Mumbai, India, 1996; pp. 28-39.
Hjaltason, Gisli R.; Samet, Hanan; “Ranking in Spatial Databases”; University of Maryland, pp. 83-95.
Funkhouser, Thomas; Min, Patrick; Kazhdan, Michael; Chen, Joyce; Halderman, Alex; Dobkin, David; Jacobs, David; “A Search Engine for 3D Models”; ACM Transactions on Graphics, vol. V., No. N; 28 Pages; 2002.
Kriegel, Hans-Peter; Potke, Marco; Seidl, Thomas; “Object-Relational Indexing for General Interval Relationships”; 21 pages; Germany, 2001.
Kamel, Ibrahim; Faloutsos, Christos; “Hilbert R-tree: An Improved R-tree Using Fractals”; VLDB Conference; pp. 500-509; Santiago, Chile; 1994.
Hellerstein, Joseph M.; Naughton, Jeffrey F.; Pfeiffer, Avi; “Generalized Search Trees for Database Systems”; VLDB Conference; pp. 562-573; Zurich, Switzerland; 1995.
O'Neil, Patrick; Quass, Dallan; “Improved Query Performance with Variant Indexes”; SIGMOD 1997; pp. 38-49; Arizona.
Guttman, Antonin; “R-trees: A Dynamic Index Structure for Spatial Searching” ACM; pp. 47-57; 1984.
Weber, Rober; Schek, Hans-J; Blott, Stephen; “A Qantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces”; VLDB Conference; pp. 194-205;1998; New York, USA.
Burges, Christopher J.C.; Platt, John C.; Jana, Soumya; “Extracting Noise-Robust Features from Audio Data” IEEE; pp. I-1021 to I-1024; 2002.
Beyer, Kevin; Goldstein, Johnathan; Ramakrishnan, Raghu; Shaft, Uri; “When is ‘Nearest Neighbor’ Meaningful?”; 19 Pages; Madison, Wisconsin, USA.
Rui, Yong; Huang, Thomas S.; and Chang, Shih-Fu; “Image Retrieval: current Techniques, Promising Directions and Open Issues” Journal of Visual Communications and Image Representation, vol. 10, No. 4, 1999; 17 pages.
Pagel, Bernd-Uwe; Korn, Flip; and Faloutsos, Christos; “Deflating the Dimensionality Curse Using Multiple Fractal Dimensions”; pp. 1-10, ICDE 2000.
H. Edelsbrunner; Maurer, H.A.; “On the Intersection of Orthogonal Objects”; Information Processing Letters, v13, n4 & 5; North Holland, Aug. 1981; pp. 177-181.
Bromley, J.; Bentz, J.W.; Bottou, L.; Guyon, I.; Lecun, Y.; Moore, C.; Sackinger, E.; Shah, R.; “Signature Verification Using a ‘Siamese’ Time Delay Neural Network”; Advances in Neural Processing Systems, v6; 1994; pp. 25-44.
O'Neil, Patrick; “Model 204 Architecture and Performance”; High Performance Transaction Systems Workshop; Sep. 1987; pp. 40-59.

Affiliated with

Also associated with

Rating

Multidimensional data object searching using bit vector indices does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multidimensional data object searching using bit vector indices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multidimensional data object searching using bit vector indices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2770440