Source: https://patents.justia.com/patent/6278992
Timestamp: 2019-03-21 09:47:13
Document Index: 675302117

Matched Legal Cases: ['art 1', 'art 1', 'art 1', 'art 2', 'art 2', 'art 2222', 'art 2222']

US Patent for Search engine using indexing method for storing and retrieving data Patent (Patent # 6,278,992 issued August 21, 2001) - Justia Patents Search
Justia Patents US Patent for Search engine using indexing method for storing and retrieving data Patent (Patent # 6,278,992)
As discussed, a database is usually more than a collection of tables. Additional structures, on several levels, help maintain the integrity of the data. A database&apos;s schema provides an overall organization to the tables. The domain of a table column tells us what values may be stored in the column. You can apply constraints to a database table to prevent invalid data from being stored in it. A view is a way of looking at only part of the database at one time. In relational tables, primary and foreign keys are used to connect tables.
Databases make a way of storing information without much work by the applications. Data is stored as data and meta-data in files. The way this is stored is transparent to the application which allows for multiple programs to access the same data using a given database. The database doesn&apos;t even have to be on the same machine as the application. Databases can change without affecting the application to some extent.
If the index location is FULL, this signals that a field of a record having a same first character has already been stored. Accordingly, if the index location is FULL, the record location is saved and a new index is created. The logical or absolute address of the new index replaces the record location that was previously stored in the FULL index location. The record is retrieved from the container 10 using the saved pointer. The cardinality of the character at position ‘A&plus;1’ of the converted string is then preferably used to reference the new index segment using that value as a logical position. The cardinality of the character at position ‘A&plus;1’ of the string of the original record is then also used to reference the new index. If the cardinality of two indexed strings at position ‘A&plus;1’ are equal, then a new index segment must be created as described above and the value at position ‘A&plus;2’ should be used to shape the index. This process may continue until a TERMINATING CHARACTER or a given length to be indexed is reached. Once either happens a segment used for duplicates is preferably created. The preferred method for the duplicate is a wide singly linked list with a reference to the last node, or segment, within the first node, or segment.
If the index contains an address, or pointer, to another index, the index pointed to is then used in conjunction with the next character&apos;s value in the string. The pointer referenced in the string is then used again as described above until an EMPTY index location is found, a TERMINATING CHARACTER reached, or the given length for the index to index has been reached.
Strings may be indexed to a given length (Max_Length, FIG. 6A—steps 30, 32) to save some storage. If the string&apos;s length (String_Length, FIG. 6A—steps 30, 34) is greater than the maximum allowable length to be indexed, then only the characters 0 . . Max_Length can be used to index. Otherwise all characters of the string may be used to index. The flowcharts of the specification assume the maximum length to be one less than actually anticipated and it is preferred that the string&apos;s length not include the terminating character.
Address&equals;Index&lsqb;String&lsqb;Pos&rsqb; &rsqb;
Accordingly, when writing a field value of “100”, it is first converted into “3,2,20”. This converted string is then inserted into an array (i.e. “STRING&lsqb;&rsqb;”). See FIG. 6B. Then the program looks to the first character of the string (preferably starting from the left) to index. Accordingly, “Pos” is set initially to 0. Pos&equals;0 representing the leftmost character of the string. Accordingly, in this example, String &lsqb;0&rsqb; relates to a converted string value of “3”.
Address&equals;Index&lsqb;String &lsqb;0&rsqb;&rsqb;; where String&lsqb;0&rsqb;&equals;“3”
Address&equals;Index&lsqb;3&rsqb;.
Accordingly, Index&lsqb;3&rsqb; as illustrated in FIG. 6C is empty as Index&lsqb;3&rsqb;&equals;0. (If the value was negative it would mean that another index segment is present, and that the second character of the string must be indexed, or if the value was positive, then it means the first index is full and another index must be created.)
Since location 3 of the Index array (i.e. Index&lsqb;3&rsqb;) is empty, the record location of Record “100” may be placed in that slot. Accordingly, Index&lsqb;3&rsqb; is set to “Position” which is the address, or record location, of the Record “100”.
While Pos<Length (FIG. 7—step 40) is true, the data (or “Address”) located in the String&lsqb;Pos&rsqb; of the current index is taken (FIG. 7—step 42). It is then tested to be less than, greater than, or equal to zero (FIG. 7—steps 44, 46). If “Address” is equal to zero, signifying an EMPTY condition, (FIG. 7—steps 40, 42, 44, 46, 48, 50), the data contained in the index is replaced by the position of the record, e.g. address, within the record file (designated by “Position”). In this case the insertion is now complete and should be terminated.
If the data in the index, or “Address”, is greater than zero (e.g., meaning that the index location is full with a pointer to a record location), a new index is preferably created with the negative address of the new index segment replacing the record address previously contained in the index (FIG. 7—steps 56, 58). The new index will now become the current index. The record at the address is retrieved from the record file. The string created from the current field of the new record is used in conjunction with the character at position Pos&plus;1 to fill the new index. Accordingly, Pos should be incremented by one (FIG. 7—steps 60, 62, 64, 66). Again the process continues with the next character within the string until the insertion is complete or Pos no longer is less than Length.
Replace the EMPTY index location of index segment νm;2 corresponding to the second number, or character, of the newly retrieved record with the position of that record within the record file 114. In other words, since the second character of record 1, “100”, is “0”, replace the value of the index location of index segment νm;2 corresponding to character “0” with a FULL.
Check the new index location of the new index (index segment νm;2) corresponding to the second number of record 3 (“150”) for a value of(EMPTY, FULL, POINTER) (step 20).
Add the given record to a record file and obtain a position, here position 5128.
Replace the EMPTY location of index νm;3 pointed to by the second number of the newly retrieved record&apos;s converted string with the position of that record within the record file 140.
Replace the EMPTY address pointed to by the fourth number of the newly retrieved record&apos;s converted string in the index with the position of that record within the record file 148. In other words, since there is no fourth number in “100”, the location of the index segment will be the terminating character or “TC” location.
Check the new index (index segment νm;4) with the next or fourth number of record 5 as a position of the converted string of the record being inserted for a value of (EMPTY, FULL, POINTER) 150.
Swap the FULL value in the index segment νm;4 with a POINTER to the duplicate 154.
EXAMPLE νm;6
EXAMPLE νm;7
EXAMPLE νm;8
Searches of the index structure of the present invention may be performed in various ways. For example, searches for all records having a particular data object may be retrieved. Additionally, boolean searches (AND, OR) searches may be conducted. Additionally, wildcard searches may be performed which retrieves all records containing a predetermined, truncated, string of characters (e.g. searching for all records starting with “Jo” will retrieve “Joe”, “John”, and “Jonathon”; or searching for “Jo&quest;n” will retrieve “Joan” or “John” etc.). Accordingly, a user may search for a group of data objects stored in an index tree structure of the present invention by use of a wildcard. Searching for a group of data objects by use of a wildcard is comprised of the steps of:
a.) entering a search request of a string of search characters followed by a wildcard character (e.g. “Jo&quest;”);
For&equals;7,16,18,0
God&equals;8,16,5,0
so &equals;20,16,0
Loved&equals;13,16,23,6,5,0
the&equals;21,9,6,0
World&equals;24,16,19,13,5,0
Record 1 above (John 3:16) has only one “Position” or address, i.e. Position&equals;“1”. Then a search for “God” or “John” or “3” will retrieve Record 1 because the indexes all contain pointers to Position “1”.
Create a hybrid indexing schema where the first five characters of any string in a database are indexed according to the indexing schema of the present invention while any character after the fifth is indexed according to another known technology (e.g. B-tree). In order to index the name “Johnathon” into an index using such an indexing schema, the first five characters (“Johna”) would be placed in the present invention&apos;s indexing structure using the methods previously described. The fifth index level would then point to the other known database technology where the other known database technology is used to index the last four characters (“thon”) (E.g. A B-tree index structure would be used to index “thon”). (If B-tree is used for the other database structure, it is preferred that separate B-tree structures be created for indexing each different stored combination of the first five characters).
FIG. 29 illustrates the Internet 200, made up of a collection of systems, servers, computers, routers, switches, services and devices linked through a network of multi-connections made up of fiber-links, leased data lines, wireless connections, satellites, local area networks (LANS) and other networking media and connections. The Internet 200 includes computers, systems, resources, devices and servers that provide services such as Domain Name Servers (DNS routing that converts domain names such as ibm.com to an IP address so connections and the passing of information and data can be established between programs and devices), routing of data across the network, transfer of files, e-mail and many more uses. The Internet 200 provides access to tens of thousands of servers or more containing documents, many in HTML (hypertext markup language) format. There are devices such as Cisco&apos;s 2501 202 that convert the data from a leased line to a LAN type connection. There are other devices such as switches, routers, firewalls and other devices that allow for the connection of many systems, servers, users, personal computers and other resources to the Internet 200. FIG. 29 illustrates that the search engine can be connected to the Internet 200 in many locations; locally, nationally or any where in the world where access to the Internet 200 is available. That parts of the search engine(s) can be centralized and/or distributed to other locations on the Internet 200 such as the “get page server”, parts of the “process page server”, complete copies or parts of the databases or complete copies of the search engine can exist anywhere access is available to the Internet 200. This same collection of services known as the Internet 200 and the associated network of computers is used to access documents in servers and systems (devices), provide services to the search engine users and to coordinate and pass data, files, commands, documents and other information between the search engine(s) and it&apos;s functions.
FIG. 30 illustrates an example of a flow diagram involving the user interface with other parts of the search engine and demonstrates the indexing system as it relates to the index server 206 for words. Box νm;1 shows that the system has collected search words and possible conditions from the user. In box νm;2, the words are presented to the (word) index server 206 as shown at point UI1 on both FIGS. 30 and FIG. 32A and 32B. The words in the search engine are eventually converted to and stored as unique numbers. This Index server as described 206 in the search engine system described below is one example of the present invention. As words are presented to the Index 206 as part of a document that is being added or updated, these words either already exist in the Index 206 or are assigned a unique number (through the indexing method) to represent their addition to the Index 206. In the case of a user query as represented in FIG. 30, if they exist, the unique numbers are used to point to documents that contain the words, if unique numbers do not exist for a particular word, that means that no document in the search engine contains the word that is being search for. Words and numbers can be added and indexed as described in the description of the indexing system above. For this example, we will assume that all the words exist in the index to further demonstrate the operation of the index as part of a search engine. The word submitted does not have to be a speak-able or common word. For example “cp2” could be one of the words submitted to the Index server. Using “cp2” as a word, the index server would look at index location “c” in the first level index which in this example corresponds to a character “c”, index location “c” contains a pointer to a second level index block. In the second level index block, position “p” contains a pointer to a third level index block. The third level index block, represents all words that began with “cp”. The third level index block, in position “2” contains a pointer to a fourth level index block for records that start with “cp2” and the unique number that has been assigned to “cp2” in the terminating character position of the fourth level. If we had to go to the fourth level index block to follow words like “cp2st”, in the fourth level index block we would have found the unique number assigned to “cp2” in the terminating character position of the fourth level index block. The word “cp2” takes on a unique number that represents the word “cp2”, that the word itself (“cp2”) does not exist in the index, but by following the positional offsets and pointers, we determine if it does or does not exist in the index. This process is repeated for all words in the search argument, determining the unique numbers that represent the words in the document using the word index in the search engine. FIG. 30 box νm;3 shows the unique numbers (representing words) and associated attributes (must be in title, word must not be in document, etc) being submitted to one of several sets of duplicate servers 208 at point U12 in both FIGS. 30 and FIG. 32A and 32B. The duplicate servers 208 are organized by word (the numeric representation) and contain lists of documents that contain the word. These documents are also organized by other attributes of the documents and their use of the “word”. The numeric word representations and attributes are given to the duplicate server 208, and sets of results are generated that contain pages that contain the desired word(s) and exclude the specified word(s), and then these sets are sorted in most relevant order based on other attributes. In box νm;4 the results from duplicate server(s) 208 are passed back to the user interface server to be combined and re-sorted. In box νm;5 of FIG. 30 the sorted results in the user interface server interfaces with the page server(s) 210 of FIG. 32A and 32B at point U13 to retrieve the corresponding pages (documents) to display to the user.
FIG. 31 illustrates an example of a flow diagram to delete a document from the Search Engine. The URL index as discussed in box νm;1 of FIG. 31 is another example of the present invention and will be explained further in the discussions of FIGS. 32A and 32B. As part of FIG. 31, in box νm;1 the corresponding URL data record in URL server 212 is set to deleted. (Note, if the URL is reused by the owner of the URL address at a later time, the status will again change to updated, and the updated replacement document will be added—or the history of the URL can be deleted and the space reclaimed, or other possible variations). FIG. 31 box νm;2, the Archive server 226 relating to a given URL, would contain a list of all the words (the numeric representation) and attributes contained in that document. Since the document has been deleted, all the words in the Archive server 226 listed for this document and any corresponding attributes will be deleted, see FIG. 32B point DELI. FIG. 31 box νm;3, the corresponding page entries and their attributes as it relates to words are deleted out of the corresponding Duplicate server 208 see FIG. 32B point DEL2.
In FIG. 32, the first server shown is the URL (uniform resource locator) server 212. URL&apos;s are used to locate on the Internet HTML documents, images, audio, video, programs, binary files, domains, servers, computers, devices, functions, other files, and combinations thereof. URL&apos;s can be very long in length, usually over 8 to 30 characters, and in some cases exceeding 150 or more characters in length. The URL index server in the URL server in the search engine is one example of the present invention. Initially, a seed file of URL&apos;s is submitted to the URL server. Using the index technology, each entry is indexed into the index server of the URL server. For example, if the first URL seed entry is “easyresults.com/support/htl” this 27 character string is presented to the URL index server. Using the first letter of the string “e” in the first level index in position “e” a pointer is placed to a second level index. Using the second letter of the string “a” in the second level index in position “a” a pointer is placed to a third level index. Not all characters of the URL may be indexed. Also, certain characters may have the same position. For example, the back slash could map to the same position as the period. Another more common example is mapping upper and lower case characters (A and a) to the same position within the level. In this case the back slashes will be included, so 27 levels of the index will be needed for the URL to be represented. In the 28th level in the terminating character position the URL-ID number will be there. This URL-ID number is unique and represents in this case the 27 character URL in the search engine. In the URL server there are others files as well. One file is a direct indexed fixed length record file by sequential URL-ID that contains attributes about the URL that are contained in the URL server such as: Popularity rating, remote links, size of page, page server, page server position, date last seen, date last updated, date of next check, and various flags and statuses such as deleted, in process, and so forth. Another file in the URL server is a variable length record file that contains the URL-ID and the actual URL with all the special characters; this file provides for backup and rebuilding of the URL index with different attributes, and has other uses in the search engine as well. The URL server(s) receives files and requests for data and functions from the Process Page server(s), the Index (word) server system, the Split server, and numerous other servers in the search engine and from possible other servers outside the search engine. The URL server(s), after adding new URL&apos;s to the index, then creates files of new URL&apos;s discovered, retrieves the IP addresses from the DNS server, and creates files that are passed on to the next server(s), the Get Page server 216.
In FIG. 32, the second server shown is the Get Page server 216. This server 216 is also commonly referred to as a “web walker”, “spider”, “browser”, “robot” and other names in the industry. This server2l6 requests files from the URL server as needed, and then using the URL and IP addresses, the Get Page server 216 then requests the documents as a user would on the Internet (web). The Get Page server 216 has the ability to follow pages that are make up of other pages and requests the IP address form the DNS server on the Internet. The Get Page server 216 collects files that are representative of the URL&apos;s it received from the URL server and pages it followed as it was forwarded (like a user would be). The Get Page server 216 also processes requests and functions, and makes requests and functions of other servers in and out of the search engine. The Get Page server 216 , as all or most servers, can exist at remote and local sites and can contain multiple copies of itself on a computer system(s). The Get Page server 216 builds files of its results to pass on to other servers as requested.
In FIG. 32, the third server shown is the Process Page—part 1 server 220. The Get Page and Process Page—part 1 can be easily remoted as server pairs to locations all over the web. This was done to allow the pair to be closer to the pages being spidered, for better performance and possible lower costs, and other considerations. This remoting and multiple occurance of the servers can apply to most if not all the servers in the search engine as well as servers shown in FIG. 32 that are not directly a part of the search engine. The Process Page—part 1 server 220 performs functions such as: parse each document (page) to strip off all ULR&apos;s found, all email addresses found, determine the home server and domain, sense type of page and attributes (color, font, pictures, objects, etc.), parse title, parse description, meta-tags, features, ranking assignments, look for spamming (hidden words, where the words are the same color as the background so a user will not see them but a spider will), parse computer code, html and other information. After the parsing is done, the processed files are compressed, to be sent to other servers. Some processed files may be sent as batches, such as email addresses to an email server system.
In FIG. 32, the fourth server shown is the Process Page—part 2 server 222. The Process Page—part 2 server 222 performs functions such as: uncompress data, save titles, save or create descriptions, parse all words, determine root words and exact words (horses is also horse, this greatly expands the words in a page), rank words, location of words, frequency of words, and other processing and operations. In this Process Page—part 2222, one example of the present invention is use of the index technology to collect the word count and ranking of the words on the page and create a unique list of words on the page (document). For each document, a temporary index and word list is generated for the document, then as each word is parsed, it is added to the index and the word count and ranking is stored in the index. If this is the first time the word has been added to the index, the word is also added to a list. By the end of the document, a word list has been generated and the index for the list contains word count and ranking information. This is just one example of the use of the indexing technology as it relates to and improves the processing of data for a search engine. As each document is processed by Process Page—part 2222, files are created for further processing. This server 222 interfaces to other servers and systems as needed, to provide functions and services.
In FIG. 32B, the Split server 224 receives files from the URL server 212. The split server 224 processes these files, and if the document is new, the split server 224 assigns the Process page server 210 (triplet of servers 210, 226, 208). If the document is pre-existing the split server 224 forwards the document to its current triplet PAD (Page, Archive, and Duplicate) 210, 226, 208 of servers. The Split server 224 allows for the search engine to add PAD&apos;s as the files grow, and for the search engine to re-balance the load on PAD&apos;s as the document (file) updates and users place loads on the search engine and the PAD&apos;s. The Split server 224 generates files that are further processed by the Triplet PAD&apos;s (the PAD&apos;s are in mated sets of three relate servers (triplets)). The Split server(s) 224 like all servers, have files, perform functions and services, and request and provide services to other servers.
In FIG. 32B, the Page server 210 receives it&apos;s files from the Split server(s), and based on records that are in the files for this Page server 210, the Page server 210 updates the existing information stored in the Page server 210 with the newer information if the document already exists, otherwise the information is added to the Page server 210. Some of the information contained in the Page server 210 is as follows: title, description, size in bytes, URL, URL-ID, last updated date, popularity information, relevance data, and other data and processing. Not all data stored in the Page server 210 is available to the user interface. The remaining words and their relevance and other data is placed into files for the related set Archive server. The Page server(s) 210 like all servers, have files, perform functions and services, and requests and provides services to other servers. For new pages, the Page server 210 generates files to be sent to the URL server 212.
In FIG. 32B, the Archive server 226 that is part of the PAD set, receives files from it&apos;s associated Page server 210. The Archive server 226 processes the files it receives, and performs some of the following functions:
If the document already exists in the Archive server 226, the Archive server 226 compares the new word list and each word&apos;s Relevance, as well as other data associated with the document to the existing word list (old words) of the document and each of the old word&apos;s relevance. For all new words and their relevance that differ from the old words or their relevance, a file is generated for the associated Duplicate server 208; old words that no longer exist in the newer version of the document are placed in a delete file, new words that now exist in the newer document with their relevance are placed in an add file, and words that have changed their relevance but still exist are placed in the delete file and then the add file with their relevance (an update function could be used in place of the delete and add procedure to achieve the same result).
FIG. 33 shows an example of a compressed index array of the present invention. By using compression for the index blocks where efficient, and given the fact that the actual values being indexed are not stored in the index, the index&apos;s RAM Memory and disk storage becomes competitive in size with B-tree and other index technologies (while providing other significant advantages over these technologies, namely speed). In the example of FIG. 33, the compression technique uses a 48 bit binary map. The mask used for the bit map is (usually) the same positional map that is used for the basic indexing, that means that if the character “c” index entry would be in the third position of an index block, then the character “c” would be represented by the third bit in the bit map. The compression technique is comprised of: a bit map and positions for pointers, where the pointers may or may not be stored in the base index array 230.
As an example, if we were looking for the pointer for character “k”, we would first check to see if the bit representing “k” was set to “1”. (For this example, we will assume that “k” does exist.) Since its position in the bit mask is set to “1”, then the pointer for “k” is present in the pointer positions 236 in the base array 230 or an overflow block 232. Next we need to determine what position the “k” pointer represents in the sequence of pointers that are represented. Since all pointers are not normally represented, we count all the bits set to “1” up to and including “k” to determine what positional location to find the “k” pointer. For this example we will assume that “k” is the sixth bit turned on, and hence “k” pointer will be in the sixth pointer&apos;s position.
For this example embodiment, there are 128 bit long base and overflow blocks (i.e., arrays) and 32 bits are needed for each of the pointer locations in the base and overflow blocks which allows up to two pointer positions in a base array (and the 48 bit map), and up to four pointer positions in an overflow block. Since the “k” pointer plus the preceding number of pointers is 6 or greater, for this example, the second pointer 236 in the base array 230 is used to as a pointer to the first overflow block 232 (the last pointer of each overflow block 232 is either empty, a pointer to an over flowblock or the pointer for a character in the bit map). This leaves room in the base array 230 in pointer position 1236, to store the pointer corresponding to the first character stored in the bit map. The second pointer position in the base array 230 for this example, is needed to point to the overflow block 232. (If there were only 2 characters represented by the bit map, the second pointer position in the base array 230 would contain the pointer value for the second character and no overflow block 232 would be needed.) The first overflow block 232 would contain three more pointers in the first three positions corresponding to the additional characters before “k” in the bit map (in their sequential order) and the fourth pointer position points to a second overflow block (not shown).
Accordingly, in the second overflow block in the second pointer position we would find the pointer corresponding to the sixth bit map position, i.e., the pointer for “k”. This second overflow location could be the current end of the chain if eight or less characters were represented by the bit map. An typical index block (not compressed) would take 48×32 bits&equals;1536 bits of storage (the bit map represented 48 characters) while in the example using compression 230, if 5 to 8 characters were present, 128 bits×3&equals;384 bits of storage were needed
FIGS. 34A and 34B illustrate a flowchart of one embodiment of the present invention were compressed index arrays are used for data retrieval. With regard to FIGS. 34A and 34B, assume that the data has been indexed according to the compressed indexing structure as described with reference to FIG. 33. As shown in FIG. 34A, let us assume that we are looking for string of characters in the indexed structure where one character is denoted by String &lsqb;pos&rsqb; (the character of the string at position pos). It is also preferred that the value of String &lsqb;pos&rsqb; is the position of the BITMAP. Accordingly, for FIG. 34A, the value of BITMAP &lsqb;string &lsqb;pos&rsqb;&rsqb; is the valued stored in the BITMAP corresponding to the String&lsqb;pos&rsqb; position. If the value returned is a “0” block 240, that particular data item is not found in the index 242. If the value returned is “1”, there is a corresponding record. To find the position of the next index level, the pointer needs to be retrieved. To determine which location of the compressed index array stores the pointer for the String&lsqb;pos&rsqb; location, the bits from the BITMAP from position to 0 to the String &lsqb;pos&rsqb; are scanned. These bits are counted to determine the position (X) of the pointer in either the base array 230 or the overflow arrays 232 (see block 248 in FIG. 34A). Accordingly, the location of the next index array can be retrieved.
Inventors: John Andrew Curtis (Plain City, OH), Gordon Frank Scherer (Westerville, OH)
Application Number: 09/251,882
Current U.S. Class: 707/3; 707/2; 707/100; 707/103; 707/500; 707/513