Data processing system with tree and list data structure

• US 5,230,048 A
• Filed: 02/15/1991
• Issued: 07/20/1993
• Est. Priority Date: 09/03/1986
• Status: Expired due to Term

• Current Assignee: Research Investment Network Incorporated
• Original Assignee: Wang Laboratories Incorporated
• Inventors: Moy, Diana Y.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/657,250
• Time in Patent Office: 886 Days
• Field of Search: 395/600, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 12/1804 for stock exchange and similar applications
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A multitask multiuser system provides for efficient transfer of data from a remote data base to individual subscribers and has particular utility in the distribution of stock market data. A primary provider distributes the incoming data directly to user tasks or to an inquiry provider or a monitor provider. The inquiry provider responds to specific inquiries by users for information in the data base. The monitor provider maintains lists of information which are being monitored by the host computer for individual users. The inquiry provider and the monitor provider do not repeat requests to the remote data base where a similar request is already pending from another user. Data transfer paths between task are established by a code module which may be linked to any of the tasks. The transfer paths are established using information from a configuration list and they are monitored by the operating system through a wait list established for each user tasks. Providers in the system may establish subscriber lists through the code module.

Claims

1. A programmed data processing system comprising:

a read/write memory;

means for storing in said memory a first tree structure having nodes each representing a datum of a first data type and pointing to a list having elements each representing a datum of a second data type associated with the datum of said first data type represented by that node;

means for storing in said memory a second tree structure having nodes each representing a datum of the second data type and pointing to a list having elements each representing a datum of the first data type associated with the datum of said second data type represented by that node;

a source of successive data of either of said first and second data types; and

means, responsive to one of said successive data of one of said first and second data types, for searching the one of said first and second tree structures in said memory having nodes representing data of said one of said first and second data types for the node representing said one of said successive data, and retrieving from the list pointed to by that node a datum of the other one of said first and second data type associated with said one of said successive data.

2. A data structure as claimed in claim 1 wherein the data of the first data type identifies services, and the data of the second data type identifies users of the services.

3. A programmed data processing system as claimed in claim 2 wherein the list having elements each representing a datum of the second data type is a list referencing users that made a service request, and the list having elements each representing a datum of the first data type is a list referencing service requests made by a user.

4. A programmed data processing system as claimed in claim 3 wherein the service requests are requests for stock market information.

5. A programmed data processing system as claimed in claim 3 wherein, for each element of the list having elements each representing a datum of the second data type, there is an associated node of the second tree structure, and for such element of the list having elements each representing a datum of the first data type, there is an associated node of the first tree structure.

6. A programmed data processing system as claimed in claim 1 wherein, for each element of the list having elements each representing a datum of the second data type , there is an associated node of the second tree structure, and for each element of the list having elements each representing a datum of the first data type, there is an associated node of the first tree structure.

7. In a data processing system, a method of storing and retrieving data of one of first and second data types associated with a given datum of the other one of said first and second data types, comprising the steps of:

storing in a memory under control of a processor a first tree structure having nodes each representing a respective datum of the first data type and pointing to an associated list of elements each representing a respective datum of the second data type associated with the respective datum of the first data type represented by that node;

storing in the memory under control of the processor a second tree structure having nodes each representing a respective datum of the second data type and pointing to an associated list of elements each representing a respective datum of the first data type associated with the respective datum of the second data type represented by that node; and

searching, in the memory under control of the processor the one of said first and second tree structures having nodes representing respective data of the other one of said first and second data types for the node representing the given datum, and then retrieving from the list associated with that node a datum of the one of said first and second data types associated with the given datum.

8. A method as claimed in claim 7 wherein the data of the first data type identifies service requests and the data of the second data type identifies users that made the service requests.

9. A method as claimed in claim 8 wherein the list having elements each representing a datum of the second data type is a list referencing users that made a service request, and the list having elements each representing a datum of the second data type is a list referencing service requests made by a user.

10. A method as claimed in claim 9 wherein the service requests are requests for stock market information.

11. A method as claimed in claim 9 wherein, for each element of the list having elements each representing a datum of the second data type, there is an associated node of the second tree structure, and for each element of the list having elements each representing a datum of the first data type, there is an associated node of the first tree structure.

12. A method as claimed in claim 7 wherein, for each element of the list having elements each representing a datum of the second data type, there is an associated node of the second tree structure, and for each element of the list having elements each representing a datum of the first data type, there is an associated node of the first tree structure.