Method and system for performing spatial similarity joins on high-dimensional points
Patent 5978794 Issued on November 2, 1999. Estimated Expiration Date: 
April 9, 2016. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
April 9, 2016. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.Patent ReferencesNumerical processing of optical wavefront data Database engine predicate evaluator Apparatus for realigning database fields through the use of a crosspoint switch Method for high-dimensionality indexing in a multi-media database Method and apparatus for imaging, image processing and data compression merge/purge techniques for document image databases Memory system for storing and retrieving experience and knowledge with natural language Image signal coding method Patent #: 5754701 InventorsApplicationNo. 629688 filed on 04/09/1996US Classes:707/3, Query processing (i.e., searching)707/4, Query formulation, input preparation, or translation707/101Manipulating data structure (e.g., compression, compaction, compilation)ExaminersPrimary: Black, Thomas G.Assistant: Jung, David Attorney, Agent or FirmInternational ClassG06F 017/00AbstractA method and system are disclosed for performing spatial similarity joins on high-dimensional points that represent data objects of a database. The method comprises the steps of: generating a data structure based on the similarity distance &3xb5; for organizing the high-dimensional points, traversing the data structure to select pairs of leaf nodes from which the high-dimensional points are joined, and joining the points from selected pairs of nodes according to a joining condition based on the similarity distance &3xb5;. An efficient data structure referred to as an &3xb5;-K-D-B tree is disclosed to provide fast access to the high-dimensional points and to minimize system storage requirements. The invention provides algorithms for generating the &3xb5;-K-D-B tree using biased splitting to minimize the number of nodes to be examined during join operations. The traversing step includes joining selected pairs of nodes and also self-joining selected nodes. Alternatively, the data structure is an R+tree generated using biased splitting.Other References
Field of SearchObject-oriented database structureObject-oriented database structure processing Object-oriented database structure reference Object-oriented database structure network Privileged access Query augmenting and refining (e.g., inexact access) Coherency (e.g., same view to multiple users) Garbage collection Access augmentation or optimizing Archiving or backup Version management DATABASE SCHEMA OR DATA STRUCTURE Distributed or remote access Generating database or data structure (e.g., via user interface) Application of database or data structure (e.g., distributed, multimedia, image) Manipulating data structure (e.g., compression, compaction, compilation) FILE OR DATABASE MAINTENANCE DATABASE OR FILE ACCESSING Query processing (i.e., searching) Pattern matching access Query formulation, input preparation, or translation Sorting Concurrency (e.g., lock management in shared database) File allocation Recoverability | |
