Scalable extension of the H.264/AVC video coding standard

The main idea behind the scalable extension of H.264/AVC is to take the block based hybrid video
coding scheme one step further and achieve spatiotemporal and signal-to-noise-ratio (SNR)
scalability. The term scalability in the video coding context means that physically meaningful
video information can be recovered by decoding only a portion of the compressed bit stream.
For example, one should be able to recover from the compressed bit stream a video with lower
resolution than the original by decoding only the lowest spatial layer and discarding other
spatial layers. In SVC, scalability is achieved by taking advantage of the layered approach.
The structure of the encoding depends on which kind of scalability is needed. For example, Figure 1
depicts the block diagram of an SVC encoder with two spatial layers, which contain additional
SNR enhancement layers.

In each spatial layer hierarchical motion compensation and prediction is made. The redundancy
between adjacent pictures and layers is based on interand intraprediction techniques. After
motion compensated prediction, transform coding is applied using the same transformation
techniques as in the H.264/AVC standard. SNR and quality scalability is achieved by coding the
difference between transformed and not transformed slices using progressive coding. These
progressively coded slices can then be truncated at any position within each slice thus improving
the userperceived visual quality proportional to the number of bits included in the truncated
slice. Mean while, temporal scalability is achieved using hierarchical B pictures, which provide a
predictive structure already included in H.264/AVC. Motion compensated temporal filtering can also
be used but it is, for the time being, included as a non-normative option only for achieving
temporal scalability. An example of hierarchical coding structure for group of pictures (GOP)
which length is eight pictures is illustrated in Figure 2. All of these scalability modes can be
combined to achieve three dimensional (spatial, temporal and SNR) scalability.

Figure 1: Block diagram for the H.264 scalable extension

Figure 2: Hierarchical GOP structure

The dependency between layers in scalable video coding

Layers in scalable video coding are classified as a base layer and enhancement layer(s). In SVC, the
base layer can be decoded using a standard H.264/AVC decoder. Information from lower layers is used
to remove the redundancy between different layers. This increases coding efficiency but it also
increases the importance of the lowest layers during decoding process and reduce error resiliency.
If the base layer or one of the most important layers is lost, less important layers are useless
because decoding them requires redundant data from the most important layers. The dependency between
layers makes the prioritization of different layers during transmission suitable. The base layer
also usually needs less transmission bandwidth than the enhancement layers, which is also quite
important when allocating resources to different prioritization classes. Based on the SVC layer
prioritization suitability we propose a mechanism for adapting the video transmission to rapidly
changing wireless channel and network conditions. One of the main requirements for the architecture
is to be general enough to work with different access networks from IEEE 802.11 (WiFi) and
IEEE 802.16 (WiMAX) to 3GPP and UMTS.

E-negotiation system based on intelligent architecture

E-negotiation process model and protocol provide plausible method for negotiation systems and remove
additional activities of the system. The model with activities related to every phase presented in
“Fig.1”. Negotiation process model is formed by goal driven negotiation and requirements assigned to
agents. Based on view point, agents are able to improve their behaviors over time. In that way, they
may get better with experiences at selecting and achieving goals by taking correct actions. So agents
can take proactive and reactive negotiation actions.
Now a day’s, because in e-market there are infinite participants, exponentially growing amount of
information available, information transparency, information overloading, different negotiation
mechanism price wars between buyers and between sellers and complexity of modern business trade
, therefore intelligent agent based automated negotiation systems are hopeful technologies that
play an important role. Intelligent agents systems can adopt various mechanisms (e.g. bidding,
auction, bargaining, and arbitration), information discovery and collection, negotiator selection,
proposal generation and evaluation, play of advisor and provide effective suggestion, fully
understand of owner requirements and preferences, coordinate interdependent relationships between
various negotiations, build comprehensive user models and finally the systems can make trust between
both users. In addition, intelligent agents allow negotiator to play both roles of buyer and seller
at the same time. Our proposed design has considered the notations and results of this research show
that proposed intelligent agent architecture would reduce negotiation time and provide rapid response
for their owners. Next step, we explain the particular design of intelligent agent’s architecture.
In order to explain the architecture, first we have to illustrate types of agents employed in the
architecture and then we show buyer and seller agent architecture.

Figure 1. Negotiation process model and assigns different activities to them

Figure 2. Buyer Agent Architecture based on Intelligent Agents

Figure 3.Seller Agent Architecture based on Intelligent Agents

In purposed model, Owner profile agent is to present owner goals, and aid the negotiator deciding on
goals and strategies. In addition, agents of this type would be able to adapt to the changes based on
owner behavior in the process of negotiations. Searcher Agent is an agent that searches potential
buyers or sellers that are in other distributed environments and performs the role of managing,
querying, or collating information from many distributed sources. A simple rule matching mechanism is
developed to extract relevant negotiator information from the search results. This agent also performs
post processing for the retrieved items and gives a list of qualified buyers or sellers with the
offer. Information mediator agent would envelope in actively searching, fetching, filtering, and
delivering information relevant to the issues from market knowledge base. Also this agent type is
able to identify the objectives, preferences and strategies of the opponent. Recommender agent is
able to generate a set of likely offers to be considered for submission to the opponent. The proposed
of advisor agent is to evaluate the offers received from the opponent and provide a feedback on the
defect and, possibly benefits of these offers. Negotiator agent is responsible for negotiating with
potential buyers or sellers, with respect to the preferences that have been collected from a group of
participants. Here, the goal is to bargaining with candidate sellers or buyers for the best offer
that satisfies the most demands and preferences of group members. In addition, this agent may be
capable of conducting negotiations by itself in a semi-autonomous or fully autonomous mode.
Applicability of full automation depends on the degree of certainty in objectives, preferences, and
tactics of the negotiator therefore the agent is an agent that optimizes the buyer or seller utility
based upon the requirements from owners’ requirements and constraints.Buyer or seller mediator agent
is an agent that delivers the status messages of active services between negotiators agents, and
between peer agents. In addition, this agent can play a role of an expert agent and in a sense; the
agent is an intelligent administrator agent.

Computer Network Routing with a Fuzzy Neural Network

As more individuals transmit data through a computer network, the quality of service received by the users
begins to degrade. A major aspect of computer networks that is vital to quality of service is data routing.
A more effective method for routing data through a computer network can assist with the new problems being
encountered with today’s growing networks. Effective routing algorithms use various techniques to determine
the most appropriate route for transmitting data. Determining the best route through a wide area network
(WAN), requires the routing algorithm to obtain information concerning all of the nodes, links, and devices
present on the network. The most relevant routing information involves various measures that are often
obtained in an imprecise or inaccurate manner, thus suggesting that fuzzy reasoning is a natural method to
employ in an improved routing scheme. The neural network is deemed as a suitable accompaniment because it
maintains the ability to learn in dynamic situations.

Once the neural network is initially designed, any alterations in the computer routing environment can
easily be learned by this adaptive artificial intelligence method. The capability to learn and adapt is
essential in today’s rapidly growing and changing computer networks. These techniques, fuzzy reasoning
and neural networks, when combined together provide a very effective routing algorithm for computer
networks. Computer simulation is employed to prove the new fuzzy routing algorithm outperforms the
Shortest Path First (SPF) algorithm in most computer network situations. The benefits increase as the
computer network migrates from a stable network to a more variable one. The advantages of applying this
fuzzy routing algorithm are apparent when considering the dynamic nature of modern computer networks.

Applying artificial intelligence to specific areas of network management allows the network engineer
to dedicate additional time and effort to the more specialized and intricate details of the system.
Many forms of artificial intelligence have previously been introduced to network management; however,
it appears that one of the more applicable areas, fuzzy reasoning, has been somewhat overlooked.
Computer network managers are often challenged with decision-making based on vague or partial
information. Similarly, computer networks frequently perform operational adjustments based on this
same vague or partial information. The imprecise nature of this information can lead to difficulties
and inaccuracies when automating network management using currently applied artificial intelligence
techniques. Fuzzy reasoning will allow this type of imprecise information to be dealt with in a
precise and well-defined manner, providing a more flawless method of automating the network
management decision making process.

The objective of this research is to explore the use of fuzzy reasoning in one area of network
management, namely the routing aspect of configuration management. A more effective method for
routing data through a computer network needs to be discovered to assist with the new problems
being encountered on today’s networks. Although traffic management is only one aspect of
configuration management, at this time it is one of the most visible networking issues. This
becomes apparent as consideration is given to the increasing number of network users and the
tremendous growth driven by Internet-based multimedia applications. Because of the number of
users and the distances between WAN users, efficient routing is more critical in wide area
networks than in LANs (also, many LAN architectures such as token ring do not allow any
flexibility in the nature of message passing). In order to determine the best route over the
WAN, it is necessary to obtain information concerning all of the nodes, links, and LANs present
in the wide area network. The most relevant routing information involves various measures
regarding each link. These measures include the distance a message will travel, bandwidth
available for transmitting that message (maximum signal frequency), packet size used to segment
the message (size of the data group being sent), and the likelihood of a link failure. These
are often measured in an imprecise or inaccurate manner, thus suggesting that fuzzy reasoning
is a natural method to employ in an improved routing scheme.

Utilizing fuzzy reasoning should assist in expressing these imprecise network measures; however, there
still remains the massive growth issue concerning traffic levels. Most routing algorithms currently
being implemented as a means of transmitting data from a source node to a destination node cannot
effectively handle this large traffic growth. Most network routing methods are designed to be efficient
for a current network situation; therefore, when the network deviates from the original situation, the
methods begin to lose efficiency. This suggests that an effective routing method should also be capable
of learning how to successfully adapt to network growth. Neural networks are extremely capable of
adapting to system changes, and thus will be applied as a second artificial intelligence technique to
the proposed routing method in this research. The proposed routing approach incorporates fuzzy reasoning
in order to prepare a more accurate assessment of the network’s traffic conditions, and hence provide a
faster, more reliable, or more efficient route for data exchange. Neural networks will be incorporated
into the routing method as a means for the routing method to adapt and learn how to successfully handle
network traffic growth. The combination of these two tools is expected to produce a more effective
routing method than is currently available.

In order to achieve the primary objective of more efficient routing, several minor objectives also need
to be accomplished. A method of data collection is needed throughout the different phases of the study.
Data collection will be accomplished through the use of simulation methods; therefore, a simulation model
must be accurately designed before proceeding with experimenting or analysis. Additional requirements
include building and training the neural network and defining the fuzzy system. The objective of this
research is to demonstrate the effective applicability of fuzzy reasoning to only one area of network
management, traffic routing.

 

Android Science, Toward a new cross-interdisciplinary framework

In the development of humanoids, both the appearance and behavior of the robots are significant issues.
However, designing the robot’s appearance, especially to give it a humanoid one, was always a role of the
industrial designer. To tackle the problem of appearance and behavior, two approaches are necessary: one
from robotics and the other from cognitive science. The approach from robotics tries to build very
humanlike robots based on knowledge from cognitive science. The approach from cognitive science uses the
robot for verifying hypotheses for understanding humans. We call this cross- interdisciplinary framework
android science. This conceptual paper introduces the developed androids and states the key issues in
android science.

Intelligence as subjective phenomena

How can we define intelligence ? This fundamental question motivates researchers in artificial intelligence
and robotics. Previous works in artificial intelligence considered functions of memory and prediction to
realize the intelligence of artificial systems. After the big wave of artificial intelligence in the 1980’s
and 1990’s, researchers focused on the importance of embodiment and started to use robots. The behavior-
based system proposed by Brooks was a trigger for this new wave. This means the main focus on artificial
intelligence and robotics has changed from an internal mechanism to interaction with the environment.
On the other hand, there are also two ideas in cognitive science. One is to focus on the internal
mechanism for understanding human intelligent behaviors, while the other focuses on the interactions
among people. This  approaches is studied in the framework of distributed cognition. The idea of
distributed cognition has similar aspects to the behavior-based system. The common concept is to
understand intelligence through human-human or human-robot interactions. This is also follows the ideas
of the behavior-based systems and distributed cognition. Because intelligence is a subjective phenomena,
it is therefore important to implement rich interactive behaviors with the robot. The author believes the
development of rich interactions among robots will provide hints of principles of communication systems,
with the design methodology of intelligent robots then being derived from those principles.

Constructive approach in robotics

First we have the question of how to develop the robots. There are explicit evaluation criteria for robot
navigation such as speed, precision, etc. On the other hand, our purpose is also to develop interactive
robots. If we have enough knowledge of humans, we may have explicit evaluation criteria. However this
knowledge is not sufficient to provide a top-down design; instead the potential approach is rather
bottom-up. By utilizing available sensors and actuators, we can design the behaviors of a robot and then
decide the execution rules among those behaviors. While doing this developing, we also evaluate the
robot’s performance and modify the behaviors and execution rules. This bottom-up approach is called the
constructive approach .In the constructive approach, interactions between a robot and a human are often
evaluated and analyzed through discussions with cognitive scientists and psychologists, with the robot
then being improved by the knowledge obtained through the discussions.

Appearance and behavior

In the evaluation, the performance measures are subjective impression of human subjects who interact with
the robot and their unconscious reactions, such as synchronized human behaviors in the interactions and eye
movements. Obviously, both the appearance and behavior of the robots are important factors in this
evaluation. There are many technical reports that compare robots with different behaviors. However nobody
has focused on appearance in the previous robotics. There many empirical discussions on very simplified
static robots, say dolls. Designing the robot’s appearance, especially to give it a humanoid one, was always
a role of the industrial designer. However we consider this to be a serious problem for developing and
evaluating interactive robots. Appearance and behavior are tightly coupled with both each other and these
problems, as the results of evaluation change with appearance. We developed several
humanoids for communicating with people, as shown in Figure 1. We empirically know the effect of appearance
is as significant as behaviors in communication. Human brain functions that recognize people support our
empirical knowledge.

Figure 1: From humanoids to androids. The first robot (the left end) is Robovie II developed by ATR
Intelligent Robotics and Communications Laboratories. The second is Wakamaru developed by Mitsubishi
Heavy Industry Co. Ltd. The third is a child android, while the fourth is the master of the child android.

Android Science

To tackle the problem of appearance and behavior, two approaches are necessary: one from robotics and the
other from cognitive science. The approach from robotics tries to build very humanlike robots based on
knowledge from cognitive science. The approach from cognitive science uses the robot for verifying hypotheses
for understanding humans. We call this cross-interdisciplinary framework android science.

Figure 2: The framework of android science

Previous robotics research also used knowledge of cognitive science while research in cognitive science
utilized robots. However the contribution from robotics to cognitive science was not enough as robot-like
robots were not sufficient as tools of cognitive science, because appearance and behavior cannot be separately
handled. We expect this problem to be solved by using an android that has an identical appearance to a human.
Robotics research utilizing hints from cognitive science also has a similar problem as it is difficult to
clearly recognize whether the hints are given for just robot behaviors isolated from their appearance or for
robots that have both the appearance and the behavior. In the framework of android science, androids enable us
to directly exchange knowledge between the development of androids in engineering and the understanding of
humans in cognitive science.

Search Space Optimization

The optimizer considers each algebraic operation independently since the query decomposition step has
already taken global reorganization decisions. Optimization of all operations but the n-way Select
Project Join (SPJ) is quit straightforward. It consists of choosing the algorithm and the home of
operation. The crucial issue in terms of the search strategy is the join ordering problem, which
is NP-hard on the number of relations.

The search space, or solution space, is the set of all QEPs that compute the same result. A point
in the solution space is one particular plan, i. e. solution for the problem. A solution is
described by the query tree for executing the join expression. Every point of the search space
has a cost associated with it; a cost function maps query trees to their respective costs. The
query tree itself is a binary tree that consists of base relations as its leaves and joins
operations as its inner nodes; edges denote the flow of data that takes place from the leaves
of the tree to the root. As the join operation is commutative and associative, the number of
possible query trees increases quickly with increasing the number of relations involved in the
query. Thus, we reduce the goal of the query optimizer to find the best join order, together
with the best join method for each join. For a complex query, involving many relations and
many operators, the number of equivalent operator trees can be very high. Investigating a large
search space may make optimization time prohibitive, sometime much more expensive than the
execution time. Therefore, query optimizers typically restrict the size of the search space
they consider. The first restriction is to use heuristics. Another important restriction is the
shape of the join tree. The following sections discuss the characteristics of the most interesting
kinds of search spaces depending on the shape of the join tree they include.

Left-Deep and Right-Deep Trees

The search space restricted to only left-deep trees consists of all query trees where the inner
relation of each join is a base relation as in Figure 2-a. For a fixed number of base relations,
left-deep tree does not leave any degree of freedom concerning the shape of the tree, but there
are n! ways to allocate n base relations to the tree leaves.

Figure 2. Different query trees

In most sequential optimizers like the optimizer of IBM System R, the search space is restricted
to left-deep trees. The reason for this heuristic restriction is that the space including all trees
is much larger, while an optimal or nearly optimal plan can often be found in the much smaller
space of left-deep trees. When join algorithms are not symmetric, which is the case for hash-join,
it is useful to distinguish between left-deep and right-deep trees, see Figure 2-b. Hash-based join
algorithm have been shown to be the most efficient for equi-joins and particularly interesting in a
parallel environment because they naturally induce intra-operation parallelism. Hash-join usually
consists of two consecutive phases: Build and probe. In the build phase, a hash table is constructed
on the join attribute of the smallest relation. In the probe phase, the largest relation is
sequentially scanned and the hash table is consulted for each of its tuples.

Shortest Path Algorithm for Multicast Routing in Multimedia Applications

A new heuristic algorithm is proposed for constructing multicast tree for multimedia and real-time applications.
The tree is used to concurrently transmit packets from source to multiple destinations such that exactly one
copy of any packet traverses the links of the multicast tree. Since multimedia applications require some
Quality of Service, QoS, a multicast tree is needed to satisfy two main goals, the minimum path cost
from source to each destination (Shortest Path Tree) and a certain end-to-end delay constraint from source to
each destination. This problem is known to be NP-Complete. The proposed heuristic algorithm solves this
problem in polynomial time and gives near optimal tree. We first mention some related work in this area then
we formalize the problem and introduce the new algorithm with its pseudo code and the proof of its complexity
and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms
are examined and compared with the proposed algorithm via simulation.

Handling group communication is a key requirement for numerous applications that have one source sends
the same information concurrently to multiple destinations. Multicast routing refers to the construction
of a tree rooted at the source and spanning all destinations. Generally, there are two types of such a tree,
the Steiner tree and the shortest path tree. Steiner tree or group-shared tree tends to minimize the total
cost of the resulting tree, this is an NP-Complete problem. Shortest path tree or source-based trees tends
to minimize the cost of each path from source to any destination, this can be achieved in polynomial time
by using one of the two famous algorithms of Bellman and Dijkstra and pruning the undesired links. Recently,
with the rapid evolution of multimedia and real-time applications like audio/video conferencing, interactive
distributed games and real-time remote control system, certain QoS need to be guaranteed in the resulted
tree. One such QoS, and the most important one is the end-to-end delay between source and each destination,
where the information must be sent within a certain delay constraint D. By adding this constraint to the
original problem of multicast routing, the problem is reformulated and the multicast tree should be either
delay constrained Steiner tree, or delay-constrained shortest path tree. Delay constrained Steiner tree
is an NP-Complete problem, several heuristics are introduced for this problem each trying to get near
optimal tree cost, without regarding to the cost of each individual path for each destination. Delay
constrained shortest path tree is also an NP-Complete problem. An optimal algorithm for this problem
is presented, but its execution time is exponential and used only for comparison with other algorithms.
Heuristic for this problem is presented, which tries to get a near optimal tree from the point of
view of each destination without regarding the total cost of the tree. An exhaustive comparison between
the previous heuristics for the two problems can be found. We investigate the problem of delay
constrained shortest path tree since it is appropriate in some applications like Video on Demand (VoD),
where the multicast group has a frequent change, and every user wants to get his information in the lowest
possible cost for him without regarding the total cost of the routing tree. Also shortest path tree always
gives average cost per destination less than Steiner tree. We present a new heuristic algorithm that finds
the required tree in polynomial time.

FPGA Based Dijkstra’s Shortest Path Algorithm

A parameterizable version of Dijkstra’s shortest path algorithm was designed in VHDL with Synopsys’ FPGA
Express design software version 3.4. The design was targeted for Altera’s FLEX10K device family with the
Quartus design software. The parameterizable features of Dijkstra’s shortest path algorithm were compiled
into a separate VHDL package which was included in the main design file. This way the design of other
versions of Dijsktra’s algorithm with different accuracy and for networks of different sizes is made
easier, since all the changes are made only in the VHDL package.

Fig. 1. The top-level block diagram of the FPGA-based Dijkstra’s shortest path algorithm. The ROM block
contains the network description and the RAM block contains the temporary results of shortest path
computation. The comparator bank selects the smallest distance from the prefetched edge lengths.

The block diagram of the FPGA-based Dijkstra’s shortest path algorithm is presented in Fig. 1. The
network structure is presented in the internal ROM block of the logic device. In the block diagram
of Fig. 1, there are six address lines. This is sufficient to represent all node-to-node links of
networks of size upto eight nodes, if the network is represented as an adjacency matrix. The
internal RAM blocks of the logic device represent the known status of nodes, the distance to this
node and the previous node. There are separate address and data lines for the ROM and RAM blocks,
which allows the parallel transfer of information to/from the memory blocks. To speed up the
computations for finding the closest node from the set of unknown nodes, all node-to-node links
whose other pair is the last known node are prefetched from ROM. Then the next known node is
computed by the parallel comparator bank.

As an example, the compiled version of Dijsktra’s algorithm for networks of maximum sixe eight nodes
fitted into an EPF10K20TC144-3 device, which has 1152 logic elements (LEs) corresponding to
approximately 20000 available gates. The design required 72 per cent of all LEs and 5 per cent of
available memory bits. Logic element requirements increase linearly, since the size of the comparator
bank grows linearly. On the other hand, memory requirements increase quadratically,since the network
description of a network of size N nodes requires NxN memory locations. If the network description
requires an external memory chip, all that is needed is to add an external data and address bus and
to change the memory handling functions to handle external memory instead of internal memory.

To compare the performance of an FPGA-based Dijsktra’s algorithm with a microprocessor-based version,
an identical algorithm was coded in C and compiled with gcc in Linux Redhat 6.2. The same network
descriptions were then tried in both the FPGA-based and software-based versions of the same algorithm.
The speedup factor in favor of the FPGA-based version depended on the number of network nodes. As
network sizes grew, the average execution time of the FPGA-based version grew only linearly, whereas
the average execution time of the microprocessor-based version displayed quadratic growth
(in Table 2). This can be attributed to the more effective FPGA-based execution in Dijkstra’s
algorithm, since multiple comparators are used in parallel.

Table 2. FPGA resources required by the implementation of Dijkstra’s shortest path algorithm and a
comparison between the execution times of FPGA-based and microprocessor-based versions of the same algorithm.

Overcoming Barriers to Early Detection with Pervasive Computing

Embedded assessment leverages the capabilities of pervasive computing to advance early detection
of health conditions. In this approach, technologies embedded in the home setting are used to
establish personalized baselines against which later indices of health status can be compared.
Our ethnographic and concept feedback studies suggest that adoption of such health technologies
among end users will be increased if monitoring is woven into preventive and compensatory health
applications, such that the integrated system provides value beyond assessment. We review health
technology advances in the three areas of monitoring, compensation, and prevention. We then define
embedded assessment in terms of these three components. The validation of pervasive computing
systems for early detection involves unique challenges due to conflicts between the exploratory
nature of these systems and the validation criteria of medical research audiences. We discuss an
approach for demonstrating value that incorporates ethnographic observation and new ubiquitous
computing tools for behavioral observation in naturalistic settings such as the home.

Leveraging synergies in these three areas holds promise for advancing detection of disease states.
We believe this highly integrated approach will greatly increase adoption of home health
technologies among end users and ease the transition of embedded health assessment prototypes from
computing laboratories into medical research and practice. We derive our observations from a series
of exploratory and qualitative studies on ubiquitous computing for health and wellbeing.
These studies, highlighted barriers to early detection in the clinical setting, concerns about home
assessment technologies among end users, and values of target user groups related to prevention and
detection. Observations from the studies are used to identify challenges that must be overcome by
pervasive computing developers if ubiquitous computing systems are to gain wide acceptance for early
detection of health conditions.

The motivation driving research on pervasive home monitoring is that clinical diagnostic practices
frequently fail to detect health problems in their early stages. Often, clinical testing is first
conducted after the onset of a health problem when there is no data about an individual’s previous
level of functioning. Subsequent clinical assessments are conducted periodically, often with no data
other than self-report about functioning in between clinical visits. Self-report data on mundane or
repetitive health-related behaviors has been repeatedly demonstrated as unreliable. Clinical
diagnostics are also limited in ecological validity, not accounting for functioning in the home and
other daily environments. Another barrier to early detection is that agebased norms used to detect
impairment may fail to capture significant decline among people whose premorbid functioning was far
above average. Cultural differences have also been repeatedly shown to influence performance on
standardized tests. Although early detection can cut costs in the long term, most practitioners are
more accustomed to dealing with severe, late stage health issues than subclinical patterns that may
or may not be markers for more serious problems. In our participatory design interviews, clinicians
voiced concerns about false positives causing unwarranted patient concerns and additional demands
on their time. Compounding the clinical barriers to early detection listed above are psychological
and behavioral patterns among individuals contending with the possibility of illness. Our interviews
highlighted denial, perceptual biases regarding variability of health states, over-confidence in
recall and insight, preference for preventive and compensatory directives over pure assessment
results, and a disinclination towards time consuming self-monitoring as barriers to early detection.
Our ethnographic studies of households coping with cognitive decline revealed a tension between a
desire for forecasting of what illness might lie ahead and a counter current of denial. Almost all
caregivers and patients wished that they had received an earlier diagnosis to guide treatment and
lifestyle choices, but they also acknowledged that they had overlooked blatant warning signs until
the occurrence of a catastrophic incident (e.g. a car accident). This lag between awareness and
actual decline caused them to miss out on the critical window for initiation of treatments and
planning that could have had a major impact on independence and quality of life. Ethnography and
concept feedback participants attributed this denial in part to a fear of being diagnosed with a
disease for which there is no cure. They also worried about the effect of this data on insurers and
other outside parties. Participants in the three cohorts included in our studies (boomers, healthy
older adults, and older adults coping with illness themselves or in a spouse) were much more
interested in, and less conflicted about, preventive and compensatory directives than pure assessment.

Perceptual biases also appear to impede traditional assessment and selfmonitoring. Ethnography
participants reported consistently overestimating functioning before a catastrophic event and appeared,
during the interview, to consistently underestimate functioning following detection of cognitive
impairment Additionally, we observed probable over-confidence among healthy adults in their ability to
recall behaviors and analyze their relationship to both environmental factors and wellbeing. This
confidence in recall and insight seemed exaggerated given findings that recall of frequent events is
generally poor. As a result of these health perceptions, many of those interviewed felt that the time
and discipline required for journaling (e.g. of eating, sleeping, mood, etc.) outweighed the benefits.
Additionally, they expressed wariness of confronting or being reprimanded about what is already obvious
to them. They would prefer to lead investigations and develop strategies for improving their lives.
Pervasive computing systems may enable this type of integrated, contextualized inquiry if they can also
overcome the clinical and individual barriers that might otherwise impede adoption of the new technologies.

Changing Java’s Semantics for Handling Null Pointer Exceptions

We envision a world where no exceptions are raised; instead, language semantics are changed
so that operations are total functions. Either an operation executes normally or tailored
recovery code is applied where exceptions would have been raised. As an initial step and
evaluation of this idea, we propose to transform programs so that null pointer dereferences
are handled automatically without a large runtime overhead. We increase robustness by replacing
code that raises null pointer exceptions with error handling code, allowing the program to
continue execution. Our technique first finds potential null pointer dereferences and then
automatically transforms programs to insert null checks and error-handling code. These
transformations are guided by composable, context sensitive recovery policies. Error-handling
code may,  for example, create default objects of the appropriate types, or restore data
structure invariants. If no null pointers would be dereferenced, the transformed program behaves
just as the original. We applied our transformation in experiments involving multiple benchmarks,
the Java Standard Library, and externally reported null pointer exceptions. Our technique is
able to handle the reported exceptions and allow the programs to continue to do useful work, with
an average execution time overhead of less than 1% and an average byte code space overhead of 22%.

Null pointer exception management is a logical starting point for changing Java’s semantics for
exception handling, because of the simplicity and regularity and null pointer exceptions. Null pointer
exceptions, while conceptually simple, remain prevalent in practice. Null pointer dereferences are not
only frequent, but also catastrophic and are “a very serious threat to the safety of programs”. Many
classes of null pointer exceptions can be found automatically by static analyses, and they have been
reported as one of the top ten causes of common web application security risks. Addressing such risks
with fault-tolerance techniques is a promising avenue. For example, techniques that mask memory errors
have successfully eliminated security vulnerabilities in servers.

Though Java already provides an infrastructure for exceptions, the current state of the language is
only a partial solution. Java makes a clear distinction between checked and unchecked exceptions.
The former are included in method type signatures and must be addressed by the programmer; the latter
may be ignored without compiler complaint. Unchecked exceptions should also be documented and properly
handled by the language, in a systematic and universal manner. Java treats null pointer exceptions as
unchecked by default, while APPEND’s approach to null pointer prevention is similar to the way Java
treats checked exceptions: an undesirable situation or behavior is identified by the programmer, and
some error handling code is generated. One reason null pointer exceptions are not treated as checked by
Java is that there are many potential sources of null pointer dereferences and different recovery
situations would have to be embedded in multiple local catch blocks explicitly: a time-consuming and
error-prone task. First, it would be difficult to identify, for each null pointer exception that
propagated upwards, what kind of recovery code could be applied, without knowing context information.
Secondly, Java’s current exception handling mechanisms also open up the possibility of a breakdown of
encapsulation and information hiding, as implementation details from lower levels of scope are raised
to the top level of the program. A solution to null pointer exceptions that is able to prevent or mask
them in a way that is both reasonable and accessible to the programmer has yet to be implemented.

APPEND is a program transformation that changes Java’s null pointer exception handling by automatically
inserting null checks and error-handling code. No program annotations are required, and developers need
not wade through defect reports. Programs are modified according to composable recovery policies.
Recovery policies are executed at compile-time and, depending on the context, recovery code is inserted
that is then executed at run-time if the null checks fail. Recovery policies are conceptually related to
theorem prover tactics and tacticals or to certain classes of aspect-oriented programming. If no null
values are dereferenced at run-time, the transformed program behaves just as the original program. If the
original program would dereference a null value, the transformed program instead executes the policy
dictated error-handling code, such as creating a default value on the fly or not calculating that
expression. Previous research has suggested that programs might successfully continue even with discarded
instructions; we present and measure a concrete, low-level, annotation-free version of such a system, and
extend it to allow for user-specified actions.

The idea behind this approach is that null pointer dereferences are undesirable, especially in circumstances
where they are involved in non-critical computations where the program is forced to crash if one is
encountered. If we had a way of preventing the program from ceasing execution, while logging and performing
some sort of recovery code instead of raising an exception, we hypothesize that there are many applications
where this behavior would be preferred. Therefore, it becomes possible to check every pointer dereference
in the code for nullness, and to include recovery code for every such instance. We argue that this is a
practical and preferable way to deal with null pointer exceptions in Java.Because we intend to check every
pointer dereference for nullness, we could have chosen to take advantage of the existing null checking of
the Java virtual machine. Given the low overhead of our tool, we chose to work on the application level
instead, to remain portable and not have to rely on a single modified JVM instantiation.The transformation
can be implemented directly atop existing program transformation frameworks and dovetails easily with
standard development processes.

Write Optimized Tree Indexing

Due to the poor random write performance of flash SSDs (Solid State Drives), write optimized tree indexes have been proposed to improve the update performance. BFTL was proposed to balance the inferior random write performance and fast random read performance for flash memory based sensor nodes and embedded systems. It allows the index entries in one logical B-tree node to span over multiple physical pages, and maintains an in-memory table to map each B-tree node to multiple physical pages. Newly inserted entries are packed and then written together to some new blocks. The table entries of corresponding B-tree nodes are updated, thus reducing the number of random writes. However, BFTL entails a high search cost since it accesses multiple disk pages to search a single tree node. Furthermore, even though the in-memory mapping table is compact, the memory consumption is still high. FlashDB was proposed to implement a self-tuning scheme between standard B+-tree and BFTL, depending on the workloads and the types of flash devices. Since our proposed index mostly outperforms both B+-tree and BFTL under various workloads on different flash SSDs, we do not compare our index with this self-tuning index in this paper. More recently, LA-tree was proposed for flash memory devices by adding adaptive buffers between tree nodes. LA-tree focuses on raw, small-capacity and byte addressable flash memory devices, such as sensor nodes, whereas our work is targeted for off theshelf large flash SSDs, which provide only a block-based access interface. Different target devices of these two indexes result in their differences in design.

On the hard disk, many disk-based indexes optimized for write operations have also been proposed.
Graefe proposed a write-optimized B-tree by applying the idea of the log file system to the B-tree
index. Y-tree supports high volume insertions for data warehouses following the idea of buffer tree.
The logarithmic structures have been widely applied to optimize the write performance. O’Neil et al.
proposed LSM-tree and its variant LHAM for multi-version databases. Jagadish et al. used a similar
idea to design a stepped tree index and the hash index for data warehouses. Our FD-tree follows the
idea of logarithmic method. The major difference is that we propose a novel method based on the
fractional cascading technique to improve the search performance on the logarithmic structure.