Theory and Algorithms Commons^™

User Interface Design, Moritz Stefaner, Sebastien Ferre, Saverio Perugini, Jonathan Koren, Yi Zhang

Saverio Perugini

As detailed in Chap. 1, system implementations for dynamic taxonomies and faceted search allow a wide range of query possibilities on the data. Only when these are made accessible by appropriate user interfaces, the resulting applications can support a variety of search, browsing and analysis tasks. User interface design in this area is confronted with specific challenges. This chapter presents an overview of both established and novel principles and solutions.

An Immersive Telepresence System Using Rgb-D Sensors And Head-Mounted Display, Xinzhong Lu, Ju Shen, Saverio Perugini, Jianjun Yang

Saverio Perugini

We present a tele-immersive system that enables people to interact with each other in a virtual world using body gestures in addition to verbal communication. Beyond the obvious applications, including general online conversations and gaming, we hypothesize that our proposed system would be particularly beneficial to education by offering rich visual contents and interactivity. One distinct feature is the integration of egocentric pose recognition that allows participants to use their gestures to demonstrate and manipulate virtual objects simultaneously. This functionality enables the instructor to effectively and efficiently explain and illustrate complex concepts or sophisticated problems in an intuitive manner. The …

Query Analyzer And Manager For Complex Event Processing As A Service, Wilson Higashino, Cedric Eichler, Miriam A M Capretz, Thierry Monteil, M. Beatriz F. Toledo, Patricia Stolf

Wilson A Higashino

Complex Event Processing (CEP) is a set of tools and techniques that can be used to obtain insights from high-volume, high-velocity continuous streams of events. CEP-based systems have been adopted in many situations that require prompt establishment of system diagnostics and execution of reaction plans, such as in monitoring of complex systems. This article describes the Query Analyzer and Manager (QAM) module, a first effort toward the development of a CEP as a Service (CEPaaS) system. This module is responsible for analyzing user-defined CEP queries and for managing their execution in distributed cloud-based environments. Using a language-agnostic internal query representation, …

Evaluation Of Particle Swarm Optimization Applied To Grid Scheduling, Wilson Higashino, Miriam Capretz, M. Beatriz Toledo

Wilson A Higashino

The problem of scheduling independent users’ jobs to resources in Grid Computing systems is of paramount importance. This problem is known to be NP-hard, and many techniques have been proposed to solve it, such as heuristics, genetic algorithms (GA), and, more recently, particle swarm optimization (PSO). This article aims to use PSO to solve grid scheduling problems, and compare it with other techniques. It is shown that many often-overlooked implementation details can have a huge impact on the performance of the method. In addition, experiments also show that the PSO has a tendency to stagnate around local minima in high-dimensional …

Network And Energy-Aware Resource Selection Model For Opportunistic Grids, Izaias Faria, Mario Dantas, Miriam A M Capretz, Wilson Higashino

Wilson A Higashino

Due to increasing hardware capacity, computing grids have been handling and processing more data. This has led to higher amount of energy being consumed by grids; hence the necessity for strategies to reduce their energy consumption. Scheduling is a process carried out to define in which node tasks will be executed in the grid. This process can significantly impact the global system performance, including energy consumption. This paper focuses on a scheduling model for opportunistic grids that considers network traffic, distance between input files and execution node as well as the execution node status. The model was tested in a …

Residual-Based Measurement Of Peer And Link Lifetimes In Gnutella Networks, Xiaoming Wang, Zhongmei Yao, Dmitri Loguinov

Zhongmei Yao

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent …

Modeling Heterogeneous User Churn And Local Resilience Of Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov, Xiaoming Wang

Zhongmei Yao

Previous analytical results on the resilience of unstructured P2P systems have not explicitly modeled heterogeneity of user churn (i.e., difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a generic model of heterogeneous user churn, derive the distribution of the various metrics observed in prior experimental studies (e.g., lifetime distribution of joining users, joint distribution of session time of alive peers, and residual lifetime of a randomly selected user), derive several closed-form results on the transient behavior of in-degree, and eventually obtain the joint in/out degree isolation probability as a simple …

Robust Lifetime Measurement In Large-Scale P2p Systems With Non-Stationary Arrivals, Xiaoming Wang, Zhongmei Yao, Yueping Zhang, Dmitri Loguinov

Zhongmei Yao

Characterizing user churn has become an important topic in studying P2P networks, both in theoretical analysis and system design. Recent work has shown that direct sampling of user lifetimes may lead to certain bias (arising from missed peers and round-off inconsistencies) and proposed a technique that estimates lifetimes based on sampled residuals. In this paper, however, we show that under non-stationary arrivals, which are often present in real systems, residual-based sampling does not correctly reconstruct user lifetimes and suffers a varying degree of bias, which in some cases makes estimation completely impossible. We overcome this problem using two contributions: a …

In-Degree Dynamics Of Large-Scale P2p Systems, Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov

Zhongmei Yao

This paper builds a complete modeling framework for understanding user churn and in-degree dynamics in unstructured P2P systems in which each user can be viewed as a stationary alternating renewal process. While the classical Poisson result on the superposition of n stationary renewal processes for n→∞ requires that each point process become sparser as n increases, it is often difficult to rigorously show this condition in practice. In this paper, we first prove that despite user heterogeneity and non-Poisson arrival dynamics, a superposition of edge-arrival processes to a live user under uniform selection converges to a Poisson process when …

Automatically Discovering The Number Of Clusters In Web Page Datasets, Zhongmei Yao

Zhongmei Yao

Clustering is well-suited for Web mining by automatically organizing Web pages into categories, each of which contains Web pages having similar contents. However, one problem in clustering is the lack of general methods to automatically determine the number of categories or clusters. For the Web domain in particular, currently there is no such method suitable for Web page clustering. In an attempt to address this problem, we discover a constant factor that characterizes the Web domain, based on which we propose a new method for automatically determining the number of clusters in Web page data sets. We discover that the …

The Staging Transformation Approach To Mixing Initiative, Robert Capra, Michael Narayan, Saverio Perugini, Naren Ramakrishnan, Manuel A. Pérez-Quiñones

Saverio Perugini

Mixed-initiative interaction is an important facet of many conversational interfaces, flexible planning architectures, intelligent tutoring systems, and interactive information retrieval systems. Software systems for mixed-initiative interaction must enable us to both operationalize the mixing of initiative (i.e., support the creation of practical dialogs) and to reason in real-time about how a flexible mode of interaction can be supported (e.g., from a meta-dialog standpoint). In this paper, we present the staging transformation approach to mixing initiative, where a dialog script captures the structure of the dialog and dialog control processes are realized through generous use of program transformation techniques (e.g., partial …

Personalizing Interactions With Information Systems, Saverio Perugini, Naren Ramakrishnan

Saverio Perugini

Personalization constitutes the mechanisms and technologies necessary to customize information access to the end-user. It can be defined as the automatic adjustment of information content, structure, and presentation tailored to the individual. In this chapter, we study personalization from the viewpoint of personalizing interaction. The survey covers mechanisms for information-finding on the web, advanced information retrieval systems, dialog-based applications, and mobile access paradigms. Specific emphasis is placed on studying how users interact with an information system and how the system can encourage and foster interaction. This helps bring out the role of the personalization system as a facilitator which reconciles …

Mining Web-Functional Dependencies For Flexible Information Access, Saverio Perugini, Naren Ramakrishnan

Saverio Perugini

We present an approach to enhancing information access through Web structure mining in contrast to traditional approaches involving usage mining. Specifically, we mine the hardwired hierarchical hyperlink structure of Web sites to identify patterns of term-term co-occurrences we call Web functional dependencies (FDs). Intuitively, a Web FD ‘x y’ declares that all paths through a site involving a hyperlink labeled x also contain a hyperlink labeled y. The complete set of FDs satisfied by a site help characterize (flexible and expressive) interaction paradigms supported by a site, where a paradigm is the set of explorable sequences therein. …

Personalization By Website Transformation: Theory And Practice, Saverio Perugini

Saverio Perugini

We present an analysis of a progressive series of out-of-turn transformations on a hierarchical website to personalize a user’s interaction with the site. We formalize the transformation in graph-theoretic terms and describe a toolkit we built that enumerates all of the traversals enabled by every possible complete series of these transformations in any site and computes a variety of metrics while simulating each traversal therein to qualify the relationship between a site’s structure and the cumulative effect of support for the transformation in a site. We employed this toolkit in two websites. The results indicate that the transformation enables users …

Staging Transformations For Multimodal Web Interaction Management, Michael Narayan, Christopher Williams, Saverio Perugini, Naren Ramakrishnan

Saverio Perugini

Multimodal interfaces are becoming increasingly ubiquitous with the advent of mobile devices, accessibility considerations, and novel software technologies that combine diverse interaction media. In addition to improving access and delivery capabilities, such interfaces enable flexible and personalized dialogs with websites, much like a conversation between humans. In this paper, we present a software framework for multimodal web interaction management that supports mixed-initiative dialogs between users and websites. A mixed-initiative dialog is one where the user and the website take turns changing the flow of interaction. The framework supports the functional specification and realization of such dialogs using staging transformations – …

Clustering Of Search Trajectory And Its Application To Parameter Tuning, Linda Lindawati, Hoong Chuin Lau, David Lo

David LO

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as …

Aidr: Artificial Intelligence For Disaster Response, Muhammad Imran, Carlos Castillo, Ji Lucas, Patrick Meier, Sarah Vieweg

Muhammad Imran

We present AIDR (Artificial Intelligence for Disaster Response), a platform designed to perform automatic classification of crisis-related microblog communications. AIDR enables humans and machines to work together to apply human intelligence to large-scale data at high speed. The objective of AIDR is to classify messages that people post during disasters into a set of user-defined categories of information (e.g., "needs", "damage", etc.) For this purpose, the system continuously ingests data from Twitter, processes it (i.e., using machine learning classification techniques) and leverages human-participation (through crowdsourcing) in real-time. AIDR has been successfully tested to classify informative vs. non-informative tweets posted during …

Model-Based Software Engineering For An Imaging Cubesat And Its Extrapolation To Other Missions, Atif Mohammad, Jeremy Straub, Christoffer Korvald, Emanuel Grant

Jeremy Straub

Small satellites with their limited computational capabilities require that software engineering techniques promote efficient use of spacecraft resources. A model-driven approach to software engineering is an excellent solution to this resource maximization challenge as it facilitates visualization of the key solution processes and data elements.

The software engineering process utilized for the OpenOrbiter spacecraft, which is a remote sensing technology demonstrator, is presented. Key challenges presented by the Open Orbiter project included concurrent operation and tasking of five computer-on-module (COM) units and a flight computer and the associated data marshaling between local and general storage. The payload processing system (consisting …

Precis: A Design-Time Precision Analysis Tool, Mark L. Chang, Scott Hauck

Mark L. Chang

Currently, few tools exist to aid the FPGA developer in translating an algorithm designed for a general-purpose-processor into one that is precision-optimized for FPGAs. This task requires extensive knowledge of both the algorithm and the target hardware. We present a design-time tool, Precis, which assists the developer in analyzing the precision requirements of algorithms specified in MATLAB. Through the combined use of simulation, user input, and program analysis, we demonstrate a methodology for precision analysis that can aid the developer in focusing their manual precision optimization efforts.

Non-Redundant Sequential Rules,Theory And Algorithm, David Lo, Siau-Cheng Khoo, Limsoon Wong

David LO

A sequential rule expresses a relationship between two series of events happening one after another. Sequential rules are potentially useful for analyzing data in sequential format, ranging from purchase histories, network logs and program execution traces. In this work, we investigate and propose a syntactic characterization of a non-redundant set of sequential rules built upon past work on compact set of representative patterns. A rule is redundant if it can be inferred from another rule having the same support and confidence. When using the set of mined rules as a composite filter, replacing a full set of rules with a …

Efficient Mining Of Recurrent Rules From A Sequence Database, David Lo, Siau-Cheng Khoo, Chao Liu

David LO

We study a novel problem of mining significant recurrent rules from a sequence database. Recurrent rules have the form "whenever a series of precedent events occurs, eventually a series of consequent events occurs". Recurrent rules are intuitive and characterize behaviors in many domains. An example is in the domain of software specifications, in which the rules capture a family of program properties beneficial to program verification and bug detection. Recurrent rules generalize existing work on sequential and episode rules by considering repeated occurrences of premise and consequent events within a sequence and across multiple sequences, and by removing the "window" …

Lm: A Miner For Scenario-Based Specifications, Tuan Anh Doan, David Lo, Shahar Maoz, Siau-Cheng Khoo

David LO

We present LM, a tool for mining scenario-based specifications in the form of Live Sequence Charts, a visual language that extends sequence diagrams with modalities. LM comes with a project management component, a wizard-like interface to the mining algorithm, a set of pre- and postprocessing extensions, and a visualization module.

Application Of Triz Principles In Software Concepts, Umakant Mishra

Umakant Mishra

The Inventive Principles of TRIZ are not only applicable to mechanical or technical field; they are also applicable to Software solutions. Most of the 40 principles are easy to learn, but the question arises where to apply and how to apply. This article shows some simple examples of applying TRIZ principles.

Some people may ask, the solutions in this article are all known, what is the use of trying out TRIZ Principles on them. My answer is the art of problem solving is like learning a bicycle. If you are capable of riding the cycle on a known road, there …

Book Review: Reasoning Agents In A Dynamic World: The Frame Problem. Kenneth M. Ford And Patrick J. Hayes, Eds.,, Jozsef A. Toth

Jozsef A Toth Ph.D.

No abstract provided.