Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View

  Buy Now:   Buy PDF- 17pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
Title: US5884320: Method and system for performing proximity joins on high-dimensional data points in parallel
[ Derwent Title ]


Country: US United States of America

View Images High
Resolution

 Low
 Resolution

 
17 pages

 
Inventor: Agrawal, Rakesh; San Jose, CA
Shafer, John Christopher; San Jose, CA

Assignee: International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
 News, Profiles, Stocks and More about this company

Published / Filed: 1999-03-16 / 1997-08-20

Application Number: US1997000920331

IPC Code: Advanced: G06F 17/30;
Core: more...
IPC-7: G06F 17/30;

ECLA Code: G06F17/30S8M; G06F17/30S4P3P; G06F17/30S4P4P3J;

U.S. Class: Current: 707/104.1; 707/002; 707/100;
Original: 707/104; 707/002; 707/100;

Field of Search: 707/001,5,10,100-105,200-206 364/282.1 706/934

Priority Number:
1997-08-20  US1997000920331

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.

Attorney, Agent or Firm: Tran, Khanh Q. ;

Primary / Asst. Examiners: Black, Thomas G.; Ho, Ruay Lian

INPADOC Legal Status: Show legal status actions

Family: None

First Claim:
Show all 49 claims
What is claimed is:     1. A method for performing proximity join operations on high-dimensional data points in parallel in a multiprocessor system, the join operations being based on a similarity distance between any two data points, the method comprising the steps of:
  • partitioning the data points among the processors;
  • creating an index structure for the data points of each processor, the index structure having a plurality of leaf nodes each corresponding to a subset of the data points;
  • 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.


Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 25 U.S. patent(s) that reference this one

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (25)   |   Backward references (6)   |   Citation Link

Buy
PDF
Patent  Pub.Date  Inventor Assignee   Title
Buy PDF- 17pp US5121494  1992-06 Dias et al.  IBM Corporation Joining two database relations on a common field in a parallel relational database field
Buy PDF- 16pp US5345585  1994-09 Iyer et al.  International Business Machines Corporation Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations
Buy PDF- 21pp US5404510  1995-04 Smith et al.  Oracle Corporation Database index design based upon request importance and the reuse and modification of similar existing indexes
Buy PDF- 33pp US5412806  1995-05 Du et al.  Hewlett-Packard Company Calibration of logical cost formulae for queries in a heterogeneous DBMS using synthetic database
Buy PDF- 13pp US5423035  1995-06 DePrez  Hughes Aircraft Company Method for evaluating relational database queries with automatic indexing and ordering of join components
Buy PDF- 11pp US5542073  1996-07 Schiefer et al.  International Business Machines Corporation Computer program product for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization
       
Foreign References: None

Other Abstract Info: DERABS G1999-214411 DERABS G1999-214411

Other References:
  • T. Brinkoff et al., "Parallel Processing of Spatial Joins Using R-Trees", In Proc. of 12th Int'l Conference on Data Engineering, New Orleans, USA, Feb. 1996.
  • T. Brinkoff et al., "Efficient Processing of Spatial Joins Using R-trees", In Proc. of the ACM-SIGMOD Conference on Management of Data, Washington, D.C., May 1993.
  • E. Hoel et al., "Algorithms for Data-Parallel Spatial Operations", Technical Report CS-TR-3230, University of Maryland, Feb. 1994.
  • R. Agrawal et al., "Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases", Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995, pp. 490-501.
  • N. Beckmann et al., "The R*-tree: An Efficient and Robust Access method for Points and Rectangles", ACM, 1990, p.. 322-331.
  • D.J. Dewitt et al., "The Gamma Database Machine Project", IEEE Transactions on Data and Knowledge Engineering, vol. 2, No. 1, Mar. 1990, pp. 44-63.
  • O. Gunther, "Efficient Computation of Spatial Joins", Proceedings of the 9th International Conference on Data Engineering, Vienna, Austria, 1993, pp.1-27.
  • A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching", ACM, 1984, pp. 47-57.
  • H.V. Jagadish, "A Retrieval Technique for Similar Shapes", ACM, 1991, pp. 208-217.
  • M. L. Lo et al., "Spatial Joins Using Seeded Trees", Presented at SIGMOD 94, Minneapolis, MN, may 1994, ACM, 1994, pp. 209-220.
  • "MPI: A Message-passing Interface Standard", Chapter 1, Unversity of Tennessee, Knoxville, Tennessee, May 5, 1994, pp. 1-14.
  • J. Nievergelt et al., "The Grid File: An Adaptable, Symmetric Multikey File Structure", ACM, 1984, pp. 108-124.
  • J.M. Patel et al., "Partition Based Spatial-Merge Join", SIGMOD 1996, pp. 1-12.
  • J.T. Robinson, "The K-D-B*-Tree: A Search Structure for Large Multidimessional Dynamic Indexes", ACM, 1981, pp. 10-18.
  • T. Sellis et al., "The R*-Tree: A Dynamic Index for Multi-dimensional Objects", Technical Report UMIACS-TR-87-3, CS-TR-1795, University of Maryland, Feb. 1987, pp. 1-24.


  • Inquire Regarding Licensing

    Powered by Verity


    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help