bluuebunny/crossref_metadata_2025 huggingface dataset:
Comparing traffic classifiers
Authors: Salgarelli Luca , Gringoli Francesco , Karagiannis Thomas
Published: September 2007

Many reputable research groups have published several interesting papers on traffic classification, proposing mechanisms of different nature. However, it is our opinion that this community should now find an objective and scientific way of comparing results coming out of different groups. We see at least two hurdles before this can happen. A major issue is that we need to find ways to share full-payload data sets, or, if that does not prove to be feasible, at least anonymized traces with complete application layer meta-data. A relatively minor issue refers to finding an agreement on which metric should be used to evaluate the performance of the classifiers. In this note we argue that these are two important issues that the community should address, and sketch a few solutions to foster the discussion on these topics.
Enhanced wireless mesh networking for ns-2 simulator
Authors: Mhatre Vivek
Published: September 2007

The ns-2 simulator has limited support for simulating 802.11 based wireless mesh networks. We have added the following new features at the MAC and PHY layer of ns-2: (i) cumulative interference in SINR (Signal to Interference and Noise Ratio) computation, (ii) an accurate and combined shadow-fading module, (iii) multi-SINR and multi-rate link support, (iv) auto rate fallback (ARF) for rate adaptation, and (v) a framework for link probing and link quality estimation as required by most mesh routing protocols. We have made these modules publicly available. In this paper, we present an overview of these new features.
Author feedback experiment at PAM 2007
Authors: Papagiannaki Konstantina
Published: September 2007

This editorial article is put together to disseminate the experience gained through the author feedback experiment, performed at the 2007 Passive and Active Measurement (PAM) conference.
You must be joking
Authors: Faloutsos Michalis , Banerjee Anirban , Rejaie Reza
Published: September 2007

We did it! A few CCR issues back, this column argued in favor of an all open review. At the time, most people thought that it was a joke. Quite frankly, we meant it as a joke. It is a crazy world we live in. No, seriously, it was not so much of a joke, as a wild attempt to think outside the box. Or else, desperate times call for desperate measures. Something like that. Apparently, we were so desperate that we actually tried it. And it worked. Beautifully. But then again, we may be biased.

"To say it was easy would be a lie." R. Rejaie and M. Faloutsos, early 21st century.
Future internet research and experimentation
Authors: Gavras Anastasius , Karila Arto , Fdida Serge , May Martin , Potts Martin
Published: September 2007

The research community worldwide has increasingly drawn its attention to the weaknesses of the current Internet. Many proposals are addressing the perceived problems, ranging from new enhanced protocols to fix specific problems up to the most radical proposal to redesign and deploy a fully new Internet. Most of the problems in the current Internet are rooted in the tremendous pace of increase of its use. As a consequence there was little time to address the deficiencies of the Internet from an architectural point of view.

Within FP7, the European Commission has facilitated the creation of European expert groups around the theme FIRE "Future Internet Research and Experimentation". FIRE has two related dimensions: on one hand, promoting experimentally-driven long-term, visionary research on new paradigms and networking concepts and architectures for the future Internet; on the other hand, building a large-scale experimentation facility supporting both medium- and long-term research on networks and services by gradually federating existing and new testbeds for emerging or future Internet technologies. By addressing future challenges for the Internet such as mobility, scalability, security and privacy, this new experimentally-driven approach is challenging the mainstream perceptions for future Internet development. This new initiative is intended to complement the more industrially-driven approaches which are addressed under the FP7 Objective "The Network of the Future" within the FP7-ICT Workprogramme 2007-08. FIRE is focused on exploring new and radically better technological solutions for the future Internet, while preserving the "good" aspects of the current Internet, in terms of openness, freedom of expression and ubiquitous access. The FIRE activities are being launched in the 2nd ICT call, which closes in October 2007, under the FP7-ICT Objective 1.6 "New Paradigms and Experimental Facilities" (budget ε40m). Projects are envisaged to start in early 2008.
An undergraduate experimental UAV payload project to teach problem solving and project lifecycle skills
Authors: Marchant Anne , Marchant William
Published: September 2007

The ability to do advanced research can be nurtured through the development of problem solving skills at the undergraduate level. As with any information technology project, IT research is most often done in teams. This paper describes an undergraduate team-based project to build and integrate the payload for an uninhabited aerial vehicle (UAV). The class mission was to survey a mock disaster area and to acquire photos, video, and GPS tracking data to aid in recovery efforts. Freeware tools and a Linux processor were used to keep costs low. The UAV platform was a radio controlled helicopter. Teams were tasked with quality control, documentation, and public relations to simulate a real IT development project. A "wiki" type website was used to aid in project management and documentation. A project of this nature can be incorporated into any project management class to teach project lifecycle principles and should serve to prepare students for more advanced research projects.
BI-hyperdoctrines, higher-order separation logic, and abstraction
Authors: Biering Bodil , Birkedal Lars , Torp-Smith Noah
Published: September 2007

We present a precise correspondence between separation logic and a simple notion of
predicate
BI, extending the earlier correspondence given between part of separation logic and
propositional
BI. Moreover, we introduce the notion of a BI hyperdoctrine, show that it soundly models classical and intuitionistic first- and higher-order predicate BI, and use it to show that we may easily extend separation logic to
higher-order
. We also demonstrate that this extension is important for program proving, since it provides sound reasoning principles for data abstraction in the presence of aliasing.
A new foundation for control dependence and slicing for modern program structures
Authors: Ranganath Venkatesh Prasad , Amtoft Torben , Banerjee Anindya , Hatcliff John , Dwyer Matthew B.
Published: September 2007

The notion of control dependence underlies many program analysis and transformation techniques. Despite being widely used, existing definitions and approaches to calculating control dependence are difficult to apply directly to modern program structures because these make substantial use of exception processing and increasingly support reactive systems designed to run indefinitely.

This article revisits foundational issues surrounding control dependence, and develops definitions and algorithms for computing several variations of control dependence that can be directly applied to modern program structures. To provide a foundation for slicing reactive systems, the article proposes a notion of slicing correctness based on weak bisimulation, and proves that some of these new definitions of control dependence generate slices that conform to this notion of correctness. This new framework of control dependence definitions, with corresponding correctness results, is even able to support programs with irreducible control flow graphs. Finally, a variety of properties show that the new definitions conservatively extend classic definitions. These new definitions and algorithms form the basis of the Indus Java slicer, a publicly available program slicer that has been implemented for full Java.
Analysis of modular arithmetic
Authors: Müller-Olm Markus , Seidl Helmut
Published: September 2007

We consider integer arithmetic modulo a power of 2 as provided
by mainstream programming languages like Java or standard
implementations of C. The difficulty here is that, for
w
> 1, the ring
Z

m

of integers modulo
m
= 2

w

has zero divisors and thus cannot
be embedded into a field. Not withstanding that, we present intra-
and interprocedural algorithms for inferring for every program
point
u
affine relations between program variables valid at
u
. If conditional branching is replaced with
nondeterministic branching, our algorithms are not only sound but
also
complete
in that they detect
all
valid affine
relations in a natural class of programs. Moreover, they run in
time linear in the program size and polynomial in the number of
program variables and can be implemented by using the same modular
integer arithmetic as the target language to be analyzed. We also
indicate how our analysis can be extended to deal with equality
guards, even in an interprocedural setting.
24-hour knowledge factory
Authors: Gupta Amar , Seshasai Satwik
Published: September 2007

Several of the outsourcing endeavors of today will gradually converge to a hybrid outsourcing model that will involve a team spread across three or more strategically-located centers interconnected by Internet technology. White-collar professionals in the US, Australia, and Poland, for example, could each work on a standard 9--5 basis, transfer the activity to a colleague in the next center, thereby enabling work to be performed on a round-the-clock basis. The effective use of sequential workers in such a 24-hour knowledge factory requires that professional tasks be broken down to the level where individuals can work on them with minimal interaction with their peers, and where new approaches can be employed to reduce the effort involved in transitioning from one employee to the next. This article describes an Internet-based prototype system that uses a Web-based interactive approach, coupled with a unique data model, to optimize collection and storage of design rationale and history from stakeholders and workers. The idea of multiple individuals acting as one “composite persona” is explored in the context of facilitating tasks and knowledge to be shared across the Internet in a seamless manner. The article also describes related activities in the commercial arena.
Impact of Internet-based distributed monitoring systems on offshore sourcing of services
Authors: Aron Ravi , Jayanty Siddarth , Pathak Praveen
Published: September 2007

The use of Internet-based distributed monitoring systems has allowed firms to source services globally that were hitherto thought of as being too risky or complex to execute offshore. These systems enable buyers of such services (clients) to monitor the execution of processes in real-time and exert a degree of managerial control over information workers of another firm located in a distant region. Our research shows that process codifiability plays a key role in determining output quality. Further, we show that the efforts made by the client and the provider in monitoring work via Internet-based monitoring mechanisms have a significant impact on output quality. Finally, we show that these monitoring mechanisms enable clients and providers of services to focus on those processes that are best managed by each entity. This scheme of optimal allocation of monitoring effort is termed by us as the efficient monitoring frontier.
Preserving data privacy in outsourcing data aggregation services
Authors: Xiong Li , Chitti Subramanyam , Liu Ling
Published: September 2007

Advances in distributed service-oriented computing and Internet technology have formed a strong technology push for outsourcing and information sharing. There is an increasing need for organizations to share their data across organization boundaries both within the country and with countries that may have lesser privacy and security standards. Ideally, we wish to share certain statistical data and extract the knowledge from the private databases without revealing any additional information of each individual database apart from the aggregate result that is permitted. In this article, we describe two scenarios for outsourcing data aggregation services and present a set of decentralized peer-to-peer protocols for supporting data sharing across multiple private databases while minimizing the data disclosure among individual parties. Our basic protocols include a set of novel probabilistic computation mechanisms for important primitive data aggregation operations across multiple private databases such as max, min, and top
k
selection. We provide an analytical study of our basic protocols in terms of precision, efficiency, and privacy characteristics. Our advanced protocols implement an efficient algorithm for performing
k
NN classification across multiple private databases. We provide a set of experiments to evaluate the proposed protocols in terms of their correctness, efficiency, and privacy characteristics.
Untangling the usability of fisheye menus
Authors: Hornbæk Kasper , Hertzum Morten
Published: September 2007

Fisheye menus have become a prominent example of fisheye interfaces, yet contain several nonfisheye elements and have not been systematically evaluated. This study investigates whether fisheye menus are useful, and tries to untangle the impact on usability of the following properties of fisheye menus: use of distortion, index of letters for coarse navigation, and the focus-lock mode for accurate movement. Twelve participants took part in an experiment comparing fisheye menus with three alternative menu designs across known-item and browsing tasks, as well as across alphabetical and categorical menu structures. The results show that for finding known items, conventional hierarchical menus are the most accurate and by far the fastest. In addition, participants rate the hierarchical menu as more satisfying than fisheye and multifocus menus, but do not consistently prefer any one menu. For browsing tasks, the menus neither differ with respect to accuracy nor selection time. Eye-movement data show that participants make little use of nonfocus regions of the fisheye menu, though these are a defining feature of fisheye interfaces. Nonfocus regions are used more with the multifocus menu, which enlarges important menu items in these regions. With the hierarchical menu, participants make shorter fixations and have shorter scanpaths, suggesting lower requirements for mental activity and visual search. We conclude by discussing why fisheye menus are inferior to the hierarchical menu and how both may be improved.
Constructing reality
Authors: Corter James E. , Nickerson Jeffrey V. , Esche Sven K. , Chassapis Constantin , Im Seongah , Ma Jing
Published: September 2007

Laboratories play a crucial role in the education of future scientists and engineers, yet there is disagreement among science and engineering educators about whether and which types of technology-enabled labs should be used. This debate could be advanced by large-scale randomized studies addressing the critical issue of whether remotely operated or simulation-based labs are as effective as the traditional hands-on lab format. The present article describes the results of a large-scale (N = 306) study comparing learning outcomes and student preferences for several different lab formats in an undergraduate engineering course. The lab formats that were evaluated included traditional hands-on labs, remotely operated labs, and simulations. Learning outcomes were assessed by a test of the specific concepts taught in each lab. These knowledge scores were as high or higher (depending on topic) after performing remote and simulated laboratories versus performing hands-on laboratories. In their responses to survey items, many students saw advantages to technology-enabled lab formats in terms of such attributes as convenience and reliability, but still expressed preference for hands-on labs. Also, differences in lab formats led to changes in group functions across the plan-experiment-analyze process: For example, students did less face-to-face work when engaged in remote or simulated laboratories, as opposed to hands-on laboratories.
Modeling the effects of delayed haptic and visual feedback in a collaborative virtual environment
Authors: Jay Caroline , Glencross Mashhuda , Hubbold Roger
Published: September 2007

Collaborative virtual environments (CVEs) enable two or more people, separated in the real world, to share the same virtual “space.” They can be used for many purposes, from teleconferencing to training people to perform assembly tasks. Unfortunately, the effectiveness of CVEs is compromised by one major problem: the delay that exists in the networks linking users together. Whilst we have a good understanding, especially in the visual modality, of how users are affected by delayed feedback from their own actions, little research has systematically examined how users are affected by delayed feedback from other people, particularly in environments that support haptic (force) feedback. The current study addresses this issue by quantifying how increasing levels of latency affect visual and haptic feedback in a collaborative target acquisition task. Our results demonstrate that haptic feedback in particular is very sensitive to low levels of delay. Whilst latency affects visual feedback from 50 ms, it impacts on haptic task performance 25 ms earlier, and causes the haptic measures of performance deterioration to rise far more steeply than visual. The “impact-perceive-adapt” model of user performance, which considers the interaction between performance measures, perception of latency, and the breakdown of perception of immediate causality, is proposed as an explanation for the observed pattern of performance.
Rx
Authors: Qin Feng , Tucek Joseph , Zhou Yuanyuan , Sundaresan Jagadeesan
Published: September 2007

Many applications demand availability. Unfortunately, software failures greatly reduce system availability. Prior work on surviving software failures suffers from one or more of the following limitations: required application restructuring, inability to address deterministic software bugs, unsafe speculation on program execution, and long recovery time.

This paper proposes an innovative
safe
technique, called Rx, which can quickly recover programs from many types of software bugs, both deterministic and nondeterministic. Our idea, inspired from allergy treatment in real life, is to rollback the program to a recent checkpoint upon a software failure, and then to reexecute the program in a
modified
environment. We base this idea on the observation that many bugs are correlated with the execution environment, and therefore can be avoided by removing the “allergen” from the environment. Rx requires few to no modifications to applications and provides programmers with additional feedback for bug diagnosis.

We have implemented Rx on Linux. Our experiments with five server applications that contain seven bugs of various types show that Rx can survive six out of seven software failures and provide transparent fast recovery within 0.017--0.16 seconds, 21--53 times faster than the whole program restart approach for all but one case (CVS). In contrast, the two tested alternatives, a whole program restart approach and a simple rollback and reexecution without environmental changes, cannot successfully recover the four servers (Squid, Apache, CVS, and ypserv) that contain deterministic bugs, and have only a 40% recovery rate for the server (MySQL) that contains a nondeterministic concurrency bug. Additionally, Rx's checkpointing system is lightweight, imposing small time and space overheads.
Gossip-based peer sampling
Authors: Jelasity Márk , Voulgaris Spyros , Guerraoui Rachid , Kermarrec Anne-Marie , van Steen Maarten
Published: September 2007

Gossip-based communication protocols are appealing in large-scale distributed applications such as information dissemination, aggregation, and overlay topology management. This paper factors out a fundamental mechanism at the heart of all these protocols: the
peer-sampling
service. In short, this service provides every node with peers to gossip with. We promote this service to the level of a first-class abstraction of a large-scale distributed system, similar to a name service being a first-class abstraction of a local-area system. We present a generic framework to implement a peer-sampling service in a decentralized manner by constructing and maintaining
dynamic unstructured
overlays through gossiping membership information itself. Our framework generalizes existing approaches and makes it easy to discover new ones. We use this framework to empirically explore and compare several implementations of the peer-sampling service. Through extensive simulation experiments we show that---although all protocols provide a good quality uniform random stream of peers to each node locally---traditional theoretical assumptions about the randomness of the unstructured overlays as a whole do not hold in any of the instances. We also show that different design decisions result in severe differences from the point of view of two crucial aspects: load balancing and fault tolerance. Our simulations are validated by means of a wide-area implementation.
Cross-component energy management
Authors: Li Xiaodong , Gupta Ritu , Adve Sarita V. , Zhou Yuanyuan
Published: September 2007

Researchers have proposed the use of adaptation to reduce the energy consumption of different hardware components, such as the processor, memory, disk, and display for general-purpose applications. Previous algorithms to control these adaptations, however, have focused on a single component. This work takes the first step toward developing algorithms that can jointly control adaptations in multiple interacting components for general-purpose applications, with the goal of minimizing the total energy consumed within a specified performance loss. Specifically, we develop a joint-adaptation algorithm for processor and memory adaptations. We identify two properties that enable per-component algorithms to be easily used in a cross-component context---the algorithms' performance impact must be guaranteed and composable. We then modify a current processor and a memory algorithm to obey these properties. This allows the cross-component problem to be reduced to determine an appropriate (energy-optimal) allocation of the target performance loss (slack) between the two components. We develop such an optimal slack allocation algorithm that exploits the above properties. The result is an efficient cross-component adaptation framework that minimizes the total energy of the processor and memory without exceeding the target performance loss, while substantially leveraging current per-component algorithms. Our experiments show that joint processor and memory adaptation provides significantly more energy savings than adapting either component alone; intelligent slack distribution is specifically effective for highly compute- or memory-intensive applications; and the performance slowdown never exceeds the specification.
Fairness enforcement in switch on event multithreading
Authors: Gabor Ron , Weiss Shlomo , Mendelson Avi
Published: September 2007

The need to reduce power and complexity will increase the interest in Switch On Event multithreading (coarse-grained multithreading). Switch On Event multithreading is a low-power and low-complexity mechanism to improve processor throughput by switching threads on execution stalls. Fairness may, however, become a problem in a multithreaded processor. Unless fairness is properly handled, some threads may starve while others consume all of the processor cycles. Heuristics that were devised in order to improve fairness in simultaneous multithreading are not applicable to Switch On Event multithreading. This paper defines the fairness metric using the ratio of the individual threads' speedups and shows how it can be enforced in Switch On Event multithreading. Fairness is controlled by forcing additional thread switch points. These switch points are determined dynamically by runtime estimation of the single threaded performance of each of the individual threads. We analyze the impact of the fairness enforcement mechanism on aggregate IPC and weighted speedup. We present simulation results of the performance of Switch On Event multithreading. Switch On Event multithreading achieves an average aggregate IPC increase of 26% over single thread and 12% weighted speedup when no fairness is enforced. In this case, a sixth of our runs resulted in poor fairness in which one thread ran extremely slowly (10 to 100 times slower than its single-thread performance), while the other thread's performance was hardly affected. By using the proposed mechanism, we can guarantee fairness at different levels of strictness and, in most cases, even improve the weighted speedup.
Precise automatable analytical modeling of the cache behavior of codes with indirections
Authors: Andrade Diego , Fraguela Basilio B. , Doallo Ramón
Published: September 2007

The performance of memory hierarchies, in which caches play an essential role, is critical in nowadays general-purpose and embedded computing systems because of the growing memory bottleneck problem. Unfortunately, cache behavior is very unstable and difficult to predict. This is particularly true in the presence of irregular access patterns, which exhibit little locality. Such patterns are very common, for example, in applications in which pointers or compressed sparse matrices give place to indirections. Nevertheless, cache behavior in the presence of irregular access patterns has not been widely studied. In this paper we present an extension of a systematic analytical modeling technique based on PMEs (probabilistic miss equations), previously developed by the authors, that allows the automated analysis of the cache behavior for codes with irregular access patterns resulting from indirections. The model generates very accurate predictions despite the irregularities and has very low computing requirements, being the first model that gathers these desirable characteristics that can automatically analyze this kind of codes. These properties enable this model to help drive compiler optimizations, as we show with an example.
Java object header elimination for reduced memory consumption in 64-bit virtual machines
Authors: Venstermans Kris , Eeckhout Lieven , De Bosschere Koen
Published: September 2007

Memory performance is an important design issue for contemporary computer systems given the huge processor/memory speed gap. This paper proposes a space-efficient Java object model for reducing the memory consumption of 64-bit Java virtual machines. We completely eliminate the object header through typed virtual addressing (TVA) or implicit typing. TVA encodes the object type in the object's virtual address by allocating all objects of a given type in a contiguous memory segment. This allows for removing the type information as well as the status field from the object header. Whenever type and status information is needed, masking is applied to the object's virtual address for obtaining an offset into type and status information structures. Unlike previous work on implicit typing, we apply TVA to a selected number of frequently allocated object types, hence, the name selective TVA (STVA); this limits the amount of memory fragmentation. In addition to applying STVA, we also compress the type information block (TIB) pointers for all objects that do not fall under TVA. We implement the space-efficient Java object model in the 64-bit version of the Jikes RVM on an AIX IBM platform and compare its performance against the traditionally used Java object model using a multitude of Java benchmarks. We conclude that the space-efficient Java object model reduces memory consumption by on average 15% (and up to 45% for some benchmarks). About one-half the reduction comes from TIB pointer compression; the other one-half comes from STVA. In terms of performance, the space-efficient object model generally does not affect performance; however, for some benchmarks we observe statistically significant performance speedups, up to 20%.
Unified control flow and data dependence traces
Authors: Tallam Sriraman , Gupta Rajiv
Published: September 2007

We describe the design, generation, and compression of the
extended whole program path
(eWPP), representation that not only captures the control flow history of a program execution but also its data dependence history. This representation is motivated by the observation that, typically, a significant fraction of data dependence history can be recovered from the control flow trace. To capture the remainder of the data dependence history, we introduce
disambiguation checks
in the program whose control flow signatures capture the results of the checks. The resulting extended control flow trace enables the recovery of otherwise irrecoverable data dependences. The code for the checks is designed to minimize the increase in program execution time and the extended control flow trace size when compared to directly collecting control flow and address traces. Our experiments show that compressed eWPPs are only one-quarter of the size of combined compressed control flow and address traces. However, their collection incurs a 5× increase in runtime overhead relative to the overhead required for directly collecting the control flow and address traces, respectively.
Probabilistic design of multimedia embedded systems
Authors: Hua Shaoxiong , Qu Gang , Bhattacharyya Shuvra S.
Published: September 2007

In this paper, we propose the novel concept of probabilistic design for multimedia embedded systems, which is motivated by the challenge of how to design, but not overdesign, such systems while systematically incorporating performance requirements of multimedia application, uncertainties in execution time, and tolerance for reasonable execution failures. Unlike most present techniques that are based on either worst- or average-case execution times of application tasks, where the former guarantees the completion of each execution, but often leads to overdesigned systems, and the latter fails to provide any completion guarantees, the proposed probabilistic design method takes advantage of unique features mentioned above of multimedia systems to relax the rigid hardware requirements for software implementation and avoid overdesigning the system. In essence, this relaxation expands the design space and we further develop an off-line on-line minimum effort algorithm for quick exploration of the enlarged design space at early design stages. This is the first step toward our goal of bridging the gap between real-time analysis and embedded software implementation for rapid and economic multimedia system design. It is our belief that the proposed method has great potential in reducing system resource while meeting performance requirements. The experimental results confirm this as we achieve significant saving in system's energy consumption to provide a statistical completion ratio guarantee (i.e., the expected number of completions over a large number of iterations is greater than a given value).
Techniques for maintaining connectivity in wireless ad-hoc networks under energy constraints
Authors: Koushanfar Farinaz , Davare Abhijit , Nguyen David T. , Sangiovanni-Vincentelli Alberto , Potkonjak Miodrag
Published: September 2007

Distributed wireless systems (DWSs) are emerging as the enabler for next-generation wireless applications. There is a consensus that DWS-based applications, such as pervasive computing, sensor networks, wireless information networks, and speech and data communication networks, will form the backbone of the next technological revolution. Simultaneously, with great economic, industrial, consumer, and scientific potential, DWSs pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize the lifetime of the network using only local information, while preserving network connectivity. We start by introducing the care-free sleep (CS) Theorem that provides provably optimal conditions for a node to go into sleep mode while ensuring that global connectivity is not affected. The CS theorem is the basis for an efficient localized algorithm that decides which nodes will go to into sleep mode and for how long. We have also developed mechanisms for collecting neighborhood information and for the coordination of distributed energy minimization protocols. The effectiveness of the approach is demonstrated using a comprehensive study of the performance of the algorithm over a wide range of network parameters. Another important highlight is the first mathematical and Monte Carlo analysis that establishes the importance of considering nodes within a small number of hops in order to preserve energy.
Hardware/software IP integration using the ROSES design environment
Authors: Wagner Flávio R. , Cesário Wander , Jerraya Ahmed A.
Published: September 2007

Considering current time-to-market pressures, IP reuse is mandatory for the design of complex embedded systems-on-chip (SoC). The integration of IP components into a given design is the most complex task in the whole reuse process. This paper describes the IP integration approach implemented in the ROSES design environment, which presents a unique combination of features that enhance IP reuse: automatic assembly of interfaces between heterogeneous software and hardware IP components; easy adaptation to different on-chip communication structures and bus and core standards; generation of customized and minimal OSs for programmable components; and an architecture-independent high-level API embedded into SystemC that makes application software independent from system implementation. Application code is written by using communication functions available in this API. ROSES automatically assembles wrappers that implement these functions, such that the application code does not need to be modified in order to run in the final synthesized system.
A log buffer-based flash translation layer using fully-associative sector translation
Authors: Lee Sang-Won , Park Dong-Joo , Chung Tae-Sun , Lee Dong-Ho , Park Sangwon , Song Ha-Joo
Published: September 2007

Flash memory is being rapidly deployed as data storage for mobile devices such as PDAs, MP3 players, mobile phones, and digital cameras, mainly because of its low electronic power, nonvolatile storage, high performance, physical stability, and portability. One disadvantage of flash memory is that prewritten data cannot be dynamically overwritten. Before overwriting prewritten data, a time-consuming erase operation on the used blocks must precede, which significantly degrades the overall write performance of flash memory. In order to solve this “erase-before-write” problem, the flash memory controller can be integrated with a software module, called “flash translation layer (FTL).” Among many FTL schemes available, the log block buffer scheme is considered to be optimum. With this scheme, a small number of log blocks, a kind of write buffer, can improve the performance of write operations by reducing the number of erase operations. However, this scheme can suffer from low space utilization of log blocks. In this paper, we show that there is much room for performance improvement in the log buffer block scheme, and propose an enhanced log block buffer scheme, called FAST (full associative sector translation). Our FAST scheme improves the space utilization of log blocks using fully-associative sector translations for the log block sectors. We also show empirically that our FAST scheme outperforms the pure log block buffer scheme.
Efficient columnar storage in B-trees
Authors: Graefe Goetz
Published: September 2007

Column-oriented storage formats have been proposed for query processing in relational data warehouses, specifically for fast scans over non-indexed columns. This short note proposes a data compression method that reuses traditional on-disk B-tree structures with only minor changes yet achieves storage density and scan performance comparable to specialized columnar designs. The advantage of the proposed method over alternative storage structures is that traditional algorithms can be reused, e.g., for assembling rows with multiple columns, bulk insertion and deletion, logging and recovery, consistency checking, etc.
Finding shapes in a set of points
Authors: Ross Kenneth A. , Vespe David , Hessing David , Jain Pranay
Published: September 2007

We present a tool for querying a set of points for geometric shapes. This tool was developed as part of a larger project studying the architecture of 13th century French churches. We present a query language for specifying shapes. We describe an implementation of the tool that optimizes and executes shape queries. We describe the performance of the tool, and show examples of how it can be used to analyze building floorplans. The tool is available for download over the internet.
Developmental informatics at IIT Bombay
Authors: Bahuman Anil , Bahuman Chaitra , Baru Malati , Duttagupta Subhasri , Ramamritham Krithi
Published: September 2007

IIT Bombay's Developmental Informatics Lab is a cross disciplinary group consisting of 6 faculty, 30 research staff and several students. The lab is working towards increasing access to information -- through the use of internet and communication technologies -- to communities in the developing world especially rural and small town India. The lab is supported by Indian Government funding sources as well as corporate and multi-lateral agencies to solve technical problems in local communities in sustainable ways. This paper focuses on two mature projects of the lab -- one caters to Indian farmers while another helps with the education of tribal populations.
Report on the First International VLDB Workshop on Clean Databases (CleanDB 2006)
Authors: Lee Dongwon , Li Chen
Published: September 2007

In this report, we provide a summary of the First Int'l VLDB Workshop on Clean Databases (CleanDB 2006), which took place at Seoul, Korea, on September 11, 2006, in conjunction with the 32nd Int'l Conference on Very Large Data Bases (VLDB).
High diversity transforms multimedia information retrieval into a cross-cutting field
Authors: Wang James Z. , Boujemaa Nozha , Chen Yixin
Published: September 2007

Indexing and retrieval of large quantity of multimedia data is a highly challenging and growingly important problem for the computer science research community. Researchers in multimedia, databases, computer vision, machine learning, signal and image processing and statistics have worked on multimedia information retrieval (MIR) for over a decade. A number of significant technological advances have been achieved in this field. Some of the techniques have been applied to application areas such as art image retrieval, biomedical image and video retrieval, education, sensor networks, large-scale online personal and professional photo sharing communities, classification and filtering of images on the Web, scientific content, computer forensics, threat assessment and security applications more generally.
Frequently-asked questions about double-blind reviewing
Authors: Snodgrass Richard
Published: September 2007

As announced in an editorial [Snodgrass 2007], ACM
Transactions on Database Systems
has adopted double-blind reviewing, in which the identities of the author and the reviewer are not known to each other. That editorial provided a comprehensive analysis of the costs of double-blind reviewing (DBR) and a detailed examination of the decision.
Solid texture synthesis from 2D exemplars
Authors: Kopf Johannes , Fu Chi-Wing , Cohen-Or Daniel , Deussen Oliver , Lischinski Dani , Wong Tien-Tsin
Published: September 2007

We present a novel method for synthesizing solid textures from 2D texture exemplars. First, we extend 2D texture optimization techniques to synthesize 3D texture solids. Next, the non-parametric texture optimization approach is integrated with histogram matching, which forces the global statistics of the synthesized solid to match those of the exemplar. This improves the convergence of the synthesis process and enables using smaller neighborhoods. In addition to producing compelling texture mapped surfaces, our method also effectively models the material in the interior of solid objects. We also demonstrate that our method is well-suited for synthesizing textures with a large number of channels per texel.
Photo clip art
Authors: Lalonde Jean-François , Hoiem Derek , Efros Alexei A. , Rother Carsten , Winn John , Criminisi Antonio
Published: September 2007

We present a system for inserting new objects into existing photographs by querying a vast image-based object library, pre-computed using a publicly available Internet object database. The central goal is to shield the user from all of the arduous tasks typically involved in image compositing. The user is only asked to do two simple things: 1) pick a 3D location in the scene to place a new object; 2) select an object to insert using a hierarchical menu. We pose the problem of object insertion as a data-driven, 3D-based, context-sensitive object retrieval task. Instead of trying to manipulate the object to change its orientation, color distribution, etc. to fit the new image, we simply retrieve an object of a specified class that has all the required properties (camera pose, lighting, resolution, etc) from our large object library. We present new automatic algorithms for improving object segmentation and blending, estimating true 3D object size and orientation, and estimating scene lighting conditions. We also present an intuitive user interface that makes object insertion fast and simple even for the artistically challenged.
Scene completion using millions of photographs
Authors: Hays James , Efros Alexei A.
Published: September 2007

What can you do with a million images? In this paper we present a new image completion algorithm powered by a huge database of photographs gathered from the Web. The algorithm patches up holes in images by finding similar image regions in the database that are not only seamless but also semantically valid. Our chief insight is that while the space of images is effectively infinite, the space of semantically differentiable scenes is actually not that large. For many image completion tasks we are able to find similar scenes which contain image fragments that will convincingly complete the image. Our algorithm is entirely data-driven, requiring no annotations or labelling by the user. Unlike existing image completion methods, our algorithm can generate a diverse set of results for each input image and we allow users to select among them. We demonstrate the superiority of our algorithm over existing image completion approaches.
Responsive characters from motion fragments
Authors: McCann James , Pollard Nancy
Published: September 2007

In game environments, animated character motion must rapidly adapt to changes in player input - for example, if a directional signal from the player's gamepad is not incorporated into the character's trajectory immediately, the character may blithely run off a ledge. Traditional schemes for data-driven character animation lack the split-second reactivity required for this direct control; while they can be made to work, motion artifacts will result. We describe an on-line character animation controller that assembles a motion stream from short motion fragments, choosing each fragment based on current player input and the previous fragment. By adding a simple model of player behavior we are able to improve an existing reinforcement learning method for precalculating good fragment choices. We demonstrate the efficacy of our model by comparing the animation selected by our new controller to that selected by existing methods and to the optimal selection, given knowledge of the entire path. This comparison is performed over real-world data collected from a game prototype. Finally, we provide results indicating that occasional low-quality transitions between motion segments are crucial to high-quality on-line motion generation; this is an important result for others crafting animation systems for directly-controlled characters, as it argues against the common practice of transition thresholding.
Near-optimal character animation with continuous control
Authors: Treuille Adrien , Lee Yongjoon , Popović Zoran
Published: September 2007

We present a new approach to realtime character animation with interactive control. Given a corpus of motion capture data and a desired task, we automatically compute near-optimal controllers using a low-dimensional basis representation. We show that these controllers produce motion that fluidly responds to several dimensions of user control and environmental constraints in realtime. Our results indicate that very few basis functions are required to create high-fidelity character controllers which permit complex user navigation and obstacle-avoidance tasks.
Soft scissors
Authors: Wang Jue , Agrawala Maneesh , Cohen Michael F.
Published: September 2007

We present
Soft Scissors
, an interactive tool for extracting alpha mattes of foreground objects in realtime. We recently proposed a novel offline matting algorithm capable of extracting high-quality mattes for complex foreground objects such as furry animals [Wang and Cohen 2007]. In this paper we both improve the quality of our offline algorithm and give it the ability to incrementally update the matte in an online interactive setting. Our realtime system efficiently estimates foreground color thereby allowing both the matte and the final composite to be revealed instantly as the user roughly paints along the edge of the foreground object. In addition, our system can dynamically adjust the width and boundary conditions of the scissoring paint brush to approximately capture the boundary of the foreground object that lies ahead on the scissor's path. These advantages in both speed and accuracy create the first interactive tool for high quality image matting and compositing.
Image vectorization using optimized gradient meshes
Authors: Sun Jian , Liang Lin , Wen Fang , Shum Heung-Yeung
Published: September 2007

Recently, gradient meshes have been introduced as a powerful vector graphics representation to draw multicolored mesh objects with smooth transitions. Using tools from Abode Illustrator and Corel CorelDraw, a user can manually create gradient meshes even for photo-realistic vector arts, which can be further edited, stylized and animated.

In this paper, we present an easy-to-use interactive tool, called
optimized gradient mesh
, to semi-automatically and quickly create gradient meshes from a raster image. We obtain the optimized gradient mesh by formulating an energy minimization problem. The user can also interactively specify a few vector lines to guide the mesh generation. The resulting optimized gradient mesh is an editable and scalable mesh that otherwise would have taken many hours for a user to manually create.
Detail preserving shape deformation in image editing
Authors: Fang Hui , Hart John C.
Published: September 2007

Shape deformation is a common practice in digital image editing, but can unrealistically stretch or compress texture detail. We propose an image editing system that decouples feature position from pixel color generation, by resynthesizing texture from the source image to preserve its detail and orientation around a new feature curve location. We introduce a new distortion to patch-based texture synthesis that aligns texture features with image features. A dense correspondence field between source and target images generated by the control curves then guides texture synthesis.