Method and apparatus for executing a binary search in a data cac

Details Method and apparatus for executing a binary search in a data cac Method and apparatus for executing a binary search in a data cac

1995-12-11

1998-08-11

Lintz, Paul R.

Data processing: database and file management or data structures

Database design

Data structure types

707205, 711100, 711118, 711122, 711120, 711143, G06F 1730

Patent

active

057942439

ABSTRACT:
Minimizing data cache misses when performing binary searches. Values in an array to be searched are stored as subsets, clustered to minimize the number of cache misses. A first set of auxiliary values is created consisting of a subset of the first-searched values that fit on one cache line. Subsequent sets of values are then created consisting of one cache line full of values for each value in the first set within one cache line. A binary search is conducted by first searching SET ONE, for the largest array value that is less-than or equal to the search key, or alternatively the smallest array value greater than or equal to the search key. The search of SET ONE, is followed by a search of any subsequent sets of values, with the binary search concluding by testing values within one cache line in the subsequent sets of values until the desired value is found.

REFERENCES:
patent: 4860201 (1989-08-01), Stolfo et al.
patent: 5155832 (1992-10-01), Hunt
patent: 5241638 (1993-08-01), Mork et al.
patent: 5263160 (1993-11-01), Porter, Jr. et al.
patent: 5280613 (1994-01-01), Chan et al.
patent: 5305389 (1994-04-01), Palmer
patent: 5359723 (1994-10-01), Mathews et al.
patent: 5396604 (1995-03-01), Delano et al.
patent: 5404510 (1995-04-01), Smith et al.
patent: 5513344 (1996-04-01), Nakamura
patent: 5537573 (1996-07-01), Ware et al.
patent: 5548742 (1996-08-01), Wang et al.
patent: 5563987 (1996-10-01), Scott
patent: 5577227 (1996-11-01), Finnell et al.
patent: 5586297 (1996-12-01), Bryg et al.
patent: 5590307 (1996-12-01), McClure

Affiliated with

Also associated with

Rating

Method and apparatus for executing a binary search in a data cac 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 and apparatus for executing a binary search in a data cac, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for executing a binary search in a data cac will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-403960