Method and system for performing proximity joins on high-dimensional data points in parallel
US5884320A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 20, 1997 |
| Grant date | Mar 16, 1999 |
| Priority date | — |
| Expiry date | Aug 20, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99948
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system for performing spatial proximity joins on high-dimensional points representing data objects of a database in parallel in a multiprocessor system. The method comprises the steps of: partitioning the data points among the processors; creating index structures for the data points of the processors in parallel; assigning the join operations to the processors using the index structures; and simultaneously redistributing and joining the data points in the processors in parallel based on a predetermined joining condition. An efficient data structure, .epsilon.-K-D-B tree, is used to provide fast access to the high-dimensional points and to minimize system storage requirements. The invention achieves fast response time and requires minimum storage space by having structurally identical indices among the processors, assigning workload based on the join costs, and redistributing the data points among the processors while joining the data whenever possible.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.