Management in data structures

Details Management in data structures Management in data structures

1998-12-18

2001-10-02

Lintz, Paul R. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06298339

ABSTRACT:

This application claims priority under 35 U.S.C. §§119 and/or 365 to 9704767-4 filed in Sweden on Dec. 19, 1997; the entire content of which is hereby incorporated by reference.
1. Technical Field of the Invention
The invention relates to a direct and space-efficient way of managing symbols, preferrably letters and digits, in data structures.
2. Description of Related Art
When managing or “handling” symbols in data structures, i.e for example storing, deleting or searching, there is a need for both a rapid management and also a management of the symbols which do not use too much of memory space. This need increases of course with the amount of data processed.
Today there exist databases with vast amounts of data, e.g registers of telephone numbers that have to be searched millions of times every day. There are electronic dictionaries and tables of information everywhere in the modern society that are accessed frequently. The searching and storing methods for finding data in these registers are varying and more or less efficient. A common problem is however that the managing of these registers is very space demanding and time consuming and in real time applications the need for a fast and correct result of the management action might be essential.
For example, a typical problem which can arise when dealing with long strings of symbols, e.g telephone numbers is to, as quickly as possible, be able to determine if a given telephone number belongs to a predefined set of numbers. A possible application is for instance numbers which are on a black list, which is not to be accessible for calls from the outside. This example is equivalent to that of finding a given word in an electronic dictionary. A prior art example of this implementation uses data structures which are implemented as linked lists of records. The records are arrays of pointers with an element for each value (e.g a digit). When inserting a black-listed telephone number there will be a linked list of records, terminating in a record where the element for the last number contains a null pointer. Searching through these lists and finding a sequence of numbers which does not belong to anyone of the inserted ones allows the call to proceed. This example will be more clarified with reference to a drawing further down.
This structure allows detection of non-valid numbers with a minimum of information; as soon as a non-present element is encountered or the search tries to continue beyond a null pointer, it can be terminated with a negative result.
The problem with this so called single record type structure is that it is very space-intensive for storing long sequences. In the general case only the initial records in a chain will contain more than one present element. Therefore there will be huge amounts of unused space for the trailing symbols.
Another piece of prior art is published by Sussenguth: “Use of Tree Structures for Processing Files”, Comm of the ACM, Vol 6, no 5, May 1963. Here Sussenguth describes use of tree structures for processing files. The application which is primarily addressed by Sussenguth is that of searching and updating large files with key values of varying length and initial coincidences. A specific application of this is the storage of dictionary data, eg for spelling checkers and translators. This prior art will also be more clarified further down and with reference to a figure.
In the international IBM-application PCT/EP94/02135, a design is suggested where the topic of finding a best match for keys of different length, for instance IP-addresses in a routing system is addressed. However the solution for optimization principles and search methods are different from what is described in the present application.
SUMMARY
In the literature on software engineering the trie (for “reTRIEve”) store/search method is described as a common way of managing “dictionary” data, which are to be searched in order to find out whether a given word exists or not. The space requirements of the trie are also highlighted and various methods for limiting these requirements are proposed. However, there seems to be a lack of methods that in a simple manner conserve space and at the same time retain the speed of the search.
The core of this invention is the way methods from prior art are combined together with new matter to form a solution in which a data structure with a double set of records is used. That is for saving memory space and still have a very high performance for operations in applications where you have to store and search through long sets of records containing symbols, such as digits or letters.
The solution comprises a data structure and a method for, in a datastructure, storing, deleting and finding words or numbers where the double set of records means that a first set is a linked list of records as shown in prior art, but there is also a second list of strings containing the complete numbers. Examples will be given where the advantages of the solution will be apparent and where telephone numbers are used. The invention however, shall not be viewed upon as limited to only that application. Other sequences of symbols than numbers (e.g letters) may be used. The idea may also be used whenever a fast and effective managing of symbols is needed (e.g for searching through electronic dictionaries) and when maximum time/space performance is crucial. The need for a management of such datastructure is obvious when storing/searching subsets of several thousand numbers is done in various telecommunication services and a fast and space-efficient way of doing so is important for the in-service performance of the system.
The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself however, both as to organization and method of operation, together with further objects and advantages thereof, may be best understood by reference to the following description taken in conjunction with the accompanying drawings.


REFERENCES:
patent: 4468728 (1984-08-01), Wang
patent: 4611272 (1986-09-01), Lomet
patent: 5497485 (1996-03-01), Ferguson et al.
patent: 5560007 (1996-09-01), Thai
patent: 5802159 (1998-09-01), Smolentzov et al.
patent: 5930805 (1999-07-01), Marquis
patent: 6065046 (2000-05-01), Feinberg et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: WO96/00945 (1996-01-01), None
patent: WO97/21178 (1997-06-01), None
Douglas Comer, “The Ubiquitous B-Tree”, Computing Surveys, vol. 11, No. 2, Jun. 1979, pp. 121-137.*
Sussenguth, Jr., “Use of Tree Structures for Processing Files,”Comm of the ACM, vol. 6, No. 5, May 1963.

Affiliated with

Also associated with

Rating

Management in data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Management in data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Management in data structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2596706