Wednesday, March 4, 2009

SORTS

Definition of Data Structure
  1. Personal
Data Structure is the study of the combination of data and structure working together. Data are facts, information that can be use in the future and Structure serves as the container that holds the data and put it in a proper place.
____
2. http://en.wikipedia.org/wiki/Data_structure

A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide.
_____
3 http://www.webopedia.com/TERM/D/data_structure.html
In programming, the term data structure refers to a scheme for organizing related pieces of information.
_____
4. http://www.cs.sunysb.edu/~skiena/214/lectures/lect1/lect1.html
A data structure is an actual implementation of a particular abstract data type.
_____
5. http://searchsqlserver.techtarget.com/sDefinition/0,,sid87_gci804744,00.html
A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms.
_____
6. http://www.answers.com/topic/data-structure
A collection of data components that are constructed in a regular and characteristic way.
_____
7.http://msdn.microsoft.com/en-us/library/aa289148.aspx
Data structures are abstract structures, or classes, that are used to organize data and provide various operations upon their data.
_____
8. http://www.cplusplus.com/doc/tutorial/structures.html
A data structure is a group of data elements grouped together under one name. These data elements, known as members, can have different types and different lengths.
_____
9.http://www.itl.nist.gov/div897/sqg/dads/HTML/datastructur.html
An organization of information, usually in memory, for better algorithm efficiency, such as queue, stack, linked list, heap, dictionary, and tree, or conceptual unity, such as the name and address of a person. It may include redundant information, such as length of the list or number of nodes in a subtree.
_____
10. http://stats.oecd.org/glossary/detail.asp?ID=2582
Set of structural metadata associated to a data set, which include information about how concepts are associated with the measures, dimensions, and attributes of a data cube, along with information about the representation of data and related descriptive metadata.


Other Data Structure
  • Adjacency list

In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc.

Typically, adjacency lists are unordered.


This undirected cyclic graph can be described by the list {a,b}, {a,c}, {b,c}.

In computer science, an adjacency list is a closely related data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an instance of this type of representation, as can the representation in Cormen et al in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.

One difficulty with the adjacency list structure is that it has no obvious place to store data associated with the edges of a graph, such as the lengths or costs of the edges. To remedy this, some algorithms texts such as that of Goodrich and Tamassia advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex. To complete the structure, each edge must point back to the two vertices forming its endpoints. The extra edge objects in this version of the adjacency list cause it to use more memory than the version in which adjacent vertices are listed directly, but are a convenient location to store additional information about each edge.

  • Scene graph

data structure commonly used by vector-based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.

The scene graph is a structure that arranges the logical and often (but not necessarily) spatial representation of a graphical scene. The definition of a scene graph is fuzzy because programmers who implement scene graphs in applications and in particular the games industry take the basic principles and adapt these to suit particular applications. This means there is no hard-and-fast rule as to what a scene graph should be.

A scene graph is a collection of nodes in a graph or tree structure. A node may have many children but often only a single parent, with the effect of a parent apparent to all its child nodes; an operation applied to a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix (see also transformation and matrix) at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes/objects into a compound object which can then be moved, transformed, selected, etc. as easily as a single object.

It also happens that in some scene graphs, a node can have a relation to any node including itself, or at least an extension that refers to another node (for instance Pixar's PhotoRealistic RenderMan because of its usage of Reyes rendering algorithm, or Adobe Systems's Acrobat 3D for advanced interactive manipulation).

Scene graph implementation

The simplest form of scene graph uses an array or linked list data structure, and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see which shape intersects the mouse pointer (e.g., in a GUI-based applications) are also done via linear searches. For small scene graphs, this tends to suffice.

Larger scene graphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular being a tree. This is the most common form of scene graph. In these scene graphs the composite design pattern is often employed to create the hierarchical representation of group-nodes and leaf-nodes.

Group Nodes - Can have any number of child nodes attached to it. Group nodes include transformations and switch nodes.

Leaf Nodes - Are nodes that are actually rendered or see the effect of an operation. These include objects, sprites, sounds, lights and anything that could be considered 'rendered' in some abstract sense.

Scene graph operations and dispatch

In order to apply an operation to a scene graph, some way of dispatching an operation is needed based upon what node is currently being considered. For example in a render operation a transformation group-node would do nothing more than accumulate its transformation (generally this is matrix multiplication but could involve operations with vector displacement and quaternions or Euler angles instead). Whereas an object leaf-node would send the object off for rendering to the renderer (some implementations might render the object directly but this can integrate the underlying rendering API - e.g. OpenGL or DirectX too tightly and rigidly - it is better to separate the scene graph and renderer systems as this promotes portability.

In order to dispatch differently for different node types several different approaches can be taken, each have pros and cons and are widely disputed among programmers arguing which is best.

In Object-Oriented languages such as C++ this can easily be achieved by virtual functions, the node base class has virtual functions for every operation that can be performed on the nodes. This is simple to do but prevents the addition of new operations by other programmers that don't have access to the source. Alternatively the visitor pattern can be used. This has a similar disadvantage in that it is similarly difficult to add new node types.

Other techniques involve the use of RTTI (Run-Time Type Information). The operation can be realised as a class which is passed the current node, it then queries the nodes type (RTTI) and looks up the correct operation in an array of callbacks or functors. This requires that at initialisation the user/system registers functors/callbacks with the different operations so they can be looked up in the array. This system offers massive flexibility, speed and extensibility of new nodes and operations.

Variations on these techniques exist and new methods can offer added benefits - one alternative is scene graph rebuilding where the scene graph is rebuilt for each of the operations performed, this however can be very slow but produces a highly optimised scene graph. This demonstrates that a good scene graph implementation depends heavily on the application in which it is used.

  • Skip list

A skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).

Underlying the skip list is an augmentation of an ordered linked list with additional forward links, added in a randomized way with a geometric/negative binomial distribution [1], so that a search in the list may quickly skip parts of the list (hence the name). Insert, search and delete operations are performed in logarithmic randomized time.

Description

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly-used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in \log_{1/p} n\, lists.

A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is 1/p, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list. Therefore, the total expected cost of a search is (\log_{1/p} n)/p,\, which is \mathcal{O}(\log n)\, when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.







0 comments: