A weakness of XML dtd

Q: specify that an item contains either text, or text followed by one or more list items
A: since #PCDATA can only be mixed with elements by using
(#PCDATA | someElement)*
the Q cannot be expressed directly

Virtual Reality

A chapter on Reader's digest titled "Magic Helmets" describes the employment of VR for therapy purpose, which is interesting!

MMU (Memory Management Unit)

(MMU, "Paged Memory Management Unit", PMMU) A hardware device or circuit that supports virtual memory and paging by translating virtual addresses into physical addresses.

The virtual address space (the range of addresses used by the processor) is divided into pages, whose size is 2^N, usually a few kilobytes. The bottom N bits of the address (the offset within a page) are left unchanged. The upper address bits are the (virtual) page number. The MMU contains a page table which is indexed (possibly associatively) by the page number. Each page table entry (PTE) gives the physical page number corresponding to the virtual one. This is combined with the page offset to give the complete physical address.

A PTE may also include information about whether the page has been written to, when it was last used (for a least recently used replacement algorithm), what kind of processes (user mode, supervisor mode) may read and write it, and whether it should be cached.

It is possible that no physical memory (RAM) has been allocated to a given virtual page, in which case the MMU will signal a "page fault" to the CPU. The operating system will then try to find a spare page of RAM and set up a new PTE to map it to the requested virtual address. If no RAM is free it may be necessary to choose an existing page, using some replacement algorithm, and save it to disk (this is known as "paging"). There may also be a shortage of PTEs, in which case the OS will have to free one for the new mapping.

In a multitasking system all processes compete for the use of memory and of the MMU. Some memory management architectures allow each process to have its own area or configuration of the page table, with a mechanism to switch between different mappings on a process switch. This means that all processes can have the same virtual address space rather than require load-time relocation.

An MMU also solves the problem of fragmentation of memory. After blocks of memory have been allocated and freed, the free memory may become fragmented (discontinuous) so that the largest contiguous block of free memory may be much smaller than the total amount. With virtual memory, a contiguous range of virtual addresses can be mapped to several non-contiguous blocks of physical memory.

grid computing

Sun's work on using grid computing to support high education

http://www.sun.com/products-n-solutions/edu/whitepapers/pdf/gridcomputing_architecture.pdf

CNGrid is a big Chinese project
WestGrid is a Canada Western site for grid computing

A data grid provides resources to locate, access, transfer, and consume data. Data grids can be used for many purposes, including:

• Building collaborative applications through data sharing. For example, a group of scientists studying the atmospheric ozone layer may collect huge amounts of experimental data per day. These scientists need efficient data storage and access to geographically dispersed storage facilities. Collaborative applications would support data sharing at various locations.
• Processing data using virtual resources such as CPU. In compute-intensive applications, such as the protein folding experiment, algorithm fragments could run independently on distributed resources capable of providing compute power. The data required for executing the algorithm and the resultant data need to be transferred from execution endpoint to other resources or monitoring applications.
• Providing on-demand computing on hosted database systems. SMB-scale applications can use on-demand data centers for hosting, accessing, and executing data through reliable, scalable, and secure mechanisms.

The core functional data requirements for these kinds of grid applications include:

• The ability to integrate multiple distributed, heterogeneous, and independently managed data sources
• Efficient data transfer mechanisms that provide data where the computation will take place, for better scalability and efficiency
• Data caching or replication mechanisms to minimize network traffic
• Data discovery mechanisms to let users find data based on data characteristics
• Data encryption and integrity checks to insure that data is transported across the network in a secure fashion
• Backup and restore mechanisms and policies necessary to prevent data loss and minimize downtime across the grid
• Security for data transport
• Distributed queries and filtering capabilities
• Proper utilization of the powerful capabilities of DBMSs to perform analytical and computational tasks such as complex query execution.

a new virtual platform-- xen!!

Xen is a virtual machine monitor for x86 that supports execution of multiple guest operating systems with unprecedented levels of performance and resource isolation. Linux 2.4, 2.6 and NetBSD 2.0 ports are available. FreeBSD, Plan 9 ports on the way.

Elliptic curve cryptography

The crucial property of an elliptic curve is that we can define a rule for "adding" two points which are on the curve, to obtain a 3rd point which is also on the curve. This addition rule satisfies the normal properties of addition. In math jargon, the points and the addition law form a finite Abelian group.

Alice, Bob, Cathy, David... agree on a (non-secret) elliptic curve and a (non-secret) fixed curve point F. Alice chooses a secret random integer Ak which is her secret key, and publishes the curve point AP = Ak*F as her public key. Bob, Cathy and David do the same.

Now suppose Alice wishes to send a message to Bob. One method is for Alice to simply compute Ak*BP and use the result as the secret key for a conventional symmetric block cipher (say DES).

Bob can compute the same number by calculating Bk * AP, since Bk*AP = Bk*(Ak*F) = (Bk*Ak)*F = Ak*(Bk*F) = Ak*BP.

The security of the scheme is based on the assumption that it is difficult to compute k given F and k*F.

In spite of its small size, Sizzle makes no compromises in terms of security. It uses Elliptic Curve Cryptography (ECC), which has been chosen by the National Security Agency as the next generation public-key cryptographic technology for protecting sensitive U.S. Government information [2].

As far as is known, with the above provisions, if the order of the fixed point F is an n-bit prime, then computing k from k*F and F takes roughly 2^(n/2) operations.

For example, if the order of F is a 240-bit prime, then an attack would be expected to need 2^120 operations.

This is what makes the use of elliptic curves attractive - it means that public keys and signatures can be much smaller than with RSA for the same predicted security.

random walk

the stationary distribution on V is a uniform distribution if the graph is regular, and the stationary distribution is unique(connected graph)

the most important property about stationary distribution is that if the graph is non-bipartite, the distribution V(t) tends to a stationary distribution, with t --> infinity

The surprising fact, is that the mixting time may be much less than the number of the nodes; for an expander graphy, it takes log(n), where an expander is a graph in which the neighborhood of any set of vertices S is large relative to the size of S

The problem of deciding whether a graph is an expander is known to be co-NP-complete

Voronoi diagram

Voronoi diagrams were first discussed by Peter Lejeune-Dirichlet in 1850. But it was more than a half of a century later in 1908 that these diagrams were written about in a paper by Voronoi, hence the name Voronoi Diagrams. The Voronoi cells/polygons are sometimes also called Thiessen Polytopes or Dirichlet Regions.

The Delaunay triangulation is the dual structure of the Voronoi diagram in R². By dual, we mean to draw a line segment between two Voronoi vertices if their Voronoi polygons have a common edge, or in more mathematical terminology: there is a natural bijection between the two which reverses the face inclusions.

orthogonal code & interleaving

When I consider orthogonal code (e.g., 01 and 10 for two sequences), I got the same as the interleaving mechanism, really funnly. If I use 11 and 1-1 like what has been done in CDMA, I will come up with values beyond 1 and 0 so that the length of the signal is actually spreaded almost four times the original signal, which is frustrating in my approach, in other words, the interleaving mechanism is a better choice.

walsh code

Walsh Hadamard codes

Walsh-sequences have the advantage to be orthogonal, in this way we should get rid of any multi-access interference. There are however a number of drawbacks:

• The codes do not have a single, narrow autocorrelation peak. As a consequence code-synchronization becomes difficult.
• The spreading is not very efficient: the energy is only spread over a small number of discrete frequency-components.
  
• Although the full-sequence cross-correlation is identically zero, this does not hold for partial-sequence cross-correlation function. The consequence is that the advantage of using orthogonal codes is lost when all users are not synchronized to a single time base.
• Orthogonality is also affected by channel properties like multi-path. In practical systems equalization is applied to recover the original signal.

An implementation is found written in m language (matlab), which has the following procedures:
1. kroneck Tensor Product
2. Sum the producted different
3. Convolution with the original code
4. get the even number of elements in the convolution result, and divide them by two, then get the original data array

a report on cryptography

Best-Kept Secrets

Quantum cryptography has marched from theory to laboratory to real products

By Gary Stix

in particular, the capability of quantum computers to rapidly perform monstrously challenging factorizations--may portend the eventual demise of RSA and other cryptographic schemes.

a new idea to fix my paper

only consider a 2-dimensional which indexes all bilets contained in XML data, the advantages are listed below:
1. small routing table
2. small update cost
3. uniform distribution of coordinates
4. small world links are cheaper and routing path length is under control
5. simplify the processing of the descendant axis query because no maximum length is needed any more
6. partial hierarchical information is encoded, and hierarchically similar bilets are close in the virtual space so as to facilitate queries with wild cards
7. element-attribute pair and attribute name-value pair are easy to encode in the overlay network
8. the limited size of the dimensionality avoids the curse of dimensionality
9. can employ existing selectivity measurement to facilitate queries (Ashraf Aboulnaga's work)

garage information

Busy Corner Garage

(519) 745-1145

24 Devitt Ave S
Waterloo, ON

scale-free network

A scale-free network is a connected graph or network with the property that the number of links k originating from a given node exhibits a power law distributio