Kinetic Data Structures:Sources and Related Materials

By -
Sources and Related Materials

Results not given an explicit reference above may be traced in these surveys.

[32]: An early, and by now somewhat dated, survey of KDS work.

[10]: A report based on an NSF-ARO workshop, addressing several issues on modeling motion from the perspective of a variety of disciplines.

[34]: A “popular-science” type article containing material related to the costs of sensing and communication for tracking motion in the real world.

Comments

Post a Comment

Popular posts from this blog

Searching and Priority Queues in o(log n) Time:Sorting and Priority Queues

By -
Image
Sorting and Priority Queues In the comparison-based model of computation, the cost per element is the same ( O (log n )) for searching and sorting. However, in the RAM model of computation, the sorting problem can be solved faster than searching. The simple intuitive explanation of this is that the bit- parallelism in packed computation can be utilized more efficiently when a number of keys are treated simultaneously, as in sorting, than when they are treated one-by-one as in searching. Even more, it turns out that priority queues can be as implemented as efficiently as sorting. (The intuitive reason for this is that a priority queue can use sorting as a subroutine, and only keep a small part of the queue perfectly sorted.) Thorup [24] has shown the following reduction: TH EOREM 39.6 I f we can sort n key s in time S ( n ) p e r key, then we can implement a p riority queue supporting find-min in constant time and updates (insert and delete) in S ( n ) time. In the following, we wil...
Read more

Online Dictionary Structures:Binary Search Tree Implementations

By -
Binary Search Tree Implementations As pointed out by Gonzalez [4, 5], using a balanced binary search tree (without a trie) and storing each tuple at each node leads to membership (and also insert and delete) algorithms that take O ( d log n ) time, where n is the number of elements in the tree, because one needs to compare the element being searched with the d -tuples at each node. One can go further and claim that for some problem instances it actually requires Θ( d log n ) time. Gonzalez [5] also points out that simple shortcuts to the search process do not work. For example if we reach a node in the search such that the first k components are identical, one may be tempted to conclude that in the subtree rooted at that node one needs to search only from position k + 1 to d in the d -tuples. This is false because the k -component prefixes of all the d -tuples in a subtree may vary considerable in a binary search tree. One can easily show that even the membership operation cannot be im...
Read more

Data Structures for Databases:Data Structures for Query Processing

By -
Image
Data Structures for Query Processing Query evaluation is performed in main memory in several steps as outlined in Figure 60.2. Starting with the high-level input query expressed in a declarative language called SQL (see, for example, [ 2]) the Parser scans, parses, and validates the query. The goal is to check whether the query is formulated according to the syntax rules of the language supported in the DBMS. The parser also validates that all attribute and relation names are part of the database schema that is being queried. The parser produces a parse tree which serves as input to the Query Translation and R ewrite module shown underneath the parser. Here the query is translated into an internal representation, which is based on the relational algebra notation [1]. Besides its compact form, a major advantage of using relational algebra is that there exist transformations (re- write rules) between equivalent expressions to explore alternate, more efficient forms of the same qu...
Read more