Data structure and method for pipeline heap-sorting

Details Data structure and method for pipeline heap-sorting Data structure and method for pipeline heap-sorting

2006-02-28

2006-02-28

Gaffin, Jeffrey (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C711S129000

Reexamination Certificate

active

07007021

ABSTRACT:
An improved data structure is provided by modifying a public-domain data structure known as a “heap”. When these improvements are applied, the resultant data structure is known as a “pile.” This invention further describes a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

REFERENCES:
patent: 6105018 (2000-08-01), Demers et al.
patent: 6138123 (2000-10-01), Rathbun
patent: 6442663 (2002-08-01), Sun et al.
patent: 6449214 (2002-09-01), Carr et al.
patent: 2004/0167923 (2004-08-01), Carr
Cormen, Thomas C.; Leiserson, Charles E.; Rivest, Ronald L, Introduction to Algorithms, 24thPrinting, 2000, The Massachusetts Institute of Technology, ©1990, PP 379-419.

Affiliated with

Also associated with

Rating

Data structure and method for pipeline heap-sorting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data structure and method for pipeline heap-sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure and method for pipeline heap-sorting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3638743