The Commons

Back to Results

Patent Title: Indexing method and apparatus facilitating a binary search of digital data

Assignee: IBM
Patent Number: US5613110
Issue Date: 03-18-1997
Application Number:
File Date:01-05-1995


Abstract: An ordered index file is created for archived report data wherein each index file contains a series of 4-byte offsets into the report data. Each offset points to a field within a row of the report data from archival storage. Upon later retrieval from the report data, a binary search is performed for a key(s) that is contained in a search query, using the index field offsets to determine the order in which to retrieve the report data fields. The binary search resolves each key in the search query to a range of index offsets corresponding to report rows that match the query. The search technique optimize final filtering of matches by using the search query that matched the smallest range as the controlling field for resolving overlap of fields in the search query. Since all of the offsets refer to the same report file, this optimization operation compares the offsets of the fields, rather than comparing the field values themselves. A range check is performed before the binary search to determine whether the search key is outside the range of keys that are in the ordered index files, thereby preventing unnecessary searching of indexes that cannot contain the search key(s)

Notes:

Link to USPTO

IBM Pledge dated 1/11/2005