Search engine using indexing method for storing and retrieving data

• US 6,278,992 B1
• Filed: 02/17/1999
• Issued: 08/21/2001
• Est. Priority Date: 03/19/1997
• Status: Expired due to Term

• Current Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Original Assignee: Excellerate LLC
• Inventors: Scherer, Gordon Frank, Curtis, John Andrew
• Primary Examiner(s): Choules, Jack
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/251,882
• Time in Patent Office: 916 Days
• Field of Search: 707/3, 707/103, 707/10, 707/2, 707/100, 707/500, 707/513
• US Class Current: 707/711
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A Search Engine utilizing a method and system for efficient storage and retrieval of data. The system comprises a record file, an index file, a duplicate segment file and access to a network of computers. The index files contains locations of data items, pointers to other index files, or an empty designation. The index files are arrays that contain locations corresponding to a predetermined range of characters with which the data items may be formed. Data items are stored according to the character strings of each data item. The first portion of a data object is indexed according to the indexing method of the present invention while a second portion of the data object is indexed according to another known database technology, such as B-tree.

Claims

1. A method for storing data for rapid retrieval, comprising the steps of:

creating a plurality of index arrays having locations wherein said locations are associated with a character or group of characters;

providing a record file for storing a plurality of data items, each of said data items having a string of characters, wherein said locations of said plurality of index arrays are adapted to store either a pointer to a second index array or a second data item and wherein at least one of said plurality of index arrays is adapted to store a pointer to another database indexing structure;

indexing a first predetermined portion of each of said plurality of data items in said plurality of index arrays;

pointing to said another database indexing structure;

indexing a second predetermined portion of each of said plurality of data items in said another database indexing structure; and

wherein said another database indexing structure is a B-tree indexing structure.

2. A method according to claim 1 wherein said another database indexing structure is a hash indexing structure.

3. A method of indexing a collection of data objects, wherein a tree index structure is used in combination with a predetermined second indexing structure, comprising the steps of:

creating a first level index array;

expanding the levels of said tree index structure to a plurality of additional layers of index arrays and wherein said first level index array and each of said index arrays in said plurality of additional layers of index arrays have a plurality of locations corresponding to at least one character of a predetermined list of characters;

indexing a first predetermined portion of a data object in said first level index array and in each of said plurality of additional layers of index arrays;

pointing to said predetermined second indexing structure;

indexing a second portion of said data object in said second indexing structures; and

wherein said second indexing structure is a B-tree indexing structure.

4. A hybrid indexing structure for indexing a plurality of data objects comprising:

a plurality of index segments, said plurality of index segments having locations associated with a character or group of characters, and wherein said locations of said index segments are adapted to store either a pointer to another index segment or a second data element;

a second database structure pointed to by at least one location of one index segment;

wherein a first portion of each of said plurality of data objects are indexed by said plurality of index segments and a second portion of each of said plurality of data objects are indexed by said second database structure; and

wherein said second database structure is a B-tree structure.

5. A system according to claim 4 wherein said second data element is a pointer to one of said plurality of data objects.

6. A system according to claim 4 wherein said second data element is a pointer to said second database structure.

7. A system according to claim 4 wherein each one of said index segments corresponds to a predetermined character position of said data objects.

8. A hybrid indexing structure for indexing a plurality of data objects comprising:

a first database structure;

a plurality of layers of index segments, each of said index segments having locations wherein each of said locations are associated with a character, and wherein said locations of said index segments are adapted to store either a pointer to another index segment or a second data element, wherein said first database structure points to said at least one of said index segments from said plurality of layers of index segments;

wherein a first portion of each of said plurality of data objects are indexed by said first database structure and wherein a second portion of each of said plurality of data objects are indexed by said plurality of layers of index segments; and

wherein said first database structure is a B-tree structure.

9. An indexing process for use in Internet search engines, comprising the steps of:

retrieving a collection of data items from the Internet, said collection of data items associated with an address;

indexing said data items, said indexing further comprising the steps of;

a. creating a plurality of index arrays, each of said index arrays having locations wherein each of said locations is associated with a character or group of characters;

b. indexing a first predetermined portion of each of said plurality of data items in said plurality of index arrays;

c. configuring at least one of said index arrays with a reference for each unique data item, said reference used to locate an address associated with each of said indexed data items; and

d. wherein said reference is stored in a terminating character position of one of said index arrays.

10. An indexing process according to claim 9, wherein a first level index array corresponds to a first character of said data items to be indexed and wherein a second level index array corresponds to a second character of said data items to be indexed.

11. An indexing process according to claim 9, wherein said reference is a unique numerical value associated with a corresponding unique data item.

12. An indexing process according to claim 11, further comprising the step of:

associating each of said unique numerical values with all addresses of said collections of data items containing said data item referenced by said unique numerical value.

13. An indexing process according to claim 12, wherein said collection of data items is a web page and wherein said address is a URL.

14. An indexing process according to claim 9, wherein said reference is a record location for a record containing addresses of all collections of data items containing said data item.

15. An indexing process according to claim 9, wherein said address is a URL.

16. An indexing process according to claim 9, further comprising:

providing a separate index structure for each of said URLs of said collection of data items retrieved.

17. An indexing process for use in Internet search engines, comprising the steps of:

retrieving a Web page from said Internet, including a URL associated with said retrieved Web page;

indexing data items from said Web page, said indexing further comprised of the steps of;

a. creating an index structure by creating a plurality of index arrays, each of said index arrays having locations wherein each of said locations is associated with a character or group of characters, wherein said locations of said plurality of index arrays are adapted to store either a pointer to another index array or a second data element;

b. associating a unique reference for each unique data item in said index structure;

associating each of said unique references to Web pages containing said unique data items; and

wherein said unique reference for each unique data item is stored in a terminating character position of said index structure.

18. An indexing process according to claim 17, wherein said unique reference is a number.

20. An indexing process according to claim 17 wherein at least one of said plurality of index arrays stores pointer to another database indexing structure.

21. A method for indexing Internet pages for subsequent searching and retrieval, said method comprising:

providing a first index structure, said index structure having a plurality of index arrays, wherein each of said index arrays has a predetermined number of locations and wherein each of said locations is associated with a character and, wherein one of said locations of each of said index arrays corresponds to a terminating character reference;

obtaining a first data item from a first Internet page;

determining a first character of said first data item;

placing a pointer to a second level index array in a location of a first level index array corresponding to said first character;

indexing the remaining characters of said first data item in said index structure;

placing a pointer to a last index array in an index array and index location corresponding to a last character of said first data item; and

placing a reference value in a terminating character location of said last index array, wherein said reference value is used to retrieve the location of the Internet page.

19. An indexing process according to claim 22, further comprising the step of:

expanding said index structure to accommodate all unique combinations of said characters or group of characters.

22. A method according to claim 21, wherein said reference value is a unique numerical value assigned to said first data item.

23. A method according to claim 21, further comprising the step of:

using said reference value to look up all locations of Internet pages containing said first data item.

24. A method according to claim 21, wherein said location of said Internet pages are URLs.

25. A method according to claim 24, further comprising the step of:

providing a second index structure for indexing all retrieved URLs.

26. A method according to claim 25, wherein a URL reference value is assigned to each indexed URL.

27. An index structure for indexing data items retrieved from an Internet web page, said index structure comprised of:

a plurality of index arrays, said index arrays having a predetermined number of locations and wherein each of said locations is associated with at least one character;

wherein said locations of said index arrays are adapted to hold a pointer to another index array or another data element;

wherein said data element is a reference value used to retrieve locations of Internet pages;

wherein said reference value is a unique numerical value assigned to a unique data item indexed in said index structure; and

wherein said unique numerical value for each unique data item is stored in a terminating character location of an index array.

28. An index structure according to claim 27, wherein said character may be any character or symbol that may be found on a web page.

29. An index structure according to claim 27, wherein said unique numerical value is used to retrieve all locations of web pages containing the unique data item assigned to said unique numerical value.

30. An index structure according to claim 27, wherein said reference value used to retrieve locations of said Internet pages is stored in a terminating character location of an index array.

31. An index structure according to claim 30, wherein said terminating character for each unique data item follows the last character of said data item.

32. An index structure for indexing a data item, comprising:

a first index array, said first index array further comprised of;

a. a first portion having a predetermined number of locations, each of said locations corresponding to a predetermined character or group of characters;

b. a first pointer location for storing a pointer to another index array or a reference value, wherein said reference value is used to locate web pages containing the data item; and

c. wherein said first pointer and said first pointer location are located in non-continuous locations in memory.

33. An index structure according to claim 32, wherein said first portion stores a “

1”

bit in a location to represent a “

full”

value.

34. An index structure according to claim 32, wherein said first index array is further comprised of a second pointer location and wherein said second pointer location is adapted to store a pointer to another index array or to an overflow pointer array.

35. An index structure according to claim 34, wherein said overflow pointer array is adapted to store a pointer to another index array or another overflow pointer array.

36. An engine utilizing said index structure of claim 32 for indexing data retrieved from Internet web pages.

37. An engine according to claim 36 wherein URL associated with each of said Internet web pages are indexed in a separate index structure.

38. An index structure according to claim 32, wherein said first index array is further comprised of a counter location for tracking the number of set bits stored in said bitmap portion.

39. An index array according to claim 32, wherein the number of pointers to other index arrays corresponds to the number of set bits in said first portion.

40. An index array according to claim 39, wherein the first location of said first portion of said index array (from leftmost most position to rightmost position) that is “

full”

is associated with a pointer stored in the first pointer location.

41. An index array according to claim 32 wherein one of said locations in said first portion relates to a terminating character value.

42. An index array according to claim 32 wherein said index structure indexes data retrieved from the Internet allowing subsequent search and retrieval.

43. An index array according to claim 32, wherein said reference value is a location in memory for storing references to Web pages.

44. An index structure for indexing a data item, comprising:

a first index array, said first index array further comprised of;

a. a first portion having a predetermined number of locations, each of said locations corresponding to a predetermined character or group of characters;

b. a first pointer location for storing a pointer to another index array or a reference value, wherein said reference value is used to locate web pages containing the data item; and

c. wherein one of said locations in said first portion relates to an unknown character.

45. An index structure for indexing a data item, comprising:

a first index array, said first index array further comprised of;

a. a first portion having a predetermined number of locations, each of said locations corresponding to a predetermined character or group of characters;

b. a first pointer location for storing a pointer to another index array or a reference value, wherein said reference value is used to locate web pages containing the data item; and

c. wherein said reference value is a unique numerical value assigned to a particular data string.

46. An index structure for indexing a data item, comprising:

a first index array, said first index array further comprised of;

a. a first portion having a predetermined number of locations, each of said locations corresponding to a predetermined character or group of characters;

b. a first pointer location for storing a pointer to another index array or a reference value, wherein said reference value is used to locate web pages containing the data item; and

c. wherein said first portion is a bitmap portion.