# US 2003/0225779 A1 · Inverted index system and method for numeric attributes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0225779 A1
- Document ID: US20030225779A1
- Status: Published application
- Kind: A1
- Application number: 10/160,763
- Filed: 2002-05-31
- Published: 2003-12-04
- Earliest claimed: 2002-05-31
- Assignees: Oracle International Corporation
- Inventors: Yasuhiro Matsuda
- Web page: https://patentgrep.com/patent/US20030225779A1

## CPC

- G06F 16/319: {Inverted lists}
- Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A system and method is provide for generating an inverted index and processing search queries using the inverted index. To increase efficiency for queries having multiple numeric range conditions, numeric attributes are tokenized into a plurality of tokens based on their binary value. The tokens become keys in the inverted index. A numeric range query is translated into a query on multiple tokens and combining two or more range queries on different attributes becomes a simple merge of document identification lists.

## Claims

### Claim 1

A system of generating an inverted index from a data repository, the system comprising:
a data retriever for retrieving selected numeric attributes from the data repository;
a tokenizer for generating a plurality of tokens from each of the numeric attributes based on a binary value of each numeric attribute; and
an indexer for generating an inverted index using each of the plurality of tokens as a key.

### Claim 2 (depends on 1)

The system as set forth in claim 1 wherein, for a numeric attribute having a binary value represented by n-bits, the tokenizer generates n-tokens from the binary value.

### Claim 3 (depends on 2)

The system as set forth in claim 2 wherein each token of the n-tokens includes a different number of bits from the binary value.

### Claim 4 (depends on 2)

The system as set forth in claim 2 wherein an i-th token from the n-tokens has a length of i-bits.

### Claim 5 (depends on 1)

The system as set forth in claim 1 wherein the system is embodied as computer executable instructions.

### Claim 6 (depends on 1)

The system as set forth in claim 1 wherein the inverted index is a b-tree structure.

### Claim 7 (depends on 1)

The system as set forth in claim 1 wherein the inverted index is a hash index.

### Claim 8 (depends on 1)

The system as set forth in claim 1 wherein the inverted index is an array structure.

### Claim 9 (depends on 1)

The system as set forth in claim 1 further including logic for generating a binary value for each numeric attribute that represents the numeric attribute.

### Claim 10

A process of generating an inverted index from numeric values contained in a data repository, the process comprising the steps of:
determining a binary value for each of the numeric values;
tokenizing the binary value, for each numeric value, into a plurality of bit tokens where each of the plurality of bit tokens includes a different number of bits from the binary value; and
generating an inverted index using the plurality of bit tokens from each numeric value as an index key.

### Claim 11 (depends on 10)

The process as set forth in claim 10 wherein the binary value includes n-bits and the tokenizing step creates n-tokens from the binary value.

### Claim 12 (depends on 10)

The process as set forth in claim 10 wherein the generating step includes generating an index entry having a form of (attribute, token, list) where list is a list of entities that contain the attribute and the token.

### Claim 13 (depends on 10)

The process as set forth in claim 10 wherein the inverted index is generated as a b-tree.

### Claim 14 (depends on 10)

The process as set forth in claim 10 wherein the inverted index is generated as a hash index.

### Claim 15 (depends on 10)

The process as set forth in claim 10 wherein the inverted index is generated as an array structure.

### Claim 16 (depends on 10)

The process as set forth in claim 10 wherein the determining step includes setting a predetermined length for the binary value.

### Claim 17

A method of data retrieval from a data repository in response to a query having a numeric operand, the method comprising the steps of:
providing an inverted index generated from the data repository, the inverted index having an index key formed from an attribute in the data repository having numeric values, the index key being based on a binary value of the numeric values;
determining a binary value for the numeric operand;
tokenizing the binary value of the numeric operand into a plurality of tokens each having a different number of bits; and
retrieving data from the inverted index by searching the inverted index based on a correspondence between the plurality of tokens and the binary value of the indices.

### Claim 18 (depends on 17)

The method as set forth in claim 17 wherein if the query includes a greater-than operator, the retrieving step includes:
selecting tokens from the plurality of tokens that end in a zero bit;
converting the zero bit of the selected token to a one bit; and
matching the converted tokens to the binary values of the indices in the inverted index.

### Claim 19 (depends on 17)

The method as set forth in claim 17 further including wherein if the query includes a less-than operator, the retrieving step includes:
selecting tokens from the plurality of tokens that end in a one bit;
converting the one bit of the selected token to a zero bit, and
matching the converted tokens to the binary values of the indices in the inverted index.

### Claim 20 (depends on 17)

The method as set forth in claim 17 wherein the query includes multiple numeric operands, the method further includes:
repeating the determining, tokenizing and retrieving steps for each numeric operand; and
merging data retrieved from each numeric operand in accordance with the query to obtain a resultant data list.

### Claim 21 (depends on 17)

The method as set forth in claim 17 wherein the retrieving step retrieves a list of entity identifiers that are associated to an index that matches one of the plurality of tokens.
