Method for computing transitive closure

Details Method for computing transitive closure Method for computing transitive closure

G - Physics

06

F

354/120

G06F 12/00 (2006.01) G06F 17/30 (2006.01)

Patent

CA 1292574

A METHOD FOR COMPUTING TRANSITIVE CLOSURE Abstract A method and apparatus for creating a transitive closure of a database when the database is stored on a secondary storage in the form of links connecting nodes. The method consists of partitioning the database, transferring one partition at a time from the secondary storage to the main memory, and processing a partition in such a way that accesses to the portions of the database not in main memory are minimized. As much of the unprocessed database as would fit a predetermined fraction of main memory is fetched as one partition, and if, during the processing of this partition, the main memory becomes full, the size of the partition is reduced dynamically by discarding a portion of the database in the current partition, and including this portion in the next partition. The processing of a partition involves, for each node in the partition, the operation of creating a direct connection between every pair of nodes that are indirectly connected through this node.

575102

Affiliated with

Also associated with

Rating

Method for computing transitive closure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for computing transitive closure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for computing transitive closure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFCA-PAI-O-1240455