Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-25
2008-01-08
Pannala, Sathyanarayan (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
07318053
ABSTRACT:
Vectors representing objects in n-dimensional space are approximated by local polar coordinates on partitioned cells of the data space in response to a query, e.g., a query data vector entered with a request to find “k” nearest neighbors to the query vector. A set of candidate near neighbors is generated using the approximations, with the local polar coordinates being independent of the dimensionality of the data space. Then, an answer set of near neighbors is returned in response to the query. Thus, the present invention acts as a filter to reduce the number of actual data vectors in the data set that must be considered in responding to the query.
REFERENCES:
patent: 5619717 (1997-04-01), Staats
patent: 5802357 (1998-09-01), Li et al.
patent: 5983215 (1999-11-01), Ross et al.
patent: 6003029 (1999-12-01), Agrawal et al.
patent: 6088663 (2000-07-01), Wang
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6137493 (2000-10-01), Kamimura et al.
patent: 6226640 (2001-05-01), Ostrovsky et al.
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6289353 (2001-09-01), Hazlehurst et al.
patent: 6289354 (2001-09-01), Aggarwal et al.
“Converting Between Cartesian and Polar Coordinates”, Jul. 7, 1996, Apple Computer, Inc. Chapter 8, 1-2 & 1-4.
Kleinberg, John M., “Two Algorithms for Nearest-Neighbor Search in High Dimensions”, 1997, ACM, pp. 599-608.
Rafiei et al., “Similarity-Based queries for Time Series Data”, 1997, SIGMOD, ACM, pp. 13-25.
Chang et al., “The onion T echnique: Indexing for Linear Optimizaation Queries”, 2000,MOD 2000-ACM, pp. 391-402.
Katayama et al., “The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries”, 1997, SIGMOD-ACM, pp. 369-380.
White et al., “Similarity Indexing with the SS-tree”, 1996, IEEE, pp. 516-523.
Bozkaya et al., “Indexing Large Metric Spaces for Similarity Search Queries”, Sep. 1999, ACM Transaction on Database Systems, vol. 24, No. 3, pp. 361-404.
Department of Mathematics, “Coordinate Systems in Two and Three Dimensions”, 1996, Oregon University, <http://oregonstate.edu/dept/math/CalculusQuestStudyGuides/vcalc/coord/coord.html>, pp. 1-4.
“A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.” Weber et al. Proceedings of the 24th VLDB Conference. 12 Pgs. New York, 1998.
Cha Guang-Ho
Chung Chin-Wan
Petkovic Dragutin
Zhu Xiaoming
International Business Machines - Corporation
Pannala Sathyanarayan
Rogitz John L.
LandOfFree
Indexing system and method for nearest neighbor searches in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Indexing system and method for nearest neighbor searches in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Indexing system and method for nearest neighbor searches in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3964538