Data structure and method for pipeline heap-sorting

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

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

     

Profile ID: LFUS-PAI-O-3638743

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.