Indexing and searching across multiple sorted arrays

Details Indexing and searching across multiple sorted arrays Indexing and searching across multiple sorted arrays

1998-11-13

2001-07-24

Black, Thomas (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C704S007000, C370S392000

Reexamination Certificate

active

06266665

ABSTRACT:

FIELD
This invention relates generally to indexing and searching, and more particularly to such indexing and searching across multiple sorted arrays.
BACKGROUND
In some contexts, programmers desire to index and search across multiple arrays, such as may be stored in different arrays and that may be previously sorted themselves. For example, in the context of providing for autocompletion of statements as described more fully in the applications incorporated by reference, a program may have to display a list box of a given number of sorted elements from all the elements of the different arrays, beginning at a desired position within a global array encompassing all the different arrays.
Within the prior art, the solution to this problem is usually to first create a global array encompassing all the different arrays, and then sorting this array. However, this is a time-consuming process. For example, where each of the different arrays making up the global array consist of hundreds or thousands of elements, the amount of time to construct the sorted global array is great. In the context of providing a list box of a subset of sorted elements of the global array (for example, ten or fifteen such elements) so that the user is able to choose one of the elements, the delay in first creating the global array is significant, such that it is noticed by the user. This makes the use of the list box in picking one of the elements less convenient for the user.
Furthermore, a virtual global array can actually be created, such that indexing thereon is much more easily performed, when the individual arrays do not themselves dynamically change. However, in certain situations, the contents of these arrays are constantly changing. One array, for example, may have a list of members of a current class, while another array may have a list of members of a current function—where the current class and function change, therefore, the contents of the arrays change, too. Other situations in which changing arrays exist include computer games and telephone directories, etc.
There is a need, therefore, for faster searching and indexing across multiple lists.
SUMMARY
The above-identified problems, shortcomings and disadvantages with the prior art, as well as other problems, shortcoming and disadvantages, are solved by the present invention, which will be understood by reading and studying the specification and the drawings. In one embodiment, a method first finds a smallest element of a set of elements, comprising the element of each array of a plurality of arrays, at a pointer for the array. Each array thus has a plurality of elements indexable by the pointer for the array. Next, the method increases the pointer for the array in which the smallest element was found. Finally, the method repeats until a desired number of smallest elements is found.
The invention provides for advantages not found in the prior art. Specifically, for example, the invention provides for a desired sub-array of a virtual global array construed as a sorted union of the elements of the plurality of arrays, by constructing the sub-array without actually constructing the virtual global array first. This provides for faster indexing and searching as compared to the prior art.
The invention includes systems, methods, computers, and computer-readable media of varying scope. Besides the embodiments, advantages and aspects of the invention described here, the invention also includes other embodiments, advantages and aspects, as will become apparent by reading and studying the drawings and the following description.


REFERENCES:
patent: 5121493 (1992-06-01), Ferguson
patent: 5724593 (1998-03-01), Hargrave, III et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6119120 (2000-09-01), Miller
Bhatia et al., “Conceptual Clustering In Information Retrieval,” Systems, Man, and Cybernetics, Part B, IEEE Transactions, v. 28, issue 3, pp. 427-436.*
Bhatia et al., “Testing of Iterative Logic Arrays,” Circuits and Systms, 1990, Procedings of the 33 Midwest Symposium, Aug. 12, 1990, v. 1, p. 243-246.

Affiliated with

Also associated with

Rating

Indexing and searching across multiple sorted arrays does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Indexing and searching across multiple sorted arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Indexing and searching across multiple sorted arrays will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2519391