An active data structure is a data structure with an associated thread or process that performs internal operations.[1] More specifically, an active data structure is associated with a computing resource, which contains one or more concurrently executing processes, and data associated with those processes. Communication is modeled using remote procedure calls, as opposed to shared memory or message passing. The active data structure's internals are hidden behind its RPC interface, and may be accessed concurrently. Common examples include databases and file systems. Active data structures can perform maintenance when resources would otherwise be idle, and present multiple views of the data.[2]
Example
editA queue provided by the hardware or operating system is generally not unbounded, but rather has finite capacity. Suppose that the application has a strong requirement to never lose queue items. Then, the writing process must be modified to save items to a high-capacity storage medium if the queue is full, and the reading process must read the items back. Using the concept of active data structures, one can instead consider an "active queue" which manages saving and retrieving items from the high-capacity storage. Although there are now three running processes instead of two, potentially making synchronization more complex, the high level reader-writer abstraction for using an active queue is still simple and clear.
Formalization
editSelf-adjusting computation is a technique for creating incremental computing programs that maintain internal state and can adjust to new inputs more efficiently than recomputing from scratch. This suggests that active data structures can be formalized by introducing the notion of time to the typical algebraic characterization of data structures. Specifically, Kanat Tangwongsan proposes that an active data structure is an algebra with these three meta-operations:[3]
- perform("operationi(·)", t) will perform the operation operationi at the time t. If operationi(·) returns a value ri, then the meta-operation returns the value ri.
- The meta-operation undo(t) causes an undo of the operation at the time t. This is used for modeling incremental computation.
- The meta-operation update(t) informs the data structure to "synchronize" up to time t. This incorporates information about other processes.
See also
editReferences
edit- ^ "active data structure". xlinux.nist.gov.
- ^ Andrews, Gregory R.; Dobkin, David P. (9 March 1981). Active data structures. 5th International Conference on Software Engineering, ICSE 1981. IEEE Computer Society. pp. 354–362.
- ^ Tangwongsan, Kanat (5 May 2006). Active Data Structures and Applications to Dynamic and Kinetic Algorithms (PDF) (Thesis).
This article incorporates public domain material from Paul E. Black. "Active Data Structure". Dictionary of Algorithms and Data Structures. NIST.