Multidimensional data object searching using bit vector indices

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

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

     

Profile ID: LFUS-PAI-O-2770440

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.