Fast string searching and indexing using a search tree having a plurality of linked nodes

Claim 2

A search tree for indexing a plurality of string entries, wherein each one of said plurality of string entries is a string of characters, comprising: a plurality of linked nodes consisting of a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets.

Claim 3

The search tree for indexing a plurality of strings of claim 1, wherein the number of characters in each one of said plurality of string entries is the same.

Claim 4

The search tree for indexing a plurality of strings of claim 1, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

Claim 5

The search tree for indexing a plurality of strings of claim 1, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

Claim 6

The search tree for indexing a plurality of strings of claim 1, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

Claim 7

The search tree for indexing a plurality of strings of claim 1, wherein a search of said search tree utilizes a LIFO memory manager for managing a stack having links to at least some of said plurality of linked nodes.

Claim 8

The search tree for indexing a plurality of strings of claim 6, wherein said search utilizes backtracking.

Claim 9

The search tree for indexing a plurality of strings of claim 6, wherein said search utilizes pruning of said stack.

Claim 10

The search tree for indexing a plurality of strings of claim 4, wherein at least some of said reference links form a doubly-linked list.

Claim 15

The method for indexing a plurality of strings of claim 11, wherein the number of characters in each one of said plurality of string entries is the same.

Claim 16

The method for indexing a plurality of strings of claim 11, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

Claim 17

The method for indexing a plurality of strings of claim 11, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

Claim 18

The method for indexing a plurality of strings of claim 11, wherein at least some of said reference links form a doubly-linked list.

Claim 19

The method for indexing a plurality of strings of claim 11, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

Claim 20

The method for indexing a plurality of strings of claim 11, wherein a search of said search tree utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

Claim 21

The method for indexing a plurality of strings of claim 17, wherein said search utilizes backtracking.

Claim 22

The method for indexing a plurality of strings of claim 17, wherein said search utilizes pruning of said stack.

Claim 25

The method for searching for a certain string of claim 20, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

Claim 26

The method for searching for a certain string of claim 20, wherein said traversal utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

Claim 27

The method for searching for a certain string of claim 22, wherein said traversal utilizes backtracking.

Claim 28

The method for searching for a certain string of claim 22, wherein said traversal utilizes pruning of said stack.

Claim 29

The method for searching for a certain string of claim 20, wherein the steps of creating a search tree and forming a query associated with said certain string are performed on a human resources management, financials, logistics, business workflow, personnel management, organizational management, payroll accounting, time management, personnel development or network system.

Claim 32

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to index a plurality of string entries wherein each one of said plurality of string entries is a string of characters, by using a search tree, said search tree comprising: a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets.

Claim 33

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to index a plurality of string entries wherein each one of said plurality of string entries is a string of characters, by using a search tree, said search tree comprising: a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets.

Claim 34

The computer-readable medium of claim 27, wherein the number of characters in each one of said plurality of string entries is the same.

Claim 35

The computer-readable medium of claim 27, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

Claim 36

The computer-readable medium of claim 27, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

Claim 37

The computer-readable medium of claim 27, wherein at least some of said reference links form a doubly-linked list.

Claim 38

The computer-readable medium of claim 27, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

Claim 39

The computer-readable medium of claim 27, wherein a search of said search tree utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

Claim 40

The computer-readable medium of claim 33, wherein said search utilizes backtracking.

Claim 41

The computer-readable medium of claim 33, wherein said search utilizes pruning of said stack.

Claim 42

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, causes said processor to search for a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising the steps of: creating a search tree comprising a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets; wherein said plurality of strings forms a plurality of string entries; forming a query associated with said certain string; and traversing said search tree utilizing said query and providing an index to any of said plurality of strings that matches said certain string.

Claim 43

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, causes said processor to search for a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising the steps of: creating a search tree comprising a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets; wherein said plurality of strings forms a plurality of string entries; forming a query associated with said certain string; and traversing said search tree utilizing said query and providing an index to any of said plurality of strings that matches said certain string.

Claim 44

The computer-readable medium of claim 36, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

Claim 45

The computer-readable medium of claim 36, wherein said traversal utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

Claim 46

The computer-readable medium of claim 36, wherein said traversal utilizes backtracking.

Claim 47

The computer-readable medium of claim 36, wherein said traversal utilizes pruning of said stack.

Claim 48

The computer-readable medium of claim 36, wherein the steps of creating a search tree and forming a query associated with said certain string are performed on a human resources management, financials, logistics, business workflow, personnel management, organizational management, payroll accounting, time management, personnel development or network system.

Claim 49

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to detect or manage a collision of requests of several users accessing a database including a first plurality of string entries, by: maintaining a dynamic lock table including requests of the users; indexing said requests as a second plurality of string entries, wherein each one of said second plurality of string entries is a string of characters, by using a search tree, said search tree comprising: a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said second plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets; and performing a query to the lock table associated with a request of a user to the database before passing the request of the user to the database.

Claim 50

A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to detect or manage a collision of requests of several users accessing a database including a first plurality of string entries, by: maintaining a dynamic lock table including requests of the users; indexing said requests as a second plurality of string entries, wherein each one of said second plurality of string entries is a string of characters, by using a search tree, said search tree comprising: a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said second plurality of string entries, wherein said each one of said plurality of inner nodes further comprises: (a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes; (b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes; (c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position; (d) a reference to at least two successor nodes; and (e) a hash table array containing a predetermined number of hash buckets; and performing a query to the lock table associated with a request of a user to the database before passing the request of the user to the database.

Claim 53

The system of claim 43, wherein the number of characters in each one of said plurality of strings is the same.

Claim 54

The system of claim 43, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

Claim 55

The system of claim 43, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

Claim 56

The system of claim 43, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

Claim 57

The system of claim 43, comprising collision detection or collision management by use of a dynamic lock table.