Method and apparatus for generating and searching range-based index of word locations
First Claim
1. A system for generating an index to a database, the system comprising:
- a memory configured to store the index, each index entry including a literal word entry representing a unique portion of information of the database and one or more location entries indicating where the unique portion of information occurs in the records of the database;
a processor configured to generate a plurality of levels of subintervals of an interval, each level including all numeric values of the interval, and each level having a unique set of subintervals, each subinterval of each level comprising at least one numeric value in the interval, the processor further configured to store a representation of each subinterval of each level in the index;
a parser for receiving records of the database and breaking down portions of the records into indexable elements, thereby providing parsed records, the parser further detecting numeric values within the records and providing one parsed record for each subinterval in which each numeric value occurs; and
an indexer for sorting the parsed records and adding the sorted records to the index.
11 Assignments
0 Petitions
Accused Products
Abstract
A method indexes a database so that records including literal values, and numeric values within a specified range can be located. The range is selected from an interval of values. Each record of the database is indexed by storing index entries in a memory. Each index entry includes a literal word entry representing a unique portion of information of the database, and one or more numeric location entries indicating occurrences of the portion of information. A plurality of sets of subintervals are generated from the numeric interval of values. Each set of subintervals includes all of the values of the interval. A first set includes one subinterval for each value of the interval, and each next set includes one interval for a group of adjacent subintervals of a previous set. The subinterval of the last set is the entire interval of numeric values. Each subinterval is represented by a unique literal which can be indexed as a word entry in the index. While indexing the records, some portions of information are identified as range-based values. The range-based values are indexed by storing word and location entries in the index such that there is one word entry for each subinterval which includes the range-based values, the locations indicating occurrences of the range-based portions of information.
108 Citations
12 Claims
-
1. A system for generating an index to a database, the system comprising:
-
a memory configured to store the index, each index entry including a literal word entry representing a unique portion of information of the database and one or more location entries indicating where the unique portion of information occurs in the records of the database; a processor configured to generate a plurality of levels of subintervals of an interval, each level including all numeric values of the interval, and each level having a unique set of subintervals, each subinterval of each level comprising at least one numeric value in the interval, the processor further configured to store a representation of each subinterval of each level in the index; a parser for receiving records of the database and breaking down portions of the records into indexable elements, thereby providing parsed records, the parser further detecting numeric values within the records and providing one parsed record for each subinterval in which each numeric value occurs; and an indexer for sorting the parsed records and adding the sorted records to the index. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A system for searching an index of a database to locate records including numeric values within a selected range, the system comprising:
-
a memory configured to store the index, each index entry including a literal word entry representing a unique portion of information of the database and one or more location entries indicating where the unique portion of information occurs in the records of the database; an interval stored in the index, the interval comprising a plurality of levels of subintervals of the interval, each level including all numeric values of the interval, and each level having a unique set of subintervals, each subinterval of each level comprising at least one numeric value in the interval; a query module for parsing a query received from a user and providing a parsed query, the query module being configured to receive a range-based query; and one or more index stream readers for locating records in the index qualified by the parsed query and providing a list of identified records qualified by the parsed query. - View Dependent Claims (10, 11, 12)
-
Specification