# US 6,732,107 B1 · Spatial join method and apparatus

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,107 B1
- Document ID: US6732107B1
- Status: Granted
- Kind: B1
- Application number: 09/817,566
- Filed: 2001-03-26
- Granted: 2004-05-04
- Earliest claimed: 2001-03-26
- Assignees: NCR Corporation
- Inventors: Gang Luo; Curt J. Ellmann; Jeffrey F. Naughton
- Web page: https://patentgrep.com/patent/US6732107B1

## CPC

- G06F 16/2448: {for particular applications; for extensibility, e.g. user defined types}
- G06F 16/2456: {Join operations}
- G06F 16/29: Geographical information databases
- Y10S 707/99931: Database or file accessing
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- Y10S 707/99945: Object-oriented database structure processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A non-blocking parallel spatial join algorithm generates the spatial join result tuples continuously even in the event of memory overflow. The algorithm employs duplicate avoidance techniques to avoid the blocking and time-consuming removal of duplicates. The algorithm also uses parallelism to improve performance.

## Claims

### Claim 1

A method comprising:
storing first tuples in a first table in a system;
storing second tuples in a second table in the system;
partitioning the first and second tuples into plural portions;
wherein partitioning the first and second tuples comprises redistributing the first and second tuples among plural nodes of the system;
performing a spatial join of the first and second tuples to create join result tuples based on the partitioned portions and using spatial attributes of the first and second tuples; and
performing duplicate avoidance to avoid generating duplicate join result tuples; and
wherein performing duplicate avoidance comprises identifying a pair of a first tuple and a second tuple that is replicated on plural nodes, and selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.

### Claim 2 (depends on 1)

The method of claim 1, wherein selecting one of the plural nodes to perform the spatial join of the pair comprises:
selecting based on generating a random number.

### Claim 3 (depends on 1)

The method of claim 1, wherein redistributing the first and second tuples among plural nodes of the system comprises:
receiving first and second tuples in a memory.

### Claim 4 (depends on 3)

The method of claim 3, wherein receiving the first and second tuples in a memory comprises:
receiving the first tuples into a first spatial index.

### Claim 5 (depends on 4)

The method of claim 4, wherein receiving the first and second tuples in a memory further comprises:
receiving the second tuples into a second spatial index.

### Claim 6 (depends on 5)

The method of claim 5, wherein joining the first and second tuples comprises:
joining first tuples from the first spatial index with second tuples in the second spatial index.

### Claim 7 (depends on 6)

The method of claim 6, wherein the first spatial index and second spatial index reside in the memory, and wherein joining the first and second tuples further comprises:
determining that the memory is full;
in response to determining that the memory is full, joining first tuples not received in the first spatial index with second tuples in the second spatial index; and
storing the first tuples not received in the first spatial index in a first data structure defined in a stable storage of the system.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
in response to determining that the memory is full, joining second tuples not received in the second spatial index with first tuples in the first spatial index; and
storing the second tuples not received in the second spatial index in the a second data structure.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first data structure comprises first buckets to store first tuples and the second data structure comprises second buckets to store second tuples.

### Claim 10 (depends on 9)

The method of claim 9, wherein joining the first and second tuples further comprises:
retrieving a pair of first and second buckets at random from plural bucket pairs;
building a third spatial index comprising the first tuples;
building a fourth spatial index comprising the second tuples; and
joining the first and second tuples in the third and fourth spatial indices.

### Claim 11 (depends on 10)

The method of claim 10, further comprising wherein performing duplicate avoidance comprises:
identifying a pair of a first tuple and a second tuple that is replicated on plural nodes of the system; and
selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.

### Claim 12 (depends on 11)

The method of claim 11, wherein performing duplicate avoidance further comprises:
identifying a pair of a first tuple and a second tuple in which the first tuple is replicated in plural first buckets and the second tuple is replicated in plural second buckets; and
selecting one pair of plural bucket pairs containing the first tuple and the second tuple to perform the spatial join.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
retrieving a result once a spatial join between any two tuples is performed.

### Claim 14 (depends on 1)

The method of claim 1, performing a spatial join of the first and second tuples comprising:
performing a non-blocking spatial join.

### Claim 15

A system comprising:
a processor;
a storage; and
instructions executable by the processor, for enabling the system to:
store first tuples in a first table accessible by plural nodes in the system;
store second tuples in a second table accessible by the plural nodes;
redistribute the first and second tuples across the plural nodes;
at each node, subdivide received redistributed tuples into plural buckets; and perform a spatial join operation between the first tuples and the second tuples based on the redistributing and subdividing and using spatial attributes of the first and second tuples; and
wherein the instructions executable by the processor, further enable the system to: generate join result tuples from the spatial join: and perform duplicate avoidance to avoid generating duplicate join result tuples by:
identifying a pair of a first tuple and a second tuple that is replicated on plural nodes; and
selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.

### Claim 16 (depends on 15)

The system of claim 15, wherein the instructions executable by the processor further enable the system to:
at each node, receive the redistributed first tuples into a first spatial index;
at each node, receive the redistributed second tuples into a second spatial index; and
at each node, join first tuples from the first spatial index with second tuples in the second spatial index.

### Claim 17 (depends on 16)

The system of claim 16, further comprising a non-persistent storage and a stable storage, wherein the first and second spatial indices are stored in the non-persistent storage, and wherein the instructions executable by the processor further enable the system to:
determine that the non-persistent storage is full;
in response to determining that the non-persistent storage is full, join first tuples not received in the first spatial index with second tuples in the second spatial index; and
store the first tuples not received in the first spatial index in the buckets structure defined in the stable storage.

### Claim 18

An article comprising a medium storing instructions for enabling a processor-based, system that has non-persistent storage and persistent storage to:
store first tuples in a first table in a system;
store second tuples in a second table in the system;
redistribute the first and second tuples across plural nodes of the system; and
perform a spatial join of the redistributed first and second tuples using spatial attributes of the first and second tuples;
wherein performing the spatial join comprises performing the spatial join in plural stages, the plural stages including at least a first stage in which the spatial join is performed on redistributed first and second tuples stored in non-persistent storage, and a second stage after the non-persistent storage has become full, wherein performing the spatial join in the second storage comprises performing the spatial join on first and second tuples stored in persistent storage; and
wherein further storing instructions for enabling a processor-based system to:
identifying a pair of a first tuple and a second tuple that is replicated on plural nodes; and
selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.

### Claim 19 (depends on 18)

The article of claim 18, further storing instructions for enabling a processor-based system to:
select based on generating a random number.

### Claim 20 (depends on 18)

The article of claim 18, further storing instructions for enabling a processor-based system to:
receive first and second tuples in the non-persistent storage.

### Claim 21 (depends on 20)

The article of claim 20, further storing instructions for enabling a processor-based system to:
receive the first tuples into a first spatial index.

### Claim 22 (depends on 21)

The article of claim 21, further storing instructions for enabling a processor-based system to:
receive the second tuples into a second spatial index.

### Claim 23 (depends on 22)

The article of claim 22, further storing instructions for enabling a processor-based system to:
join first tuples from the first spatial index with second tuples in the second spatial index.

### Claim 24 (depends on 23)

The article of claim 23, further storing instructions for enabling a processor-based system to:
determine that the first spatial index is full;
in response to determining that the first spatial index is full, join first tuples not received in the first spatial index with second tuples in the second spatial index; and
store the first tuples not received in the first spatial index in a data structure defined in a stable storage of the system.

### Claim 25 (depends on 24)

The article of claim 24, further storing instructions for enabling a processor-based system to:
join second tuples not received in the second spatial index with first tuples in the first spatial index; and
store the second tuples not received in the second spatial index in the data structure.

### Claim 26 (depends on 25)

The article of claim 25, further storing instructions for enabling a processor-based system to:
store first tuples not received in the first spatial index in first buckets; and
store second tuples not received in the second spatial index in second buckets, wherein the data structure comprises the first buckets and the second buckets.

### Claim 27 (depends on 26)

The article of claim 26, further storing instructions for enabling a processor-based system to:
retrieve a pair of first and second buckets at random from plural bucket pairs;
build a third spatial index comprising the first tuples;
build a fourth spatial index comprising the second tuples; and
join the first and second tuples in the third and fourth spatial indices.

### Claim 28 (depends on 27)

The article of claim 27, further storing instructions for enabling a processor-based system to:
identify a pair of a first tuple and a second tuple that is replicated on plural nodes of the system; and
select one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple.

### Claim 29 (depends on 28)

The article of claim 28, further storing instructions for enabling a processor-based system to:
identify a pair of a first tuple and a second tuple in which the first tuple is replicated in plural first buckets and the second tuple is replicated in plural second buckets; and
select one pair of plural bucket pairs containing the first tuple and the second tuple to perform the spatial join.

### Claim 30

A system comprising:
a plurality of nodes;
a storage containing first tuples and second tuples; and
a controller adapted to partition the first and second tuples among the plurality of nodes, the controller adapted to further identify a pair of a first tuple and a second tuple that is replicated on multiple nodes, and to select one of the multiple nodes to perform a join of the pair of the first tuple and the second tuple; and
wherein the controller is adapted to perform a spatial join of the pair of the first tuple and the second tuple using spatial attributes of the first and second tuples; and
wherein the storage is divided into plural portions accessible by corresponding nodes.

### Claim 31

An article comprising at least one storage medium containing instructions that, when executed, cause a system to:
partition first tuples of a first table and second tuples of a second table among plural nodes of the system;
during the partitioning, receive, in each node, first tuples into a first spatial index and second tuples into a second spatial index, the first and second spatial indices stored in a non persistent memory;
perform a spatial join of the first and second tuples from the first and second spatial indices during the partitioning;
determine that the non-persistent memory is overflowing; and in response to determining that the non-persistent memory is overflowing, perform a spatial join of first tuples not received in the first spatial index with second tuples from the second spatial index; and
wherein the instructions, when executed, cause the system to further: identify a pair of a first tuple and a second tuple that is replicated on multiple nodes: and to select one of the multiple nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on nodes other than the selected node.

### Claim 32 (depends on 31)

The article of claim 31, wherein the instructions, when executed, cause the system to further:
partition, in each node, first and second tuples among plural buckets when overflow of the non-persistent memory occurs.

### Claim 33 (depends on 32)

The article of claim 32, wherein the instructions, when executed, cause the system to further:
store the plural buckets in stable storage.

### Claim 34 (depends on 33)

The article of claim 33, wherein the instructions, when executed, cause the system to further:
store, in each node, the first tuples in first buckets and second tuples in second buckets in response to the non-persistent memory overflowing; and
perform the spatial join of the tuples in pairs of the first and second buckets.

### Claim 35 (depends on 18)

The article of claim 18, wherein the non-persistent storage is to store first and second indices containing respective redistributed first and second tuples, and wherein performing the spatial join in the first stage comprises performing the spatial join of first and second tuples from the first and second indices.

### Claim 36 (depends on 35)

The article of claim 35, wherein the first and second indices comprise first and second R-tree indices.

### Claim 37 (depends on 35)

The article of claim 35, wherein performing the spatial join in plural stages comprises performing the spatial join in a third stage in which redistributed first tuples are not received in the first index, but the redistributed first tuples not received in the first index are spatially joined with the second tuples in the second index, wherein the third stage occurs before the second stage.
