Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-10-14
2001-09-25
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06295526
ABSTRACT:
TECHNICAL FIELD
This invention generally relates to information retrieval and, more particularly described, relates to processing a memory map related to a database in order to provide listing information about data within the database.
BACKGROUND OF THE INVENTION
One might say that an explosion has rocked the world of information in the form of an ever-increasing amount of recorded and searchable information. To efficiently search for specific information within this ever-increasing amount of information, information retrieval systems have been developed.
Information retrieval systems (“IR systems”) are systems for finding, organizing, and delivering information. A computerized IR system typically responds to data inquiries by routing messages and files between a user interface and a search engine for a database in order to perform a search of the database for desired information.
The time it takes for the IR system to service a data inquiry is usually referred to as the IR system's response time. However, as the IR system becomes more heavily used and as the IR system searches larger and larger databases, response time within the IR system may begin to diminish. Some searches within the IR system may take an undesirably long amount of time to retrieve the desired information. Long response times are very undesirable for the IR system because use of the IR system may seem to be cumbersome and slow. Users of such slow IR systems may then become frustrated and disenchanted with the particular IR system.
For example, in today's world of vast amounts of online digital information, a single database may easily be over 2 Gigabytes. Such large databases may exceed the capacity of a typical hard disk drive used in a conventional computer. Other depositories of information are maintained in huge databases using multiple high capacity memory storage units, such as CD-ROMs or DVD drives. Sifting and searching through such databases may involved loading and unloading multiple disks in order to find the desired information. The time it takes to load and unload multiple disks shows up as an undesirably increased response time.
One way in which to reduce the response time is to maintain the entire database within quickly accessible memory, such as random access memory (RAM). This solution may help to reduce response times because RAM access times are typically faster than most memory storage unit access times. For example, RAM has typical access times of 70 nanoseconds while fast hard disk drives may have typical access times of just less than 10 milliseconds. Thus, copying the entire database into a more quickly accessible form of computer-readable memory can reduce the time an IR system takes to respond to a data inquiry with the desired information.
However, the use of quickly accessible memory to store an entire database can be problematic because the use may not be economically nor physically feasible to accomplish. If the database is very large, the cost associated with outfitting a computer with the appropriate amount of RAM can become astronomical. The cost associated with the RAM may easily eclipse the cost of the rest of the computer.
Additionally, the design of many conventional computers typically includes a limitation on the amount of RAM recognized by the computer system. The ability to recognize only a limited amount of RAM is usually because of the limited addressable memory space within the computer. The addressable memory space is limited because of the width of the address bus within the hardware architecture of the computer. If a database is larger than the amount of addressable RAM, only a portion of the database can be loaded at a time. If only a portion of the database can be loaded at a time, the database is usually searched by swapping in and out other portions of the database to RAM. An IR system using such a computer system that must perform time-consuming swapping operations may be plagued by slow response time problems when responding to a data inquiry.
Even if the computer can support enough memory, the creation of a copy of the database within quickly accessible memory, such as RAM, still may not resolve the response time issue to a user's satisfaction. The use of a copy of the database within quickly accessible memory still requires time spent performing many broad, although quick, searches through a database to find the right information. Accessing the database while the database is resident in RAM is analogous to performing a faster search for the proverbial needle within a haystack. While the searches may proceed quicker, the search for the needle (the desired data) may still take time. This is because the size of the haystack (the size of the database) may still be overwhelming and because the needle (the desired data) could be anywhere within the haystack (the database). Thus, the response time for a search may still rise to an undesirable level for very large databases.
In summary, there is a need for a general solution for quickly performing a search for information represented within a database that (1) maintains a desirable level of response time for users of the IR system, (2) saves memory space within quickly accessible memory, (3) uses a memory map to provide the information without having to incur the response time of actually searching the database in order to provide the information, and (4) focuses any search of the database to a narrow region in order to enhance the response time involved with the search.
SUMMARY OF THE PRESENT INVENTION
The present invention generally provides methods for processing a memory map (also called a memory map module) to provide listing information representing data within a database. The memory map module has an index to the data within the database and has relationship information between the data within the database.
Stated generally, the method begins creating a search query by referring to the memory map. Typically, the search query is created by using one or more target elements from the index. Additionally, the target element is typically pre-validated against the data within the database using the memory map. By pre-validating the target element, the target element is known to be useful in providing listing information based upon the search query.
The index and relationship information within the memory map are searched for the listing information related to the search query. The listing information is delivered as results of searching the memory map.
In one aspect of the present invention, searching the memory map for the listing information may comprise searching the relationship information for a range within the index and then searching the index for the listing information using the range. More particularly stated, the memory map may be searched for the listing information by determining a range reference using a first table of the relationship information and the target element. The range may be determined using a second table of the relationship information and the range reference. The index may then be searched for the listing information using the range.
In another aspect of the present invention, searching the memory map for the listing information may comprise searching the relationship information for each instance of the target element. Each instance of the target element may respectively be mapped to a matching listing within the index. The matching listings for a target element typically determines the listing information for the target element. More particularly stated, a string space may be searched for each instance of the target element. An offset is typically respectively determined for each instance of the target element found within the string space. Each offset is then respectively mapped to a matching listing within the index. The matching listings for each target element are added to a listing set providing the listing information.
Additionally, a display order of the listings may be determined. The display order may be a predetermined order and may be a randomized
Kreiner Barrett Morris
Litwin Edward Paul
BellSouth Intellectual Property Corporation
Homere Jean R.
Kilpatrick & Stockton LLP
Pratt, Esq. John S.
Robinson Greta L.
LandOfFree
Method and system for processing a memory map to provide... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for processing a memory map to provide..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for processing a memory map to provide... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502836