%0 Journal Article %J Autonomous Robots %D 2012 %T Automated synthesis of action selection policies for unmanned vehicles operating in adverse environments %A Svec,Petr %A Gupta, Satyandra K. %K Computer science %X We address the problem of automated action selection policy synthesis for unmanned vehicles operating in adverse environments. We introduce a new evolutionary computation-based approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. The synthesis technique consists of the automated extraction of the vehicle’s exception states and Genetic Programming (GP) for automated composition and optimization of corrective sequences of commands in the form of macro-actions to be applied locally. The focus is specifically on automated synthesis of a policy for Unmanned Surface Vehicle (USV) to efficiently block the advancement of an intruder boat toward a valuable target. This task requires the USV to utilize reactive planning complemented by short-term forward planning to generate specific maneuvers for blocking. The intruder is human-competitive and exhibits a deceptive behavior so that the USV cannot exploit regularity in its attacking behavior. We compared the performance of a hand-coded blocking policy to the performance of a policy that was automatically synthesized. Our results show that the performance of the automatically generated policy exceeds the performance of the hand-coded policy and thus demonstrates the feasibility of the proposed approach. %B Autonomous Robots %V 32 %P 149 - 164 %8 2012/// %@ 0929-5593 %G eng %U http://www.springerlink.com/content/664k84x080868141/abstract/ %N 2 %R 10.1007/s10514-011-9268-6 %0 Book Section %B Passive and Active MeasurementPassive and Active Measurement %D 2012 %T Re-wiring Activity of Malicious Networks %A Konte,Maria %A Feamster, Nick %E Taft,Nina %E Ricciato,Fabio %K Computer science %X This paper studies the AS-level re-wiring dynamics (changes in the connectivity) of malicious networks. Anecdotal evidence suggests that some malicious ASes that are primarily involved in nefarious activities on the Internet, were sequentially de-peered by providers before their final cut-off (as occurred in the well-publicized cases of Atrivo/Intercage). We present the first systematic study of the re-wiring dynamics of malicious ASes. We tracked the ASes that were listed by Hostexploit over the last two years and compared their AS-level re-wiring dynamics with non-reported ASes. Using a publicly available dataset of Customer-Provider (CP) relations in the Internet’s AS graph, we studied how interconnection between autonomous systems evolves, both for ASes that provide connectivity for attackers and ASes that were not reported as malicious. We find that malicious networks are more aggressive both in forming links with providers and changing their upstream connectivity than other ASes. Our results indicate that the re-wiring dynamics of the networks that host attacks are stable over time, despite the evolving nature of the attacks themselves, which suggests that existing defense mechanisms could benefit from incorporating these features. %B Passive and Active MeasurementPassive and Active Measurement %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 7192 %P 116 - 125 %8 2012/// %@ 978-3-642-28536-3 %G eng %U http://www.springerlink.com/content/95vn833728404877/abstract/ %0 Book Section %B Information Security %D 2011 %T Implicit Authentication through Learning User Behavior %A Elaine Shi %A Niu, Yuan %A Jakobsson, Markus %A Chow, Richard %E Burmester, Mike %E Tsudik, Gene %E Magliveras, Spyros %E Ilic, Ivana %K Computer science %X Users are increasingly dependent on mobile devices. However, current authentication methods like password entry are significantly more frustrating and difficult to perform on these devices, leading users to create and reuse shorter passwords and pins, or no authentication at all. We present implicit authentication - authenticating users based on behavior patterns. We describe our model for performing implicit authentication and assess our techniques using more than two weeks of collected data from over 50 subjects. %B Information Security %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 6531 %P 99 - 113 %8 2011 %@ 978-3-642-18177-1 %G eng %U http://www.springerlink.com/content/m57u551u3133475m/abstract/ %0 Book Section %B Advances in Cryptology – ASIACRYPT 2011 %D 2011 %T Oblivious RAM with O((logN)^3) Worst-Case Cost %A Elaine Shi %A Chan, T. %A Stefanov, Emil %A Li, Mingfei %E Lee, Dong %E Wang, Xiaoyun %K Computer science %X Oblivious RAM is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. Until recently, most prior works on Oblivious RAM aim to optimize its amortized cost, while suffering from linear or even higher worst-case cost. Such poor worst-case behavior renders these schemes impractical in realistic settings, since a data access request can occasionally be blocked waiting for an unreasonably large number of operations to complete. This paper proposes novel Oblivious RAM constructions that achieves poly-logarithmic worst-case cost, while consuming constant client-side storage. To achieve the desired worst-case asymptotic performance, we propose a novel technique in which we organize the O-RAM storage into a binary tree over data buckets, while moving data blocks obliviously along tree edges. %B Advances in Cryptology – ASIACRYPT 2011 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 7073 %P 197 - 214 %8 2011 %@ 978-3-642-25384-3 %G eng %U http://www.springerlink.com/content/2214q8013376rj37/abstract/ %0 Conference Paper %B 2011 IEEE Conference on Visual Analytics Science and Technology (VAST) %D 2011 %T TreeVersity: Comparing tree structures by topology and node's attributes differences %A Gomez,J.A.G. %A Buck-Coleman,A. %A Plaisant, Catherine %A Shneiderman, Ben %K Computer science %K data classification %K Data visualization %K Educational institutions %K hierarchy %K Image color analysis %K LifeFlow %K node attributes differences %K Pattern classification %K structural changes %K Topology %K topology attributes differences %K traffic agencies %K tree structures comparison %K trees (mathematics) %K TreeVersity %K Vegetation %K Visualization %X It is common to classify data in hierarchies, they provide a comprehensible way of understanding big amounts of data. From budgets to organizational charts or even the stock market, trees are everywhere and people find them easy to use. However when analysts need to compare two versions of the same tree structure, or two related taxonomies, the task is not so easy. Much work has been done on this topic, but almost all of it has been restricted to either compare the trees by topology, or by the node attribute values. With this project we are proposing TreeVersity, a framework for comparing tree structures, both by structural changes and by differences in the node attributes. This paper is based on our previous work on comparing traffic agencies using LifeFlow [1, 2] and on a first prototype of TreeVersity. %B 2011 IEEE Conference on Visual Analytics Science and Technology (VAST) %I IEEE %P 275 - 276 %8 2011/10/23/28 %@ 978-1-4673-0015-5 %G eng %R 10.1109/VAST.2011.6102471 %0 Conference Paper %B 2010 Proceedings IEEE INFOCOM %D 2010 %T On Computing Compression Trees for Data Collection in Wireless Sensor Networks %A Li,Jian %A Deshpande, Amol %A Khuller, Samir %K Approximation algorithms %K Base stations %K Communications Society %K Computer networks %K Computer science %K computing compression trees %K Costs %K data collection %K Data communication %K data compression %K designing algorithms %K Educational institutions %K Entropy %K graph concept %K Monitoring %K Protocols %K trees (mathematics) %K weakly connected dominating sets %K Wireless sensor networks %X We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost. %B 2010 Proceedings IEEE INFOCOM %I IEEE %P 1 - 9 %8 2010/03/14/19 %@ 978-1-4244-5836-3 %G eng %R 10.1109/INFCOM.2010.5462035 %0 Conference Paper %B 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW) %D 2010 %T Decentralized dynamic scheduling across heterogeneous multi-core desktop grids %A Jaehwan Lee %A Keleher,P. %A Sussman, Alan %K backfill jobs %K bounded waiting time %K Computer science %K decentralized dynamic scheduling %K desktop grid resource management %K Dynamic scheduling %K Educational institutions %K Environmental management %K grid computing %K heterogeneous multicore desktop grid %K job assignment %K job migration %K load balancing %K Load management %K multicore computing environment %K Peer to peer computing %K Processor scheduling %K residual resources %K resource allocation %K Resource management %K scheduling %K Scheduling algorithm %K Throughput %X The recent advent of multi-core computing environments increases both the heterogeneity and complexity of managing desktop grid resources, making efficient load balancing challenging even for a centralized manager. Even with good initial job assignments, dynamic scheduling is still needed to adapt to dynamic environments, as well as for applications whose running times are not known a priori. In this paper, we propose new decentralized scheduling schemes that backfill jobs locally and dynamically migrate waiting jobs across nodes to leverage residual resources, while guaranteeing bounded waiting times for all jobs. The methods attempt to maximize total throughput while balancing load across available grid resources. Experimental results via simulation show that our scheduling scheme has performance competitive with an online centralized scheduler. %B 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW) %I IEEE %P 1 - 9 %8 2010/04/19/23 %@ 978-1-4244-6533-0 %G eng %R 10.1109/IPDPSW.2010.5470877 %0 Conference Paper %B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) %D 2010 %T New Constructive Aspects of the Lovasz Local Lemma %A Haeupler,B. %A Saha,B. %A Srinivasan, Aravind %K acyclic edge coloring %K Algorithm design and analysis %K Approximation algorithms %K Approximation methods %K computational complexity %K Computer science %K constant factor approximation algorithm %K graph colouring %K Linearity %K Lovasz Local Lemma %K MAX k-SAT %K Monte Carlo Algorithm %K Monte Carlo methods %K Moser-Tardos algorithm %K nonrepetitive graph coloring %K output distribution %K polynomial sized core subset %K Polynomials %K Probabilistc Method %K probabilistic analysis %K probabilistic logic %K probability %K Ramsey type graph %K Sampling methods %K Santa Claus Problem %X The Lov'{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of ``bad'' events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} – the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized ``core'' subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this. %B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) %I IEEE %P 397 - 406 %8 2010/10/23/26 %@ 978-1-4244-8525-3 %G eng %R 10.1109/FOCS.2010.45 %0 Book Section %B Financial Cryptography and Data Security %D 2010 %T Signatures of Reputation %A Bethencourt, John %A Elaine Shi %A Song, Dawn %E Sion, Radu %K Computer science %B Financial Cryptography and Data Security %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 6052 %P 400 - 407 %8 2010 %@ 978-3-642-14576-6 %G eng %U http://www.springerlink.com/content/8484428n77226512/abstract/ %0 Conference Paper %B IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009 %D 2009 %T Combining powerful local and global statistics for texture description %A Yong Xu %A Si-Bin Huang %A Hui Ji %A Fermüller, Cornelia %K Computer science %K discretized measurements %K fractal geometry %K Fractals %K geometric transformations %K global statistics %K Histograms %K illumination transformations %K image classification %K image resolution %K Image texture %K lighting %K local measurements SIFT features %K local statistics %K MATHEMATICS %K multifractal spectrum %K multiscale representation %K Power engineering and energy %K Power engineering computing %K Robustness %K Solids %K Statistics %K texture description %K UMD high-resolution dataset %K wavelet frame system %K Wavelet transforms %X A texture descriptor is proposed, which combines local highly discriminative features with the global statistics of fractal geometry to achieve high descriptive power, but also invariance to geometric and illumination transformations. As local measurements SIFT features are estimated densely at multiple window sizes and discretized. On each of the discretized measurements the fractal dimension is computed to obtain the so-called multifractal spectrum, which is invariant to geometric transformations and illumination changes. Finally to achieve robustness to scale changes, a multi-scale representation of the multifractal spectrum is developed using a framelet system, that is, a redundant tight wavelet frame system. Experiments on classification demonstrate that the descriptor outperforms existing methods on the UIUC as well as the UMD high-resolution dataset. %B IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009 %I IEEE %P 573 - 580 %8 2009/06/20/25 %@ 978-1-4244-3992-8 %G eng %R 10.1109/CVPR.2009.5206741 %0 Conference Paper %B IEEE INFOCOM 2009 %D 2009 %T Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks %A Han,Bo %A Kumar,V. S.A %A Marathe,M. V %A Parthasarathy,S. %A Srinivasan, Aravind %K access hash function %K Channel allocation %K channel assignment algorithm %K channel capacity %K collision avoidance %K Computer science %K cryptography %K distributed algorithm %K distributed algorithms %K Educational institutions %K inductive-scheduling technique %K Interference %K interference set %K packet scheduling algorithm %K Peer to peer computing %K Radio network %K radio networks %K radiofrequency interference %K random oracle methodology %K scheduling %K Scheduling algorithm %K simultaneous channel allocation %K software radio %K software-defined radio wireless network capacity %K telecommunication congestion control %K telecommunication security %K Throughput %K wireless channels %K Wireless networks %X Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice. %B IEEE INFOCOM 2009 %I IEEE %P 1521 - 1529 %8 2009/04/19/25 %@ 978-1-4244-3512-8 %G eng %R 10.1109/INFCOM.2009.5062069 %0 Conference Paper %B International Conference on Computational Science and Engineering, 2009. CSE '09 %D 2009 %T First Steps to Netviz Nirvana: Evaluating Social Network Analysis with NodeXL %A Bonsignore,E. M %A Dunne,C. %A Rotman,D. %A Smith,M. %A Capone,T. %A Hansen,D. L %A Shneiderman, Ben %K Computer science %K computer science education %K data visualisation %K Data visualization %K Educational institutions %K graph drawing %K graph layout algorithm %K Information services %K Information Visualization %K Internet %K Libraries %K Microsoft Excel open-source template %K MILC %K multi-dimensional in-depth long-term case studies %K Netviz Nirvana %K NodeXL %K Open source software %K Programming profession %K SNA %K social network analysis %K Social network services %K social networking (online) %K spreadsheet programs %K structural relationship %K teaching %K visual analytics %K visualization tool %K Web sites %X Social Network Analysis (SNA) has evolved as a popular, standard method for modeling meaningful, often hidden structural relationships in communities. Existing SNA tools often involve extensive pre-processing or intensive programming skills that can challenge practitioners and students alike. NodeXL, an open-source template for Microsoft Excel, integrates a library of common network metrics and graph layout algorithms within the familiar spreadsheet format, offering a potentially low-barrier-to-entry framework for teaching and learning SNA. We present the preliminary findings of 2 user studies of 21 graduate students who engaged in SNA using NodeXL. The majority of students, while information professionals, had little technical background or experience with SNA techniques. Six of the participants had more technical backgrounds and were chosen specifically for their experience with graph drawing and information visualization. Our primary objectives were (1) to evaluate NodeXL as an SNA tool for a broad base of users and (2) to explore methods for teaching SNA. Our complementary dual case-study format demonstrates the usability of NodeXL for a diverse set of users, and significantly, the power of a tightly integrated metrics/visualization tool to spark insight and facilitate sense-making for students of SNA. %B International Conference on Computational Science and Engineering, 2009. CSE '09 %I IEEE %V 4 %P 332 - 339 %8 2009/08/29/31 %@ 978-1-4244-5334-4 %G eng %R 10.1109/CSE.2009.120 %0 Conference Paper %B IEEE 25th International Conference on Data Engineering, 2009. ICDE '09 %D 2009 %T Minimizing Communication Cost in Distributed Multi-query Processing %A Li,Jian %A Deshpande, Amol %A Khuller, Samir %K Approximation algorithms %K Communication networks %K Computer science %K Cost function %K Data engineering %K distributed communication network %K distributed databases %K distributed multi-query processing %K grid computing %K Large-scale systems %K NP-hard %K optimisation %K Polynomials %K Publish-subscribe %K publish-subscribe systems %K Query optimization %K Query processing %K sensor networks %K Steiner tree problem %K Tree graphs %K trees (mathematics) %X Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the area of distributed query processing and optimization. In this paper we address a general, distributed multi-query processing problem motivated by the need to minimize the communication cost in these environments. Specifically we address the problem of optimally sharing data movement across the communication edges in a distributed communication network given a set of overlapping queries and query plans for them (specifying the operations to be executed). Most of the problem variations of our general problem can be shown to be NP-Hard by a reduction from the Steiner tree problem. However, we show that the problem can be solved optimally if the communication network is a tree, and present a novel algorithm for finding an optimal data movement plan. For general communication networks, we present efficient approximation algorithms for several variations of the problem. Finally, we present an experimental study over synthetic datasets showing both the need for exploiting the sharing of data movement and the effectiveness of our algorithms at finding such plans. %B IEEE 25th International Conference on Data Engineering, 2009. ICDE '09 %I IEEE %P 772 - 783 %8 2009/04/29/March %@ 978-1-4244-3422-0 %G eng %R 10.1109/ICDE.2009.85 %0 Book Section %B Programming Multi-Agent Systems %D 2009 %T Planning for Interactions among Autonomous Agents %A Au,Tsz-Chiu %A Kuter,Ugur %A Nau, Dana S. %E Hindriks,Koen %E Pokahr,Alexander %E Sardina,Sebastian %K Computer science %X AI planning research has traditionally focused on offline pl- anning for static single-agent environments. In environments where an agent needs to plan its interactions with other autonomous agents, planning is much more complicated, because the actions of the other agents can induce a combinatorial explosion in the number of contingencies that the planner will need to consider. This paper discusses several ways to alleviate the combinatorial explosion, and illustrates their use in several different kinds of multi-agent planning domains. %B Programming Multi-Agent Systems %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 5442 %P 1 - 23 %8 2009/// %@ 978-3-642-03277-6 %G eng %U http://www.springerlink.com/content/j258015ux2p38383/abstract/ %0 Book Section %B Theory of Cryptography %D 2009 %T Predicate Privacy in Encryption Systems %A Shen, Emily %A Elaine Shi %A Waters,Brent %E Reingold, Omer %K Computer science %X Predicate encryption is a new encryption paradigm which gives a master secret key owner fine-grained control over access to encrypted data. The master secret key owner can generate secret key tokens corresponding to predicates. An encryption of data x can be evaluated using a secret token corresponding to a predicate f ; the user learns whether the data satisfies the predicate, i.e., whether f ( x ) = 1. Prior work on public-key predicate encryption has focused on the notion of data or plaintext privacy, the property that ciphertexts reveal no information about the encrypted data to an attacker other than what is inherently revealed by the tokens the attacker possesses. In this paper, we consider a new notion called predicate privacy , the property that tokens reveal no information about the encoded query predicate. Predicate privacy is inherently impossible to achieve in the public-key setting and has therefore received little attention in prior work. In this work, we consider predicate encryption in the symmetric-key setting and present a symmetric-key predicate encryption scheme which supports inner product queries. We prove that our scheme achieves both plaintext privacy and predicate privacy. %B Theory of Cryptography %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 5444 %P 457 - 473 %8 2009 %@ 978-3-642-00456-8 %G eng %U http://www.springerlink.com/content/1717x5445k4718rp/abstract/ %0 Journal Article %J International Journal on Digital Libraries %D 2009 %T Techniques to audit and certify the long-term integrity of digital archives %A Song,Sangchul %A JaJa, Joseph F. %K Computer science %X A fundamental requirement for a digital archive is to set up mechanisms that will ensure the authenticity of its holdings in the long term. In this article, we develop a new methodology to address the long-term integrity of digital archives using rigorous cryptographic techniques. Our approach involves the generation of a small-size integrity token for each object, some cryptographic summary information, and a framework that enables cost-effective regular and periodic auditing of the archive’s holdings depending on the policy set by the archive. Our scheme is very general, architecture and platform independent, and can detect with high probability any alteration to an object, including malicious alterations introduced by the archive or by an external intruder. The scheme can be shown to be mathematically correct as long as a small amount of cryptographic information, in the order of 100 KB/year, can be kept intact. Using this approach, a prototype system called ACE (Auditing Control Environment) has been built and tested in an operational large scale archiving environment. %B International Journal on Digital Libraries %V 10 %P 123 - 131 %8 2009/// %@ 1432-5012 %G eng %U http://www.springerlink.com/content/y52815g805h96334/abstract/ %N 2 %R 10.1007/s00799-009-0056-2 %0 Conference Paper %B International Symposium on Collaborative Technologies and Systems, 2009. CTS '09 %D 2009 %T Understanding social computing participation with visual exploration tools %A Shneiderman, Ben %K Application software %K Books %K Collaborative tools %K Computer science %K Data visualization %K Educational institutions %K History %K International collaboration %K Social network services %K Sociotechnical systems %X The rapid growth of socio-technical systems, social media and social networking websites has raised the importance of understanding the determinants of their success. The pressure to understand success is increased by the shift from playful discretionary applications to mission critical applications in government, business, and civic settings. These include homeland defense, energy sustainability, environmental conservation, disaster response, and community safety. Information visualization tools and statistical methods can both be helpful, but their utility grows when they are well-integrated. This talk will demonstrate novel tools for network evolution and offer a framework for thinking about motivating technology-mediated social participation. %B International Symposium on Collaborative Technologies and Systems, 2009. CTS '09 %I IEEE %P xi-xii - xi-xii %8 2009/05/18/22 %@ 978-1-4244-4584-4 %G eng %R 10.1109/CTS.2009.5067426 %0 Conference Paper %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %D 2008 %T Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints %A Chafekar,D. %A Kumart,V. S.A %A Marathe,M. V %A Parthasarathy,S. %A Srinivasan, Aravind %K Algorithm design and analysis %K approximation algorithm %K Approximation algorithms %K approximation theory %K Computer networks %K Computer science %K graph theory %K graph-based model %K Interference constraints %K polynomial time algorithm %K Propagation losses %K Protocols %K radio networks %K radiofrequency interference %K signal to interference plus noise ratio %K Signal to noise ratio %K Throughput %K wireless interference %K wireless network %K Wireless networks %X A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting. %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %I IEEE %P 1166 - 1174 %8 2008/04/13/18 %@ 978-1-4244-2025-4 %G eng %R 10.1109/INFOCOM.2008.172 %0 Conference Paper %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %D 2008 %T Capacity of Asynchronous Random-Access Scheduling in Wireless Networks %A Chafekar,D. %A Levin,D. %A Kumar,V. S.A %A Marathe,M. V %A Parthasarathy,S. %A Srinivasan, Aravind %K asynchronous random-access scheduling %K channel access probability %K Computer networks %K Computer science %K Educational institutions %K Interference %K Optimal scheduling %K Peer to peer computing %K probability %K Processor scheduling %K radio link %K radio links %K radio networks %K Routing %K scheduling %K Throughput %K throughput capacity %K wireless channels %K Wireless networks %X We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models. %B IEEE INFOCOM 2008. The 27th Conference on Computer Communications %I IEEE %P 1148 - 1156 %8 2008/04/13/18 %@ 978-1-4244-2025-4 %G eng %R 10.1109/INFOCOM.2008.170 %0 Journal Article %J Intelligent Systems, IEEE %D 2008 %T Computational Cultural Dynamics %A Nau, Dana S. %A Wilkenfeld,J. %K anthropology %K behavioral science %K behavioural sciences computing %K computational cultural dynamics %K computational linguistics %K Computer science %K game theory %K journalism %K operations research %K political science %K Psychology %K social sciences %K social sciences computing %K sociology %K statistical modeling %X Computational cultural dynamics blends the behavioral and social sciences - fields such as political science, psychology, journalism, anthropology, and sociology - with technological fields such as computer science, computational linguistics, game theory, statistical modeling, and operations research. %B Intelligent Systems, IEEE %V 23 %P 18 - 19 %8 2008/08//july %@ 1541-1672 %G eng %N 4 %R 10.1109/MIS.2008.61 %0 Book Section %B Automata, Languages and Programming %D 2008 %T Delegating Capabilities in Predicate Encryption Systems %A Elaine Shi %A Waters,Brent %E Aceto,Luca %E Damgård,Ivan %E Goldberg,Leslie %E Halldórsson,Magnús %E Ingólfsdóttir,Anna %E Walukiewicz,Igor %K Computer science %X In predicate encryption systems, given a capability, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden. We consider the role of delegation in such predicate encryption systems. Suppose Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing the decryption of a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation, and give an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite order bilinear groups. %B Automata, Languages and Programming %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 5126 %P 560 - 578 %8 2008 %@ 978-3-540-70582-6 %G eng %U http://www.springerlink.com/content/w320422h15050004/abstract/ %0 Book Section %B Computer Safety, Reliability, and Security %D 2008 %T Finding Corrupted Computers Using Imperfect Intrusion Prevention System Event Data %A Chrun,Danielle %A Michel Cukier %A Sneeringer,Gerry %E Harrison,Michael %E Sujan,Mark-Alexander %K Computer science %X With the increase of attacks on the Internet, a primary concern for organizations is how to protect their network. The objectives of a security team are 1) to prevent external attackers from launching successful attacks against organization computers that could become compromised, 2) to ensure that organization computers are not vulnerable (e.g., fully patched) so that in either case the organization computers do not start launching attacks. The security team can monitor and block malicious activity by using devices such as intrusion prevention systems. However, in large organizations, such monitoring devices could record a high number of events. The contributions of this paper are 1) to introduce a method that ranks potentially corrupted computers based on imperfect intrusion prevention system event data, and 2) to evaluate the method based on empirical data collected at a large organization of about 40,000 computers. The evaluation is based on the judgment of a security expert of which computers were indeed corrupted. On the one hand, we studied how many computers classified as of high concern or of concern were indeed corrupted (i.e., true positives). On the other hand, we analyzed how many computers classified as of lower concern were in fact corrupted (i.e., false negatives). %B Computer Safety, Reliability, and Security %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 5219 %P 221 - 234 %8 2008/// %@ 978-3-540-87697-7 %G eng %U http://www.springerlink.com/content/4767u3017r613822/abstract/ %0 Journal Article %J IEEE/ACM Transactions on Computational Biology and Bioinformatics %D 2008 %T Guest Editors' Introduction to the Special Section on Algorithms in Bioinformatics %A Giancarlo,Raffaele %A Hannenhalli, Sridhar %K Abstracts %K Algorithm design and analysis %K Bioinformatics %K Biological system modeling %K biology computing %K Computational Biology %K Computational modeling %K Computer science %K Genomics %K sequences %B IEEE/ACM Transactions on Computational Biology and Bioinformatics %V 5 %P 482 - 483 %8 2008/12//Oct %@ 1545-5963 %G eng %N 4 %R 10.1109/TCBB.2008.116 %0 Journal Article %J Annals of Mathematics and Artificial Intelligence %D 2007 %T Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10^30,000 worlds %A Khuller, Samir %A Martinez,M. %A Nau, Dana S. %A Sliva,Amy %A Simari,Gerardo %A Subrahmanian,V. %K Computer science %X The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called and to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a “binary” algorithm that applies a binary search style heuristic in conjunction with the Naive, and algorithms to quickly find worlds that may not be “most probable.” We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of are very accurate and also very fast: more than 10 30,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups. %B Annals of Mathematics and Artificial Intelligence %V 51 %P 295 - 331 %8 2007/// %@ 1012-2443 %G eng %U http://www.springerlink.com/content/t70g873h613273pu/abstract/ %N 2 %R 10.1007/s10472-008-9089-2 %0 Journal Article %J IEEE Journal on Selected Areas in Communications %D 2007 %T Efficient lookup on unstructured topologies %A Morselli,R. %A Bhattacharjee, Bobby %A Marsh,M.A. %A Srinivasan, Aravind %K Computer science %K DHT %K distributed algorithms %K Distributed computing %K distributed hash table %K Least squares approximation %K LMS %K local minima search %K lookup protocol %K Network topology %K node failures %K Peer to peer computing %K Performance analysis %K Protocols %K replication strategy %K Resilience %K Robustness %K table lookup %K telecommunication network topology %K unstructured network topology %X We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size %B IEEE Journal on Selected Areas in Communications %V 25 %P 62 - 72 %8 2007/01// %@ 0733-8716 %G eng %N 1 %R 10.1109/JSAC.2007.07007 %0 Book Section %B Scalable Uncertainty Management %D 2007 %T Finding Most Probable Worlds of Probabilistic Logic Programs %A Khuller, Samir %A Martinez,Vanina %A Nau, Dana S. %A Simari,Gerardo %A Sliva,Amy %A Subrahmanian,V. %E Prade,Henri %E Subrahmanian,V. %K Computer science %X Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a possible world that is most probable. Our first result shows that the problem of computing such ”maximally probable worlds” (MPW) is intractable. We subsequently show that we can often greatly reduce the size of the linear program used in past work (by Ng and Subrahmanian) and yet solve the problem exactly. However, the intractability results still make computational efficiency quite impossible. We therefore also develop several heuristics to solve the MPW problem and report extensive experimental results on the accuracy and efficiency of such heuristics. %B Scalable Uncertainty Management %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 4772 %P 45 - 59 %8 2007/// %@ 978-3-540-75407-7 %G eng %U http://www.springerlink.com/content/e4463p4rv4k01u93/abstract/ %0 Conference Paper %B Seventh IEEE International Conference on Data Mining Workshops, 2007. ICDM Workshops 2007 %D 2007 %T Representing Tuple and Attribute Uncertainty in Probabilistic Databases %A Sen,P. %A Deshpande, Amol %A Getoor, Lise %K attribute uncertainty %K Computer science %K Conferences %K correlation structures %K data mining %K Data models %K database management systems %K Educational institutions %K inference mechanisms %K noisy data sources %K probabilistic database %K probabilistic inference %K Probability distribution %K Query processing %K Relational databases %K Sensor phenomena and characterization %K tuple representation %K Uncertainty %K uncertainty handling %X There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources-sensor data, experimental data, data from uncurated sources, and many others. There is a growing need to be able to flexibly represent the uncertainties in the data, and to efficiently query the data. Building on existing probabilistic database work, we present a unifying framework which allows a flexible representation of correlated tuple and attribute level uncertainties. An important capability of our representation is the ability to represent shared correlation structures in the data. We provide motivating examples to illustrate when such shared correlation structures are likely to exist. Representing shared correlations structures allows the use of sophisticated inference techniques based on lifted probabilistic inference that, in turn, allows us to achieve significant speedups while computing probabilities for results of user-submitted queries. %B Seventh IEEE International Conference on Data Mining Workshops, 2007. ICDM Workshops 2007 %I IEEE %P 507 - 512 %8 2007/10/28/31 %@ 978-0-7695-3019-2 %G eng %R 10.1109/ICDMW.2007.11 %0 Journal Article %J Virtual Reality %D 2007 %T Towards the development of a virtual environment-based training system for mechanical assembly operations %A Brough,John %A Schwartz,Maxim %A Gupta, Satyandra K. %A Anand,Davinder %A Kavetsky,Robert %A Pettersen,Ralph %K Computer science %X In this paper, we discuss the development of Virtual Training Studio (VTS), a virtual environment-based training system that allows training supervisors to create training instructions and allows trainees to learn assembly operations in a virtual environment. Our system is mainly focused on the cognitive side of training so that trainees can learn to recognize parts, remember assembly sequences, and correctly orient the parts during assembly operations. Our system enables users to train using the following three training modes: (1) Interactive Simulation, (2) 3D Animation, and (3) Video. Implementing these training modes required us to develop several new system features. This paper presents an overview of the VTS system and describes a few main features of the system. We also report user test results that show how people train using our system. The user test results indicate that the system is able to support a wide variety of training preferences and works well to support training for assembly operations. %B Virtual Reality %V 11 %P 189 - 206 %8 2007/// %@ 1359-4338 %G eng %U http://www.springerlink.com/content/g7760422m13l83x1/abstract/ %N 4 %R 10.1007/s10055-007-0076-4 %0 Book Section %B Geometric Modeling and Processing - GMP 2006 %D 2006 %T Finding Mold-Piece Regions Using Computer Graphics Hardware %A Priyadarshi,Alok %A Gupta, Satyandra K. %E Kim,Myung-Soo %E Shimada,Kenji %K Computer science %X An important step in the mold design process that ensures disassembly of mold pieces consists of identifying various regions on the part that will be formed by different mold pieces. This paper presents an efficient and robust algorithm to find and highlight the mold-piece regions on a part. The algorithm can be executed on current-generation computer graphics hardware. The complexity of the algorithm solely depends on the time to render the given part. By using a system that can quickly find various mold-piece regions on a part, designers can easily optimize the part and mold design and if needed make appropriate corrections upfront, streamlining the subsequent design steps. %B Geometric Modeling and Processing - GMP 2006 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 4077 %P 655 - 662 %8 2006/// %@ 978-3-540-36711-6 %G eng %U http://www.springerlink.com/content/t8t3588924263p12/abstract/ %0 Conference Paper %B 2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings %D 2006 %T Frequency Independent Flexible Spherical Beamforming Via Rbf Fitting %A Yerukhimovich,A. %A Duraiswami, Ramani %A Gumerov, Nail A. %A Zotkin,Dmitry N %K acoustic signal processing %K array signal processing %K band-limited radial basis functions %K Computer science %K Educational institutions %K Eigenvalues and eigenfunctions %K Equations %K Frequency %K frequency independent beamformer weights %K frequency independent flexible spherical beamforming %K microphone arrays %K Nails %K Position measurement %K RBF fitting %K Robustness %K sound analysis %K spherical array data %K spherical microphone array %X We describe a new method for sound analysis using a spherical microphone array without the use of quadrature over the sphere. Quadrature based solutions are very sensitive to the placement of microphones on the sphere, needing measurements to be made at exactly the quadrature positions. We propose to use fitting with band-limited radial basis functions (RBFs) rather than quadrature. Our approach results in frequency independent beamformer weights for flexibly placed microphone locations. Results are demonstrated using both synthetic and real spherical array data %B 2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings %I IEEE %V 5 %P V-V - V-V %8 2006/05// %@ 1-4244-0469-X %G eng %R 10.1109/ICASSP.2006.1661208 %0 Journal Article %J IEEE Multimedia %D 2006 %T Hierarchical Layouts for Photo Libraries %A Kustanowitz,J. %A Shneiderman, Ben %K annotated digital photo collection %K auto-layout technique %K bi-level hierarchies %K Computer science %K data visualisation %K digital libraries %K document image processing %K Information Visualization %K interactive algorithms %K interactive displays %K Libraries %K Lifting equipment %K Organization Charts %K photo collections %K photo layouts %K photo library %K Photography %K quantum content %K Silver %K Springs %K User interfaces %K Web pages %X We use an annotated digital photo collection to demonstrate a two-level auto-layout technique consisting of a central primary region with secondary regions surrounding it. Because the object sizes within regions can only be changed in discrete units, we refer to them as quantum content. Our real-time algorithms enable a compelling interactive display as users resize the canvas, or move and resize the primary region %B IEEE Multimedia %V 13 %P 62 - 72 %8 2006/12//Oct %@ 1070-986X %G eng %N 4 %R 10.1109/MMUL.2006.83 %0 Conference Paper %B 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition %D 2006 %T A Projective Invariant for Textures %A Yong Xu %A Hui Ji %A Fermüller, Cornelia %K Computer science %K Computer vision %K Educational institutions %K Fractals %K Geometry %K Image texture %K Level set %K lighting %K Robustness %K Surface texture %X Image texture analysis has received a lot of attention in the past years. Researchers have developed many texture signatures based on texture measurements, for the purpose of uniquely characterizing the texture. Existing texture signatures, in general, are not invariant to 3D transforms such as view-point changes and non-rigid deformations of the texture surface, which is a serious limitation for many applications. In this paper, we introduce a new texture signature, called the multifractal spectrum (MFS). It provides an efficient framework combining global spatial invariance and local robust measurements. The MFS is invariant under the bi-Lipschitz map, which includes view-point changes and non-rigid deformations of the texture surface, as well as local affine illumination changes. Experiments demonstrate that the MFS captures the essential structure of textures with quite low dimension. %B 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition %I IEEE %V 2 %P 1932 - 1939 %8 2006/// %@ 0-7695-2597-0 %G eng %R 10.1109/CVPR.2006.38 %0 Journal Article %J IEEE/ACM Transactions on Networking %D 2006 %T Resilient multicast using overlays %A Banerjee,S. %A Lee,Seungjoon %A Bhattacharjee, Bobby %A Srinivasan, Aravind %K application-layer multicast protocols %K Computer science %K Data communication %K Delay %K Internet %K Internet-like topologies %K IP networks %K loss recovery technique %K Multicast %K multicast data recovery scheme %K Multicast protocols %K Network topology %K NETWORKS %K overlays %K Performance loss %K probabilistic forwarding %K probabilistic resilient multicast %K Protocols %K Resilience %K Streaming media %K telecommunication network topology %K Terminology %X We introduce Probabilistic Resilient Multicast (PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols especially when there are high packet losses and host failures. Through detailed analysis in this paper, we show that this loss recovery technique has efficient scaling properties-the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10 000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (>97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1%-5%) and high topology change rates (5 changes per second) while incurring very low overheads (<5%). %B IEEE/ACM Transactions on Networking %V 14 %P 237 - 248 %8 2006/04// %@ 1063-6692 %G eng %N 2 %R 10.1109/TNET.2006.872579 %0 Conference Paper %B 2006 6th IEEE-RAS International Conference on Humanoid Robots %D 2006 %T A Sensory-Motor Language for Human Activity Understanding %A Guerra-Filho,G. %A Aloimonos, J. %K Actuators %K associative learning %K atomic segments %K computational linguistics %K Computer science %K Computer vision %K Educational institutions %K grammars %K human activity language %K human activity understanding %K human movement syntax %K Humanoid robots %K HUMANS %K joint angles %K kinetemes %K kinetological system %K Laboratories %K learning (artificial intelligence) %K List key index terms here %K Morphology %K motor information %K No mare than 5 %K parallel learning %K Reproducibility of results %K Robot kinematics %K Robot programming %K robot vision %K sensory-motor language %K sequential language learning %K symbolic nonarbitrary representation %K visual information %X We have empirically discovered that the space of human actions has a linguistic framework. This is a sensory-motor space consisting of the evolution of the joint angles of the human body in movement. The space of human activity has its own phonemes, morphemes, and sentences. We present a human activity language (HAL) for symbolic non-arbitrary representation of visual and motor information. In phonology, we define atomic segments (kinetemes) that are used to compose human activity. We introduce the concept of a kinetological system and propose five basic properties for such a system: compactness, view-invariance, reproducibility, selectivity, and reconstructivity. In morphology, we extend sequential language learning to incorporate associative learning with our parallel learning approach. Parallel learning is effective in identifying the kinetemes and active joints in a particular action. In syntax, we suggest four lexical categories for our human activity language (noun, verb, adjective, and adverb). These categories are combined into sentences through syntax for human movement %B 2006 6th IEEE-RAS International Conference on Humanoid Robots %I IEEE %P 69 - 75 %8 2006/12/04/6 %@ 1-4244-0200-X %G eng %R 10.1109/ICHR.2006.321365 %0 Book Section %B Geometric Modeling and Processing - GMP 2006 %D 2006 %T A Step Towards Automated Design of Side Actions in Injection Molding of Complex Parts %A Banerjee,Ashis %A Gupta, Satyandra K. %E Kim,Myung-Soo %E Shimada,Kenji %K Computer science %X Side actions contribute to mold cost by resulting in an additional manufacturing and assembly cost as well as by increasing the molding cycle time. Therefore, generating shapes of side actions requires solving a complex geometric optimization problem. Different objective functions may be needed depending upon different molding scenarios (e.g., prototyping versus large production runs). Manually designing side actions is a challenging task and requires considerable expertise. Automated design of side actions will significantly reduce mold design lead times. This paper describes algorithms for generating shapes of side actions to minimize a customizable molding cost function. %B Geometric Modeling and Processing - GMP 2006 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 4077 %P 500 - 513 %8 2006/// %@ 978-3-540-36711-6 %G eng %U http://www.springerlink.com/content/w7q3212607500635/abstract/ %0 Book %D 2006 %T Unconstrained face recognition %A Zhou,S. Kevin %A Chellapa, Rama %A Zhao,Wenyi %K Computer science %K Computer vision %K Computers / Computer Graphics %K Computers / Computer Science %K Computers / Computer Vision & Pattern Recognition %K Computers / General %K Computers / Image Processing %K Computers / Information Technology %K Computers / Information Theory %K Computers / Interactive & Multimedia %K Computers / Security / Cryptography %K Computers / User Interfaces %K Data encryption (Computer science) %K Data structures (Computer science) %K Electronic books %K Human face recognition (Computer science) %K IMAGE PROCESSING %K Image processing - Digital techniques %K multimedia systems %K Optical pattern recognition %K Science / Life Sciences / Biology %X Face recognition has been actively studied over the past decade and continues to be a big research challenge. Just recently, researchers have begun to investigate face recognition under unconstrained conditions. Unconstrained Face Recognition provides a comprehensive review of this biometric, especially face recognition from video, assembling a collection of novel approaches that are able to recognize human faces under various unconstrained situations. The underlying basis of these approaches is that, unlike conventional face recognition algorithms, they exploit the inherent characteristics of the unconstrained situation and thus improve the recognition performance when compared with conventional algorithms.Unconstrained Face Recognition is structured to meet the needs of a professional audience of researchers and practitioners in industry. This volume is also suitable for advanced-level students in computer science. %I Springer Science & Business %8 2006/// %@ 9780387264073 %G eng %0 Conference Paper %B Visual Analytics Science And Technology, 2006 IEEE Symposium On %D 2006 %T A Visual Interface for Multivariate Temporal Data: Finding Patterns of Events across Multiple Histories %A Fails,J. A %A Karlson,A. %A Shahamat,L. %A Shneiderman, Ben %K ball-and-chain visualization %K Chromium %K Computer science %K Data analysis %K data visualisation %K Data visualization %K Database languages %K event pattern discovery %K Graphical user interfaces %K History %K Information Visualization %K Medical treatment %K multivariate temporal data %K Pattern analysis %K pattern recognition %K PatternFinder integrated interface %K Query processing %K query visualization %K result-set visualization %K Spatial databases %K tabular visualization %K temporal pattern discovery %K temporal pattern searching %K Temporal query %K user interface %K User interfaces %K visual databases %K visual interface %X Finding patterns of events over time is important in searching patient histories, Web logs, news stories, and criminal activities. This paper presents PatternFinder, an integrated interface for query and result-set visualization for search and discovery of temporal patterns within multivariate and categorical data sets. We define temporal patterns as sequences of events with inter-event time spans. PatternFinder allows users to specify the attributes of events and time spans to produce powerful pattern queries that are difficult to express with other formalisms. We characterize the range of queries PatternFinder supports as users vary the specificity at which events and time spans are defined. Pattern Finder's query capabilities together with coupled ball-and-chain and tabular visualizations enable users to effectively query, explore and analyze event patterns both within and across data entities (e.g. patient histories, terrorist groups, Web logs, etc.) %B Visual Analytics Science And Technology, 2006 IEEE Symposium On %I IEEE %P 167 - 174 %8 2006/11/31/Oct. %@ 1-4244-0591-2 %G eng %R 10.1109/VAST.2006.261421 %0 Journal Article %J IEEE Transactions on Circuits and Systems for Video Technology %D 2005 %T Class-based access control for distributed video-on-demand systems %A Mundur, Padma %A Sood,A. K %A Simon,R. %K Access control %K Admission control %K Analytical models %K blocking performance %K class-based access control %K Computational modeling %K Computer architecture %K Computer science %K Distributed control %K Distributed video-on-demand (VoD) system %K distributed video-on-demand system %K multimedia systems %K multirate service model %K Performance analysis %K QoS %K quality of service %K request handling policy %K resource allocation %K resource capacity %K telecommunication congestion control %K threshold-based admission control %K video on demand %X The focus of this paper is the analysis of threshold-based admission control policies for distributed video-on-demand (VoD) systems. Traditionally, admission control methods control access to a resource based on the resource capacity. We have extended that concept to include the significance of an arriving request to the VoD system by enforcing additional threshold restrictions in the admission control process on request classes deemed less significant. We present an analytical model for computing blocking performance of the VoD system under threshold-based admission control. Extending the same methodology to a distributed VoD architecture we show through simulation that the threshold performance conforms to the analytical model. We also show that threshold-based analysis can work in conjunction with other request handling policies and are useful for manipulating the VoD performance since we are able to distinguish between different request classes based on their merit. Enforcing threshold restrictions with the option of downgrading blocked requests in a multirate service environment results in improved performance at the same time providing different levels of quality of service (QoS). In fact, we show that the downgrade option combined with threshold restrictions is a powerful tool for manipulating an incoming request mix over which we have no control into a workload that the VoD system can handle. %B IEEE Transactions on Circuits and Systems for Video Technology %V 15 %P 844 - 853 %8 2005/07// %@ 1051-8215 %G eng %N 7 %R 10.1109/TCSVT.2005.848351 %0 Conference Paper %B Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International %D 2005 %T Comparing the Performance of High-Level Middleware Systems in Shared and Distributed Memory Parallel Environments %A Kim,Jik-Soo %A Andrade,H. %A Sussman, Alan %K Application software %K Computer science %K Computer vision %K Data analysis %K Distributed computing %K distributed computing environment %K distributed memory parallel environment %K distributed shared memory systems %K Educational institutions %K high-level middleware system %K I/O-intensive data analysis application %K Libraries %K Middleware %K parallel computing environment %K parallel library support %K parallel memories %K programming language %K programming languages %K Runtime environment %K shared memory parallel environment %K Writing %X The utilization of toolkits for writing parallel and/or distributed applications has been shown to greatly enhance developer's productivity. Such an approach hides many of the complexities associated with writing these applications, rather than relying solely on programming language aids and parallel library support, such as MPI or PVM. In this work, we evaluate three different middleware systems that have been used to implement a computation and I/O-intensive data analysis application from the domain of computer vision. This study shows the benefits and overheads associated with each of the middleware systems, in different homogeneous computational environments and with different workloads. Our results lead the way toward being able to make better decisions for tuning the application environment, for selecting the appropriate middleware, and also for designing more powerful middleware systems to efficiently build and run highly complex applications in both parallel and distributed computing environments. %B Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International %I IEEE %P 30 - 30 %8 2005/04// %@ 0-7695-2312-9 %G eng %R 10.1109/IPDPS.2005.144 %0 Conference Paper %B Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International %D 2005 %T High Performance Communication between Parallel Programs %A Jae-Yong Lee %A Sussman, Alan %K Adaptive arrays %K Analytical models %K Chaotic communication %K Computational modeling %K Computer science %K Data analysis %K data distribution %K Educational institutions %K high performance communication %K image data analysis %K image resolution %K inter-program communication patterns %K InterComm %K Libraries %K Message passing %K parallel languages %K parallel libraries %K parallel programming %K parallel programs %K performance evaluation %K Wind %X We present algorithms for high performance communication between message-passing parallel programs, and evaluate the algorithms as implemented in InterComm. InterComm is a framework to couple parallel programs in the presence of complex data distributions within a coupled application. Multiple parallel libraries and languages may be used in the different programs of a single coupled application. The ability to couple such programs is required in many emerging application areas, such as complex simulations that model physical phenomena at multiple scales and resolutions, and image data analysis applications. We describe the new algorithms we have developed for computing inter-program communication patterns. We present experimental results showing the performance of various algorithmic tradeoffs, and also compare performance against an earlier system. %B Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International %I IEEE %P 177b- 177b - 177b- 177b %8 2005/04// %@ 0-7695-2312-9 %G eng %R 10.1109/IPDPS.2005.243 %0 Conference Paper %B Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, 2005. JCDL '05 %D 2005 %T Meaningful presentations of photo libraries: rationale and applications of bi-level radial quantum layouts %A Kustanowitz,J. %A Shneiderman, Ben %K 1024 pixel %K 1200 pixel %K 1280 pixel %K 1310720 pixel %K 1600 pixel %K 1920000 pixel %K Application software %K bi-level radial quantum layouts %K Computer displays %K Computer science %K digital libraries %K Educational institutions %K Image retrieval %K Layout %K layout generation %K Lifting equipment %K linear strips %K Permission %K photo layouts %K photo library searching %K photo management %K Photography %K Quantum computing %K software libraries %K Strips %K two-dimensional grid %K User interfaces %K visual databases %K visual presentation %K zoomable three dimensional arrangements %X Searching photo libraries can be made more satisfying and successful if search results are presented in a way that allows users to gain an overview of the photo categories. Since photo layouts on computer displays are the primary way that users get an overview, we propose a novel approach to show more photos in meaningful groupings. Photo layouts can be linear strips, or zoomable three dimensional arrangements, but the most common form is the two-dimensional grid. This paper introduces a novel bi-level hierarchical layout with motivating examples. In a bilevel hierarchy, one region is designated for primary content - an image, text, or combination. Adjacent to that region, groups of photos are placed radially in an ordered fashion, such that the relationship of the single primary region to its many secondary regions is apparent. A compelling aspect is the interactive experience in which the layout is dynamically resized, allowing users to rapidly, incrementally, and reversibly alter the dimensions and content. It can accommodate hundreds of photos in dozens of regions, can be customized in a corner or center layout, and can scale from an element on a web page to a large poster size. On typical displays (1024 times 1280 or 1200 times 1600 pixels), bi-level radial quantum layouts can conveniently accommodate 2-20 regions with tens or hundreds of photos per region %B Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, 2005. JCDL '05 %I IEEE %P 188 - 196 %8 2005/06/07/11 %@ 1-58113-876-8 %G eng %R 10.1145/1065385.1065431 %0 Conference Paper %B Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005. ICRA 2005 %D 2005 %T Robust Contrast Invariant Stereo Correspondence %A Ogale, A. S %A Aloimonos, J. %K Apertures %K Calibration %K CAMERAS %K Computer science %K contrast invariance %K diffusion %K Educational institutions %K Frequency %K gabor %K Hardware %K occlusions %K Robot vision systems %K Robotics and automation %K Robustness %K stereo %X A stereo pair of cameras attached to a robot will inevitably yield images with different contrast. Even if we assume that the camera hardware is identical, due to slightly different points of view, the amount of light entering the two cameras is also different, causing dynamically adjusted internal parameters such as aperture, exposure and gain to be different. Due to the difficulty of obtaining and maintaining precise intensity or color calibration between the two cameras, contrast invariance becomes an extremely desirable property of stereo correspondence algorithms. The problem of achieving point correspondence between a stereo pair of images is often addressed by using the intensity or color differences as a local matching metric, which is sensitive to contrast changes. We present an algorithm for contrast invariant stereo matching which relies on multiple spatial frequency channels for local matching. A fast global framework uses the local matching to compute the correspondences and find the occlusions. We demonstrate that the use of multiple frequency channels allows the algorithm to yield good results even in the presence of significant amounts of noise. %B Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005. ICRA 2005 %I IEEE %P 819 - 824 %8 2005/04/18/22 %@ 0-7803-8914-X %G eng %R 10.1109/ROBOT.2005.1570218 %0 Conference Paper %B IEEE International Symposium on Cluster Computing and the Grid, 2005. CCGrid 2005 %D 2005 %T Spatial indexing of distributed multidimensional datasets %A Nam,B. %A Sussman, Alan %K centralized global index algorithm %K centralized index server %K Computer science %K database indexing %K distributed databases %K distributed multidimensional dataset %K Educational institutions %K File servers %K Indexing %K Large-scale systems %K Multidimensional systems %K Network servers %K replication protocol %K replication techniques %K scalability %K Sensor systems %K spatial data structures %K spatial indexing %K two-level hierarchical index algorithm %K wide area networks %X While declustering methods for distributed multidimensional indexing of large datasets have been researched widely in the past, replication techniques for multidimensional indexes have not been investigated deeply. In general, a centralized index server may become the performance bottleneck in a wide area network rather than the data servers, since the index is likely to be accessed more often than any of the datasets in the servers. In this paper, we present two different multidimensional indexing algorithms for a distributed environment - a centralized global index and a two-level hierarchical index. Our experimental results show that the centralized scheme does not scale well for either insertion or searching the index. In order to improve the scalability of the index server, we have employed a replication protocol for both the centralized and two-level index schemes that allows some inconsistency between replicas without affecting correctness. Our experiments show that the two-level hierarchical index scheme shows better scalability for both building and searching the index than the non-replicated centralized index, but replication can make the centralized index faster than the two-level hierarchical index for searching in some cases. %B IEEE International Symposium on Cluster Computing and the Grid, 2005. CCGrid 2005 %I IEEE %V 2 %P 743- 750 Vol. 2 - 743- 750 Vol. 2 %8 2005/05/09/12 %@ 0-7803-9074-1 %G eng %R 10.1109/CCGRID.2005.1558637 %0 Conference Paper %B IEEE Symposium on Information Visualization, 2005. INFOVIS 2005 %D 2005 %T Turning information visualization innovations into commercial products: lessons to guide the next success %A Shneiderman, Ben %A Rao,R. %A Andrews,K. %A Ahlberg,C. %A Brodbeck,D. %A Jewitt,T. %A Mackinlay,J. %K Books %K commercial development %K commercial product %K Computer interfaces %K Computer science %K data visualisation %K Data visualization %K Educational institutions %K exploratory data analysis %K information visualization innovation %K information visualization tool %K innovation management %K Laboratories %K Management training %K new technology emergence %K Technological innovation %K technology transfer %K Turning %K User interfaces %X As information visualization matures as an academic research field, commercial spinoffs are proliferating, but success stories are harder to find. This is the normal process of emergence for new technologies, but the panel organizers believe that there are certain strategies that facilitate success. To teach these lessons, we have invited several key figures who are seeking to commercialize information visualization tools. The panelists make short presentations, engage in a moderated discussion, and respond to audience questions. %B IEEE Symposium on Information Visualization, 2005. INFOVIS 2005 %I IEEE %P 241 - 244 %8 2005/10/23/25 %@ 0-7803-9464-X %G eng %R 10.1109/INFVIS.2005.1532153 %0 Book Section %B The Semantic Web – ISWC 2005 %D 2005 %T Web Service Composition with Volatile Information %A Au,Tsz-Chiu %A Kuter,Ugur %A Nau, Dana S. %E Gil,Yolanda %E Motta,Enrico %E Benjamins,V. %E Musen,Mark %K Computer science %X In many Web service composition problems, information may be needed from Web services during the composition process. Existing research on Web service composition (WSC) procedures has generally assumed that this information will not change. We describe two ways to take such WSC procedures and systematically modify them to deal with volatile information. The black-box approach requires no knowledge of the WSC procedure’s internals: it places a wrapper around the WSC procedure to deal with volatile information. The gray-box approach requires partial information of those internals, in order to insert coding to perform certain bookkeeping operations. We show theoretically that both approaches work correctly. We present experimental results showing that the WSC procedures produced by the gray-box approach can run much faster than the ones produced by the black-box approach. %B The Semantic Web – ISWC 2005 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 3729 %P 52 - 66 %8 2005/// %@ 978-3-540-29754-3 %G eng %U http://www.springerlink.com/content/y105x8464k54l760/abstract/ %0 Conference Paper %B Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th %D 2004 %T Achieving packet-level quality of service through scheduling in multirate WLANs %A Yuan Yuan %A Daqing Gu %A Arbaugh, William A. %A Jinyun Zhang %K Analytical models %K channel conditions %K channel errors %K channel temporal fair share %K compensation %K Computer science %K Delay %K error-prone flow compensation %K IEEE 802.11a/b/g physical layer %K multirate wireless fair scheduling %K multirate WLAN %K packet radio networks %K packet-level quality of service %K Physical layer %K Processor scheduling %K QoS %K quality of service %K radio access networks %K Scheduling algorithm %K Throughput %K throughput fairness %K USA Councils %K Wireless LAN %K wireless packet scheduling %K WMFS %X Wireless packet scheduling has been a popular paradigm to achieve packet-level QoS in terms of fairness and throughput in the presence of channel errors. However, the current design does not anticipate the multi-rate capability offered by the IEEE 802.11a/b/g physical layer, thus suffering significant performance degradation in 802.11 WLANs. In this paper, we propose multirate wireless fair scheduling (WMFS). In MWFS, each flow is granted a temporal fair share of the channel, in contrast to the throughput fair share adopted by existing algorithms. Therefore, each flow receives services in proportion to its perceived transmission rate, and high-rate flows are able to opportunistically exploit their good channel conditions and receive more services. MWFS also renovates the compensation model in order to allow for error-prone flows to catch up, thus ensuring fairness for all flows over error-prone channels. We demonstrate the effectiveness of MWFS through both simulations and analysis. Especially, WMFS achieves system throughput 159% of state-of-the-art scheduling algorithms in simulated scenarios. %B Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th %I IEEE %V 4 %P 2730- 2734 Vol. 4 - 2730- 2734 Vol. 4 %8 2004/09/26/29 %@ 0-7803-8521-7 %G eng %R 10.1109/VETECF.2004.1400554 %0 Conference Paper %B 13th IEEE International Symposium on High performance Distributed Computing, 2004. Proceedings %D 2004 %T Automated cluster-based Web service performance tuning %A Chung,I. -H %A Hollingsworth, Jeffrey K %K Active Harmony system %K automated performance tuning %K business %K cluster-based Web service system %K Clustering algorithms %K Computer science %K Educational institutions %K electronic commerce %K Internet %K Middleware %K performance evaluation %K scalability %K Throughput %K Transaction databases %K Web server %K Web services %K workstation clusters %X Active harmony provides a way to automate performance tuning. We apply the Active Harmony system to improve the performance of a cluster-based web service system. The performance improvement cannot easily be achieved by tuning individual components for such a system. The experimental results show that there is no single configuration for the system that performs well for all kinds of workloads. By tuning the parameters, Active Harmony helps the system adapt to different workloads and improve the performance up to 16%. For scalability, we demonstrate how to reduce the time when tuning a large system with many tunable parameters. Finally an algorithm is proposed to automatically adjust the structure of cluster-based web systems, and the system throughput is improved up to 70% using this technique. %B 13th IEEE International Symposium on High performance Distributed Computing, 2004. Proceedings %I IEEE %P 36 - 44 %8 2004/06/04/6 %@ 0-7695-2175-4 %G eng %R 10.1109/HPDC.2004.1323484 %0 Conference Paper %B 2004 IEEE International Conference on Communications %D 2004 %T Automatic video summarization for wireless and mobile environments %A Yong Rao %A Mundur, Padma %A Yesha,Y. %K automatic video summarization %K batch processing %K batch processing (computers) %K Clustering algorithms %K Clustering methods %K clustering scheme %K Computer science %K Delaunay diagram %K graph theory %K Gunshot detection systems %K Image sequences %K mesh generation %K Mobile computing %K mobile radio %K multidimensional point data cluster %K Multidimensional systems %K Multimedia communication %K video clip %K video frame content %K Video sequences %K video signal processing %K wireless mobile environment %X In this paper, we propose a novel video summarization technique using which we can automatically generate high quality video summaries suitable for wireless and mobile environments. The significant contribution of this paper lies in the proposed clustering scheme. We use Delaunay diagrams to cluster multidimensional point data corresponding to the frame contents of the video. In contrast to the existing clustering techniques used for summarization, our clustering algorithm is fully automatic and well suited for batch processing. We illustrate the quality of our clustering and summarization scheme in an experiment using several video clips. %B 2004 IEEE International Conference on Communications %I IEEE %V 3 %P 1532- 1536 Vol.3 - 1532- 1536 Vol.3 %8 2004/06/20/24 %@ 0-7803-8533-0 %G eng %R 10.1109/ICC.2004.1312767 %0 Journal Article %J IEEE Transactions on Multimedia %D 2004 %T End-to-end analysis of distributed video-on-demand systems %A Mundur, Padma %A Simon,R. %A Sood,A. K %K Admission control %K admission control strategies %K Analytical models %K Computer science %K distributed architecture %K distributed video-on-demand systems %K end-to-end analysis %K global request handling %K High-speed networks %K Network servers %K Next generation networking %K Performance analysis %K performance evaluation methodology %K Protocols %K request handling %K reservation protocols %K resource allocation %K Resource management %K signaling protocols %K telecommunication congestion control %K video on demand %K Video sharing %X The focus of the research presented in this paper is the end-to-end analysis of a distributed Video-on-Demand (VoD) system. We analyze the distributed architecture of a VoD system to design global request handling and admission control strategies and evaluate them using global metrics. The performance evaluation methodology developed in this paper helps in determining efficient ways of using all resources in the VoD architecture within the constraints of providing guaranteed high quality service to each request. For instance, our simulation results show that request handling policies based on limited redirection of blocked requests to other resources perform better than load sharing policies. We also show that request handling policies based on redirection have simpler connection establishment semantics than load sharing policies and, therefore, are easily incorporated into reservation or signaling protocols. %B IEEE Transactions on Multimedia %V 6 %P 129 - 141 %8 2004/02// %@ 1520-9210 %G eng %N 1 %R 10.1109/TMM.2003.819757 %0 Conference Paper %B Eighth International Conference on Information Visualisation, 2004. IV 2004. Proceedings %D 2004 %T Extending the utility of treemaps with flexible hierarchy %A Chintalapani,G. %A Plaisant, Catherine %A Shneiderman, Ben %K 2D displays %K Computer displays %K Computer science %K data visualisation %K Data visualization %K Educational institutions %K flexible hierarchy %K graphical user interface %K Graphical user interfaces %K hierarchical information %K Nominations and elections %K Switches %K Tree data structures %K Tree graphs %K Treemap 4.0 %K Two dimensional displays %K usability %K visualization technique %X Treemaps are a visualization technique for presenting hierarchical information on two-dimensional displays. Prior implementations limit the visualization to pre-defined static hierarchies. Flexible hierarchy, a new capability of Treemap 4.0, enables users to define various hierarchies through dynamically selecting a series of data attributes so that they can discover patterns, clusters and outliers. This work describes the design and implementation issues of flexible hierarchy. It then reports on a usability study, which led to enhancements to the interface. %B Eighth International Conference on Information Visualisation, 2004. IV 2004. Proceedings %I IEEE %P 335 - 344 %8 2004/07/14/16 %@ 0-7695-2177-0 %G eng %R 10.1109/IV.2004.1320166 %0 Conference Paper %B Eighth International Conference on Information Visualisation, 2004. IV 2004. Proceedings %D 2004 %T Facilitating understanding of information visualizations: emerging principles and examples %A Shneiderman, Ben %K Computer science %K data visualisation %K Educational institutions %K Guidelines %K hierarchical visualization %K HUMANS %K Information Visualization %K Laboratories %K multidimensional visualization %K Portable computers %K Testing %K usability %K User interfaces %K Visualization %X Summary form only given. The enthusiasm for information visualization has generated a wide variety of interesting tools for multi-dimensional, hierarchical, and other kinds of visualizations. However, some designs are readily accepted as understandable and useful, while others are perceived as confusing and useless. Controlled studies have begun to sort of some of the issues, but the insights of designers and usability tests are contributing interesting cognitive hypotheses for researchers and practical guidelines for developers. This paper offers examples of what works and what doesn't with a preliminary set of principles that might have wide applicability. %B Eighth International Conference on Information Visualisation, 2004. IV 2004. Proceedings %I IEEE %8 2004/07/14/16 %@ 0-7695-2177-0 %G eng %R 10.1109/IV.2004.1320117 %0 Conference Paper %B 13th International Conference on Computer Communications and Networks, 2004. ICCCN 2004. Proceedings %D 2004 %T High-performance MAC for high-capacity wireless LANs %A Yuan Yuan %A Daqing Gu %A Arbaugh, William A. %A Jinyun Zhang %K 35 Mbit/s %K access protocols %K Aggregates %K Bandwidth %K batch transmission %K Computer science %K Educational institutions %K high-capacity wireless LAN %K high-performance MAC %K Laboratories %K Local area networks %K Media Access Protocol %K opportunistic selection %K Physical layer %K probability %K Throughput %K Wireless LAN %X The next-generation wireless technologies, e.g., 802.11n and 802.15.3a, offer a physical-layer speed at least an-order-of-magnitude higher than the current standards. However, direct application of current MACs leads to high protocol overhead and significant throughput degradation. In this paper, we propose ADCA, a high-performance MAC that works with high-capacity physical layer. ADCA exploits two ideas of adaptive batch transmission and opportunistic selection of high-rate hosts to simultaneously reduce the overhead and improve the aggregate throughput. It opportunistically favors high-rate hosts by providing higher access probability and more access time, while ensuring each low-rate host certain minimum amount of channel access time. Simulations show that the ADCA design increases the throughput by 112% and reduces the average delay by 55% compared with the legacy DCF. It delivers more than 100 Mbps MAC-layer throughput as compared with 35 Mbps offered by the legacy MAC %B 13th International Conference on Computer Communications and Networks, 2004. ICCCN 2004. Proceedings %I IEEE %P 167 - 172 %8 2004/10/11/13 %@ 0-7803-8814-3 %G eng %R 10.1109/ICCCN.2004.1401615 %0 Book Section %B The Semantic Web – ISWC 2004 %D 2004 %T Information Gathering During Planning for Web Service Composition %A Kuter,Ugur %A Sirin,Evren %A Nau, Dana S. %A Parsia,Bijan %A Hendler,James %E McIlraith,Sheila %E Plexousakis,Dimitris %E van Harmelen,Frank %K Computer science %X Hierarchical Task-Network (HTN) based planning techniques have been applied to the problem of composing Web Services, especially when described using the OWL − S service ontologies. Many of the existing Web Services are either exclusively information providing or crucially depend on information-providing services. Thus, many interesting service compositions involve collecting information either during execution or during the composition process itself. In this paper, we focus on the latter issue. In particular, we present ENQUIRER , an HTN-planning algorithm designed for planning domains in which the information about the initial state of the world may not be complete, but it is discoverable through plan-time information-gathering queries. We have shown that ENQUIRER is sound and complete, and derived several mathematical relationships among the amount of available information, the likelihood of the planner finding a plan, and the quality of the plan found. We have performed experimental tests that confirmed our theoretical results and that demonstrated how ENQUIRER can be used in Web Service composition. %B The Semantic Web – ISWC 2004 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 3298 %P 335 - 349 %8 2004/// %@ 978-3-540-23798-3 %G eng %U http://www.springerlink.com/content/v829m5080fc0bpng/abstract/ %0 Book Section %B Foundations of Information and Knowledge Systems %D 2004 %T Plan Databases: Model and Algebra %A Yaman,Fusun %A Adali,Sibel %A Nau, Dana S. %A Sapino,Maria %A Subrahmanian,V. %E Seipel,Dietmar %E Turull-Torres,José %K Computer science %X Despite the fact that thousands of applications manipulate plans, there has been no work to date on managing large databases of plans. In this paper, we first propose a formal model of plan databases. We describe important notions of consistency and coherence for such databases. We then propose a set of operators similar to the relational algebra to query such databases of plans. %B Foundations of Information and Knowledge Systems %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2942 %P 302 - 319 %8 2004/// %@ 978-3-540-20965-2 %G eng %U http://www.springerlink.com/content/yqhlqtu4te18q2e1/abstract/ %0 Conference Paper %B IEEE Symposium on Information Visualization, 2004. INFOVIS 2004 %D 2004 %T A Rank-by-Feature Framework for Unsupervised Multidimensional Data Exploration Using Low Dimensional Projections %A Seo,J. %A Shneiderman, Ben %K axis-parallel projections %K boxplot %K color-coded lower-triangular matrix %K computational complexity %K computational geometry %K Computer displays %K Computer science %K Computer vision %K Data analysis %K data mining %K data visualisation %K Data visualization %K Displays %K dynamic query %K Educational institutions %K exploratory data analysis %K feature detection %K feature detection/selection %K Feature extraction %K feature selection %K graph theory %K graphical displays %K histogram %K Information Visualization %K interactive systems %K Laboratories %K Multidimensional systems %K Principal component analysis %K rank-by-feature prism %K scatterplot %K statistical analysis %K statistical graphics %K statistical graphs %K unsupervised multidimensional data exploration %K very large databases %X Exploratory analysis of multidimensional data sets is challenging because of the difficulty in comprehending more than three dimensions. Two fundamental statistical principles for the exploratory analysis are (1) to examine each dimension first and then find relationships among dimensions, and (2) to try graphical displays first and then find numerical summaries (D.S. Moore, (1999). We implement these principles in a novel conceptual framework called the rank-by-feature framework. In the framework, users can choose a ranking criterion interesting to them and sort 1D or 2D axis-parallel projections according to the criterion. We introduce the rank-by-feature prism that is a color-coded lower-triangular matrix that guides users to desired features. Statistical graphs (histogram, boxplot, and scatterplot) and information visualization techniques (overview, coordination, and dynamic query) are combined to help users effectively traverse 1D and 2D axis-parallel projections, and finally to help them interactively find interesting features %B IEEE Symposium on Information Visualization, 2004. INFOVIS 2004 %I IEEE %P 65 - 72 %8 2004/// %@ 0-7803-8779-3 %G eng %R 10.1109/INFVIS.2004.3 %0 Conference Paper %B Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International %D 2004 %T Unobtrusiveness and efficiency in idle cycle stealing for PC grids %A Ryu, K. D %A Hollingsworth, Jeffrey K %K Biological system modeling %K Computational modeling %K Computer science %K Computer simulation %K Contracts %K desktop grid system %K fine-grain cycle stealing approach %K grid computing %K idle cycle stealing %K Linger-Longer system %K Linux %K Linux cluster %K microcomputers %K PC grids %K Personal communication networks %K Prototypes %K resource allocation %K Throughput %K workstation clusters %K workstation grid systems %K Workstations %X Summary form only given. Studies have shown that for a significant fraction of the time desktop PCs and workstations are under-utilized. To exploit these idle resources, various desktop/workstation grid systems have been developed. The ultimate goal of such systems is to maximize efficiency of resource usage while maintaining low obtrusiveness to machine owners. To this end, we created a new fine-grain cycle stealing approach and conducted a performance comparison study against the traditional coarse-grain cycle stealing. We developed a prototype of fine-grain cycle stealing, the Linger-Longer system, on a Linux cluster. The experiments on a cluster of desktop Linux PCs with benchmark applications show that, overall, fine-grain cycle stealing can improve efficiency of idle cycle usage by increasing the guest job throughput by 50% to 70%, while limiting obtrusiveness with no more than 3% of host job slowdown. %B Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International %I IEEE %8 2004/04/26/30 %@ 0-7695-2132-0 %G eng %R 10.1109/IPDPS.2004.1302987 %0 Book Section %B The Semantic Web - ISWC 2003 %D 2003 %T Automating DAML-S Web Services Composition Using SHOP2 %A Wu,Dan %A Parsia,Bijan %A Sirin,Evren %A Hendler,James %A Nau, Dana S. %E Fensel,Dieter %E Sycara,Katia %E Mylopoulos,John %K Computer science %X The DAML-S Process Model is designed to support the application of AI planning techniques to the automated composition of Web services. SHOP2 is an Hierarchical Task Network (HTN) planner well-suited for working with the Process Model. We have proven the correspondence between the semantics of SHOP2 and the situation calculus semantics of the Process Model. We have also implemented a system which soundly and completely plans over sets of DAML-S descriptions using a SHOP2 planner, and then executes the resulting plans over the Web. We discuss the challenges and difficulties of using SHOP2 in the information-rich and human-oriented context of Web services. %B The Semantic Web - ISWC 2003 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2870 %P 195 - 210 %8 2003/// %@ 978-3-540-20362-9 %G eng %U http://www.springerlink.com/content/rm5ejwlmbw0mdv97/abstract/ %0 Conference Paper %B Proceedings of the 36th Annual Hawaii International Conference on System Sciences, 2003 %D 2003 %T The effect of bilingual term list size on dictionary-based cross-language information retrieval %A Demner-Fushman,D. %A Oard, Douglas %K bilingual term list %K Chinese language %K Computer science %K Control systems %K Cross-language information retrieval %K data mining %K Dictionaries %K dictionary-based information retrieval %K Educational institutions %K English language %K Frequency %K Information retrieval %K language translation %K named-entity translation %K natural languages %K Surface morphology %K Terminology %X Bilingual term lists are extensively used as a resource for dictionary-based cross-language information retrieval (CLIR), in which the goal is to find documents written in one natural language based on queries that are expressed in another. This paper identifies eight types of terms that affect retrieval effectiveness in CLIR applications through their coverage by general-purpose bilingual term lists, and reports results from an experimental evaluation of the coverage of 35 bilingual term lists in news retrieval application. Retrieval effectiveness was found to be strongly influenced by term list size for lists that contain between 3,000 and 30,000 unique terms per language. Supplemental techniques for named entity translation were found to be useful with even the largest lexicons. The contribution of named-entity translation was evaluated in a cross-language experiment involving English and Chinese. Smaller effects were observed from deficiencies in the coverage of domain-specific terminology when searching news stories. %B Proceedings of the 36th Annual Hawaii International Conference on System Sciences, 2003 %I IEEE %8 2003/01/06/9 %@ 0-7695-1874-5 %G eng %R 10.1109/HICSS.2003.1174250 %0 Journal Article %J Annals of Mathematics and Artificial Intelligence %D 2003 %T IMPACTing SHOP: Putting an AI Planner Into a Multi-Agent Environment %A Dix,Jürgen %A Muñoz-Avila,Héctor %A Nau, Dana S. %A Zhang,Lingling %K Computer science %X In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. We define the A-SHOP algorithm, an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that A-SHOP is both sound and complete if certain conditions are met. %B Annals of Mathematics and Artificial Intelligence %V 37 %P 381 - 407 %8 2003/// %@ 1012-2443 %G eng %U http://www.springerlink.com/content/g4r0mn835846p65w/abstract/ %N 4 %R 10.1023/A:1021560510377 %0 Conference Paper %B 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, 2003. Proceedings. CCGrid 2003 %D 2003 %T Improving access to multi-dimensional self-describing scientific datasets %A Nam,B. %A Sussman, Alan %K Application software %K application-specific semantic metadata %K Bandwidth %K Computer science %K database indexing %K disk I/O bandwidth %K distributed databases %K Educational institutions %K Indexing %K indexing structures %K Libraries %K meta data %K Middleware %K multidimensional arrays %K multidimensional datasets %K Multidimensional systems %K NASA %K NASA remote sensing data %K Navigation %K query formulation %K self-describing scientific data file formats %K structural metadata %K very large databases %X Applications that query into very large multidimensional datasets are becoming more common. Many self-describing scientific data file formats have also emerged, which have structural metadata to help navigate the multi-dimensional arrays that are stored in the files. The files may also contain application-specific semantic metadata. In this paper, we discuss efficient methods for performing searches for subsets of multi-dimensional data objects, using semantic information to build multidimensional indexes, and group data items into properly sized chunks to maximize disk I/O bandwidth. This work is the first step in the design and implementation of a generic indexing library that will work with various high-dimension scientific data file formats containing semantic information about the stored data. To validate the approach, we have implemented indexing structures for NASA remote sensing data stored in the HDF format with a specific schema (HDF-EOS), and show the performance improvements that are gained from indexing the datasets, compared to using the existing HDF library for accessing the data. %B 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, 2003. Proceedings. CCGrid 2003 %I IEEE %P 172 - 179 %8 2003/05/12/15 %@ 0-7695-1919-9 %G eng %R 10.1109/CCGRID.2003.1199366 %0 Book Section %B KI 2003: Advances in Artificial Intelligence %D 2003 %T Planning in Answer Set Programming Using Ordered Task Decomposition %A Dix,Jürgen %A Kuter,Ugur %A Nau, Dana S. %E Günter,Andreas %E Kruse,Rudolf %E Neumann,Bernd %K Computer science %X In this paper we introduce a formalism for solving Hierarchical Task Network ( HTN ) Planning using Answer Set Programming ( ASP ). We consider the formulation of HTN planning as described in the SHOP planning system and define a systematic translation method from SHOP ’s representation of the planning problem into logic programs with negation. We show that our translation is sound and complete : answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. We compare our method to (1) similar approaches based on non- HTN planning and (2) SHOP , a dedicated planning system. We show that our approach outperforms non- HTN methods and that its performance is better with ASP systems that allow for nonground programs than with ASP systems that require ground programs. %B KI 2003: Advances in Artificial Intelligence %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2821 %P 490 - 504 %8 2003/// %@ 978-3-540-20059-8 %G eng %U http://www.springerlink.com/content/ekt1kye92lh12lpj/abstract/ %0 Conference Paper %B 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003 %D 2003 %T A secure service discovery protocol for MANET %A Yuan Yuan %A Arbaugh, William A. %K ad hoc networks %K centralized administration %K Computer architecture %K Computer science %K dynamic service discovery infrastructure %K Educational institutions %K MANET %K Manuals %K mobile ad hoc network %K Mobile ad hoc networks %K Mobile computing %K mobile radio %K noninfrastructure network %K Pervasive computing %K Protocols %K routing protocols %K secure service discovery protocol %K Security %K service discovery techniques %K service discovery technologies %K telecommunication computing %K telecommunication services %K XML %X Service discovery technologies are exploited to enable services to advertise their existence in a dynamic way, and can be discovered, configured and used by other devices with minimum manual efforts. It plays an essential role in future network scenarios especially with development of mobile ad hoc network (MANET) and emergence of pervasive computing. Because MANET allows these devices to communicate dynamically without fixed infrastructure and centralized administration, it gives rise to the challenges of the service discovery techniques. In this paper, we present a dynamic service discovery infrastructure that uses XML to describe services and match using the semantic content of service descriptions for MANET. We believe that the architecture we have designed is a necessary component of service discovery in non-infrastructure network by further exploring the secure and performance issues of this infrastructure. %B 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003 %I IEEE %V 1 %P 502- 506 Vol.1 - 502- 506 Vol.1 %8 2003/09/07/10 %@ 0-7803-7822-9 %G eng %R 10.1109/PIMRC.2003.1264322 %0 Book Section %B Privacy Enhancing TechnologiesPrivacy Enhancing Technologies %D 2003 %T Thwarting Web Censorship with Untrusted Messenger Discovery %A Feamster, Nick %A Balazinska,Magdalena %A Wang,Winston %A Balakrishnan,Hari %A Karger,David %E Dingledine,Roger %K Computer science %X All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem : how can clients discover the proxies without having the censor discover and block these proxies? To avoid widespread discovery and blocking, proxies must not be widely published and should be discovered in-band. In this paper, we present a proxy discovery mechanism called keyspace hopping that meets this goal. Similar in spirit to frequency hopping in wireless networks, keyspace hopping ensures that each client discovers only a small fraction of the total number of proxies. However, requiring clients to independently discover proxies from a large set makes it practically impossible to verify the trustworthiness of every proxy and creates the possibility of having untrusted proxies. To address this, we propose separating the proxy into two distinct components—the messenger , which the client discovers using keyspace hopping and which simply acts as a gateway to the Internet; and the portal , whose identity is widely-published and whose responsibility it is to interpret and serve the client’s requests for censored content. We show how this separation, as well as in-band proxy discovery, can be applied to a variety of anti-censorship systems. %B Privacy Enhancing TechnologiesPrivacy Enhancing Technologies %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2760 %P 125 - 140 %8 2003/// %@ 978-3-540-20610-1 %G eng %U http://www.springerlink.com/content/1gg8p94deqek968t/abstract/ %0 Conference Paper %B 2003 IEEE Conference on Open Architectures and Network Programming %D 2003 %T User-specified adaptive scheduling in a streaming media network %A Hicks, Michael W. %A Nagarajan,A. %A van Renesse,R. %K Adaptive scheduling %K CAMERAS %K Computer networks %K Computer science %K distributed stream processing system %K Educational institutions %K global resource scheduling %K Intelligent networks %K MediaNet %K Mobile computing %K network utilization %K Process design %K Processor scheduling %K quality of service %K Streaming media %K streaming media network %K user performance %K user-specified adaptive scheduling %X In disaster and combat situations, mobile cameras and other sensors transmit real-time data, used by many operators or analysis tools. Unfortunately, in the face of limited, unreliable resources, and varying demands, not all users may be able to get the fidelity they require. This paper describes MediaNet, a distributed stream processing system designed with the above scenarios in mind. Unlike past approaches, MediaNet's users can intuitively specify how the system should adapt based on their individual needs. MediaNet uses both local and online global resource scheduling to improve user performance and network utilization, and adapts without requiring underlying support for resource reservations. Performance experiments show that our scheduling algorithm is reasonably fast, and that user performance and network utilization are both significantly improved. %B 2003 IEEE Conference on Open Architectures and Network Programming %I IEEE %P 87 - 96 %8 2003/04/04/5 %@ 0-7803-7764-8 %G eng %R 10.1109/OPNARC.2003.1196376 %0 Conference Paper %B Supercomputing, ACM/IEEE 2002 Conference %D 2002 %T Active Harmony: Towards Automated Performance Tuning %A Tapus, C. %A I-Hsin Chung %A Hollingsworth, Jeffrey K %K Application software %K Automatic control %K Computational modeling %K Computer science %K Computerized monitoring %K Control systems %K grid computing %K Runtime library %K software libraries %K Specification languages %X In this paper, we present the Active Harmony automated runtime tuning system. We describe the interface used by programs to make applications tunable. We present the Library Specification Layer which helps program library developers expose multiple variations of the same API using different algorithms.The Library Specification Language helps to select the most appropriate program library to tune the overall performance. We also present the optimization algorithm used to adjust parameters in the application and the libraries. Finally, we present results that show how the system is able to tune several real applications. The automated tuning system is able to tune the application parameers to within a few percent of the best value after evaluating only 11 out of over 1,700 possible configurations. %B Supercomputing, ACM/IEEE 2002 Conference %I IEEE %P 44 - 44 %8 2002/11// %@ 0-7695-1524-X %G eng %R 10.1109/SC.2002.10062 %0 Book Section %B Advances in Case-Based Reasoning %D 2002 %T On the Complexity of Plan Adaptation by Derivational Analogy in a Universal Classical Planning Framework %A Au,Tsz-Chiu %A Muñoz-Avila,Héctor %A Nau, Dana S. %E Craw,Susan %E Preece,Alun %K Computer science %X In this paper we present an algorithm called DerUCP, which can be regarded as a general model for plan adaptation using Derivational Analogy. Using DerUCP, we show that previous results on the complexity of plan adaptation do not apply to Derivational Analogy. We also show that Derivational Analogy can potentially produce exponential reductions in the size of the search space generated by a planning system. %B Advances in Case-Based Reasoning %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2416 %P 199 - 206 %8 2002/// %@ 978-3-540-44109-0 %G eng %U http://www.springerlink.com/content/db2mr13j90mfrcaw/abstract/ %0 Conference Paper %B 18th International Conference on Data Engineering, 2002. Proceedings %D 2002 %T Decoupled query optimization for federated database systems %A Deshpande, Amol %A Hellerstein,J. M %K Algorithm design and analysis %K Cohera federated database %K Computer science %K Corporate acquisitions %K Cost function %K Database systems %K decoupled optimization %K Design optimization %K distributed databases %K federated databases %K federated relational database systems %K Internet %K Query optimization %K query optimizer %K Query processing %K Relational databases %K Space exploration %X We study the problem of query optimization in federated relational database systems. The nature of federated databases explicitly decouples many aspects of the optimization process, often making it imperative for the optimizer to consult underlying data sources while doing cost-based optimization. This not only increases the cost of optimization, but also changes the trade-offs involved in the optimization process significantly. The dominant cost in the decoupled optimization process is the "cost of costing" that traditionally has been considered insignificant. The optimizer can only afford a few rounds of messages to the underlying data sources and hence the optimization techniques in this environment must be geared toward gathering all the required cost information with minimal communication. In this paper, we explore the design space for a query optimizer in this environment and demonstrate the need for decoupling various aspects of the optimization process. We present minimum-communication decoupled variants of various query optimization techniques, and discuss tradeoffs in their performance in this scenario. We have implemented these techniques in the Cohera federated database system and our experimental results, somewhat surprisingly, indicate that a simple two-phase optimization scheme performs fairly well as long as the physical database design is known to the optimizer, though more aggressive algorithms are required otherwise %B 18th International Conference on Data Engineering, 2002. Proceedings %I IEEE %P 716 - 727 %8 2002/// %@ 0-7695-1531-2 %G eng %R 10.1109/ICDE.2002.994788 %0 Conference Paper %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %D 2002 %T Dependent rounding in bipartite graphs %A Gandhi,R. %A Khuller, Samir %A Parthasarathy,S. %A Srinivasan, Aravind %K Application software %K Approximation algorithms %K bipartite graph %K bipartite graphs %K broadcast channels %K broadcast scheduling %K Broadcasting %K capacitated vertex cover %K Character generation %K computational complexity %K Computer science %K Delay %K edge-sets %K Educational institutions %K fair scheduling %K fractional vectors %K graph theory %K per-user fairness properties %K pipage rounding technique %K Processor scheduling %K Random variables %K random-graph models %K randomized rounding approach %K rounding method %K scheduling %K Scheduling algorithm %K telecommunication computing %K unrelated parallel machines %X We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties. %B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings %I IEEE %P 323 - 332 %8 2002/// %@ 0-7695-1822-2 %G eng %R 10.1109/SFCS.2002.1181955 %0 Conference Paper %B DARPA Active NEtworks Conference and Exposition, 2002. Proceedings %D 2002 %T Experiences with capsule-based active networking %A Hicks, Michael W. %A Moore,J. T %A Wetherall,D. %A Nettles,S. %K active networking %K ANTS %K application-specific routing %K capsule architecture %K capsule-based systems %K computer crime %K Computer network management %K Computer networks %K Computer science %K Contracts %K Electronic switching systems %K INFORMATION SCIENCE %K Internet %K internetworking %K network management %K PLANet %K Planets %K programmability %K programmable packets %K Programming %K Security %K Standards development %K telecommunication network routing %K usability %X Active networking adds programmability to the elements of the network, most aggressively by using programmable packets, or capsules. ANTS [22, 21] and PLANet [10, 8] are the most mature examples of capsule-based systems, both having been publicly available for several years. This paper presents our experience with these systems and the lessons they hold for the future of capsule-based active networking. The paper focuses on four key issues: flexibility, performance, security, and usability. We consider how ANTS and PLANet address these issues, noting that despite substantial surface differences, both systems identify similar key problems and use closely related solutions. Based on our experience with these systems we conclude that capsule-based systems can achieve useful levels of flexibility, performance, and usability. Many aspects of security can also be adequately addressed, but some important problems related to denial of service remain as open problems %B DARPA Active NEtworks Conference and Exposition, 2002. Proceedings %I IEEE %P 16 - 24 %8 2002/// %@ 0-7695-1564-9 %G eng %R 10.1109/DANCE.2002.1003481 %0 Book Section %B Dependable Computing EDCC-4 %D 2002 %T Experimental Evaluation of the Unavailability Induced by a Group Membership Protocol %A Joshi,Kaustubh %A Michel Cukier %A Sanders,William %E Bondavalli,Andrea %E Thevenod-Fosse,Pascale %K Computer science %X Group communication is an important paradigm for building highly available distributed systems. However, group membership operations often require the system to block message traffic, causing system services to become unavailable. This makes it important to quantify the unavailability induced by membership operations. This paper experimentally evaluates the blocking behavior of the group membership protocol of the Ensemble group communication system using a novel global-state-based fault injection technique. In doing so, we demonstrate how a layered distributed protocol such as the Ensemble group membership protocol can be modeled in terms of a state machine abstraction, and show how the resulting global state space can be used to specify fault triggers and define important measures on the system. Using this approach, we evaluate the cost associated with important states of the protocol under varying workload and group size. We also evaluate the sensitivity of the protocol to the occurrence of a second correlated crash failure during its operation. %B Dependable Computing EDCC-4 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2485 %P 644 - 648 %8 2002/// %@ 978-3-540-00012-9 %G eng %U http://www.springerlink.com/content/mnkd4upqr14w2r7e/abstract/ %0 Conference Paper %B 2002 International Symposium on Technology and Society, 2002. (ISTAS'02) %D 2002 %T Improving Web-based civic information access: a case study of the 50 US states %A Ceaparu,I. %A Shneiderman, Ben %K Computer aided software engineering %K Computer science %K contact information %K Educational institutions %K government data processing %K Guidelines %K home page design features %K information resources %K Laboratories %K Modems %K Navigation %K online help %K privacy %K privacy policies %K search boxes %K Tagging %K Uniform resource locators %K US states %K USA %K User interfaces %K Web sites %K Web-based civic information access %X An analysis of the home pages of all fifty US states reveals great variety in key design features that influence efficacy. Some states had excessively large byte counts that would slow users connected by commonly-used 56 K modems. Many web sites had low numbers of or poorly organized links that would make it hard for citizens to find what they were interested in. Features such as search boxes, privacy policies, online help, or contact information need to be added by several states. Our analysis concludes with ten recommendations and finds many further opportunities for individual states to improve their Websites. However still greater benefits will come through collaboration among the states that would lead to consistency, appropriate tagging, and common tools. %B 2002 International Symposium on Technology and Society, 2002. (ISTAS'02) %I IEEE %P 275 - 282 %8 2002/// %@ 0-7803-7284-0 %G eng %R 10.1109/ISTAS.2002.1013826 %0 Conference Paper %B 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings %D 2002 %T P5 : a protocol for scalable anonymous communication %A Sherwood,R. %A Bhattacharjee, Bobby %A Srinivasan, Aravind %K Broadcasting %K communication efficiency %K Computer science %K cryptography %K data privacy %K Educational institutions %K Internet %K large anonymous groups %K P5 protocol %K packet-level simulations %K Particle measurements %K Peer to peer computing %K peer-to-peer personal privacy protocol %K privacy %K Protocols %K receiver anonymity %K scalable anonymous communication %K security of data %K sender anonymity %K sender-receiver anonymity %K Size measurement %K telecommunication security %X We present a protocol for anonymous communication over the Internet. Our protocol, called P5 (peer-to-peer personal privacy protocol) provides sender-, receiver-, and sender-receiver anonymity. P5 is designed to be implemented over current Internet protocols, and does not require any special infrastructure support. A novel feature of P5 is that it allows individual participants to trade-off degree of anonymity for communication efficiency, and hence can be used to scalably implement large anonymous groups. We present a description of P5, an analysis of its anonymity and communication efficiency, and evaluate its performance using detailed packet-level simulations. %B 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings %I IEEE %P 58 - 70 %8 2002/// %@ 0-7695-1543-6 %G eng %R 10.1109/SECPRI.2002.1004362 %0 Conference Paper %B Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM %D 2002 %T Scheduling multiple data visualization query workloads on a shared memory machine %A Andrade,H. %A Kurc, T. %A Sussman, Alan %A Saltz, J. %K Atomic force microscopy %K Biomedical informatics %K Computer science %K Data analysis %K data visualisation %K Data visualization %K datasets %K deductive databases %K digitized microscopy image browsing %K directed graph %K directed graphs %K dynamic query scheduling model %K Educational institutions %K high workloads %K image database %K limited resources %K multiple data visualization query workloads %K multiple query optimization %K performance %K priority queue %K Processor scheduling %K Query processing %K query ranking %K Relational databases %K scheduling %K shared memory machine %K shared memory systems %K Virtual Microscope %K visual databases %X Query scheduling plays an important role when systems are faced with limited resources and high workloads. It becomes even more relevant for servers applying multiple query optimization techniques to batches of queries, in which portions of datasets as well as intermediate results are maintained in memory to speed up query evaluation. We present a dynamic query scheduling model based on a priority queue implementation using a directed graph and a strategy for ranking queries. We examine the relative performance of several ranking strategies on a shared-memory machine using two different versions of an application, called the Virtual Microscope, for browsing digitized microscopy images %B Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM %I IEEE %P 11 - 18 %8 2002/// %@ 0-7695-1573-8 %G eng %R 10.1109/IPDPS.2002.1015482 %0 Conference Paper %B DARPA Active NEtworks Conference and Exposition, 2002. Proceedings %D 2002 %T A secure PLAN (extended version) %A Hicks, Michael W. %A Keromytis,A. D %A Smith,J. M %K active internetwork %K active networks %K active-network firewall %K Authentication %K authorisation %K Authorization %K Cities and towns %K Computer networks %K Computer science %K cryptography %K functionally restricted packet language %K general-purpose service routines %K Information security %K internetworking %K IP networks %K latency overhead %K namespace-based security %K PLAN %K PLANet %K Planets %K programmability %K Safety %K security architecture %K telecommunication security %K trust management %K two-level architecture %K Web and internet services %X Active networks promise greater flexibility than current networks, but threaten safety and security by virtue of their programmability. We describe the design and implementation of a security architecture for the active network PLANet (Hicks et al., 1999). Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN (Hicks et al., 1998), with an environment of general-purpose service routines governed by trust management (Blaze et al., 1996). In particular, we employ a technique which expands or contracts a packet's service environment based on its level of privilege, termed namespace-based security. As an application of our security architecture, we present the design and implementation of an active-network firewall. We find that the addition of the firewall imposes an approximately 34% latency overhead and as little as a 6.7% space overhead to incoming packets %B DARPA Active NEtworks Conference and Exposition, 2002. Proceedings %I IEEE %P 224 - 237 %8 2002/// %@ 0-7695-1564-9 %G eng %R 10.1109/DANCE.2002.1003496 %0 Book Section %B Logics in Artificial Intelligence %D 2002 %T Theoretical and Empirical Aspects of a Planner in a Multi-agent Environment %A Dix,Jürgen %A Munoz-Avila,Hector %A Nau, Dana S. %A Zhang,Lingling %E Flesca,Sergio %E Greco,Sergio %E Ianni,Giovambattista %E Leone,Nicola %K Computer science %X We give the theoretical foundations and empirical evaluation of a planning agent, ashop, performing HTN planning in a multi-agent environment. ashop is based on ASHOP , an agentised version of the original SHOP HTN planning algorithm, and is integrated in the IMPACT multi-agent environment. We ran several experiments involving accessing various distributed, heterogeneous information sources, based on simplified versions of noncombatant evacuation operations, NEO’s. As a result, we noticed that in such realistic settings the time spent on communication (including network time) is orders of magnitude higher than the actual inference process. This has important consequences for optimisations of such planners. Our main results are: (1) using NEO’s as new, more realistic benchmarks for planners acting in an agent environment, and (2) a memoization mechanism implemented on top of shop, which improves the overall performance considerably. %B Logics in Artificial Intelligence %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2424 %P 173 - 185 %8 2002/// %@ 978-3-540-44190-8 %G eng %U http://www.springerlink.com/content/10lxp56u3e9k0bdd/abstract/ %0 Conference Paper %B Fifth International Conference on Information Visualisation, 2001. Proceedings %D 2001 %T Dynamic queries and brushing on choropleth maps %A Dang,G. %A North,C. %A Shneiderman, Ben %K brushing %K business %K cartography %K choropleth maps %K color coding %K colour graphics %K complex data sets %K Computational Intelligence Society %K Computer science %K data visualisation %K Data visualization %K demographic data %K Demography %K Dynamaps %K dynamic queries %K economic data %K Educational institutions %K geographic information system %K geographic information systems %K Joining processes %K map representations %K map-based information visualization %K Query processing %K Scattering %K scatterplot view %K tabular representations %K user interface %K User interfaces %K World Wide Web %X Users who must combine demographic, economic or other data in a geographic context are often hampered by the integration of tabular and map representations. Static, paper-based solutions limit the amount of data that can be placed on a single map or table. By providing an effective user interface, we believe that researchers, journalists, teachers, and students can explore complex data sets more rapidly and effectively. This paper presents Dynamaps, a generalized map-based information visualization tool for dynamic queries and brushing on choropleth maps. Users can use color coding to show a variable on each geographic region, and then filter out areas that do not meet the desired criteria. In addition, a scatterplot view and a details-on-demand window support overviews and specific fact-finding %B Fifth International Conference on Information Visualisation, 2001. Proceedings %I IEEE %P 757 - 764 %8 2001/// %@ 0-7695-1195-3 %G eng %R 10.1109/IV.2001.942141 %0 Book Section %B Advances in Cryptology — EUROCRYPT 2001Advances in Cryptology — EUROCRYPT 2001 %D 2001 %T Efficient and Non-interactive Non-malleable Commitment %A Di Crescenzo,Giovanni %A Katz, Jonathan %A Ostrovsky,Rafail %A Smith,Adam %E Pfitzmann,Birgit %K Computer science %X We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are non-interactive . Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding. %B Advances in Cryptology — EUROCRYPT 2001Advances in Cryptology — EUROCRYPT 2001 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 2045 %P 40 - 59 %8 2001/// %@ 978-3-540-42070-5 %G eng %U http://www.springerlink.com/content/nhbj60a9da101w0r/abstract/ %0 Journal Article %J IEEE Transactions on Information Theory %D 2001 %T The one-inclusion graph algorithm is near-optimal for the prediction model of learning %A Li,Yi %A Long,P. M %A Srinivasan, Aravind %K Computer science %K concept class %K general-purpose algorithm %K graph theory %K learning prediction model %K learning systems %K near-optimal algorithm %K Neural networks %K one-inclusion graph algorithm %K optimisation %K Prediction algorithms %K prediction theory %K Predictive models %K probability %K Probability distribution %K Upper bound %K Vapnik-Chervonenkis dimension %K Virtual colonoscopy %X Haussler, Littlestone and Warmuth (1994) described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1+o(1) of the best possible such bound for any algorithm %B IEEE Transactions on Information Theory %V 47 %P 1257 - 1261 %8 2001/03// %@ 0018-9448 %G eng %N 3 %R 10.1109/18.915700 %0 Conference Paper %B IEEE Symposium on Information Visualization, 2001. INFOVIS 2001 %D 2001 %T Ordered treemap layouts %A Shneiderman, Ben %A Wattenberg,M. %K Clustering algorithms %K Computer science %K Data visualization %K Displays %K Electronic switching systems %K Filling %K Monte Carlo methods %K Read only memory %K Testing %B IEEE Symposium on Information Visualization, 2001. INFOVIS 2001 %I IEEE %P 73 - 78 %8 2001/// %@ 0-7695-7342-5 %G eng %R 10.1109/INFVIS.2001.963283 %0 Conference Paper %B 2001 IEEE Symposium on Security and Privacy, 2001. S&P 2001. Proceedings %D 2001 %T A trend analysis of exploitations %A Browne,H. K %A Arbaugh, William A. %A McHugh,J. %A Fithen,W. L %K Computer science %K computer security exploits %K Data analysis %K data mining %K Educational institutions %K exploitations %K Performance analysis %K Predictive models %K Regression analysis %K Risk management %K security of data %K software engineering %K system intrusions %K System software %K trend analysis %K vulnerabilities %K vulnerability exploitation %X We have conducted an empirical study of a number of computer security exploits and determined that the rates at which incidents involving the exploit are reported to CERT can be modeled using a common mathematical framework. Data associated with three significant exploits involving vulnerabilities in phf, imap, and bind can all be modeled using the formula C=I+S×√M where C is the cumulative count of reported incidents, M is the time since the start of the exploit cycle, and I and S are the regression coefficients determined by analysis of the incident report data. Further analysis of two additional exploits involving vulnerabilities in mountd and statd confirm the model. We believe that the models will aid in predicting the severity of subsequent vulnerability exploitations, based on the rate of early incident reports %B 2001 IEEE Symposium on Security and Privacy, 2001. S&P 2001. Proceedings %I IEEE %P 214 - 229 %8 2001/// %@ 0-7695-1046-9 %G eng %R 10.1109/SECPRI.2001.924300 %0 Conference Paper %B IEEE International Conference on Information Visualization, 2000. Proceedings %D 2000 %T Direct annotation: a drag-and-drop strategy for labeling photos %A Shneiderman, Ben %A Kang,H. %K Biomedical imaging %K Cities and towns %K Computer errors %K Computer science %K database indexing %K database schema %K Databases %K digital libraries %K direct annotation %K direct manipulation %K drag-and-drop strategy %K Educational institutions %K graphical user interface %K Graphical user interfaces %K History %K hobby computing %K image searching %K label placement %K Labeling %K Laboratories %K Libraries %K personal information systems %K personal names database %K PhotoFinder prototype %K photograph labelling %K photographic libraries %K Photography %K scrolling list %K user interface design %K visual databases %X Annotating photographs is such a time-consuming, tedious and error-prone data entry task that it discourages most owners of personal photo libraries. By allowing the user to drag labels, such as personal names, from a scrolling list and drop them onto a photo, we believe we can make the task faster, easier and more appealing. Since the names are entered in a database, searching for all photos of a friend or family member is dramatically simplified. We describe the user interface design and the database schema to support direct annotation, as implemented in our PhotoFinder prototype %B IEEE International Conference on Information Visualization, 2000. Proceedings %I IEEE %P 88 - 95 %8 2000/// %@ 0-7695-0743-3 %G eng %R 10.1109/IV.2000.859742 %0 Conference Paper %B 11th International Workshop on Database and Expert Systems Applications, 2000. Proceedings %D 2000 %T Domain name based visualization of Web histories in a zoomable user interface %A Gandhi,R. %A Kumar,G. %A Bederson, Benjamin B. %A Shneiderman, Ben %K Computer science %K data visualisation %K domain name %K domain name based visualization %K Domain Tree Browser %K Educational institutions %K History %K hypermedia %K hypertext links %K hypertext systems %K information resources %K Navigation %K online front-ends %K thumbnails %K Tree graphs %K tree structured visual navigation history %K Uniform resource locators %K URLs %K User interfaces %K Visualization %K Web browser companion %K Web histories %K Web pages %K World Wide Web %K zoomable user interface %K zoomable window %X Users of hypertext systems like the World Wide Web (WWW) often find themselves following hypertext links deeper and deeper, only to find themselves “lost” and unable to find their way back to the previously visited pages. We have implemented a Web browser companion called Domain Tree Browser (DTB) that builds a tree structured visual navigation history while browsing the Web. The Domain Tree Browser organizes the URLs visited based on the domain name of each URL and shows thumbnails of each page in a zoomable window %B 11th International Workshop on Database and Expert Systems Applications, 2000. Proceedings %I IEEE %P 591 - 598 %8 2000/// %@ 0-7695-0680-1 %G eng %R 10.1109/DEXA.2000.875085 %0 Conference Paper %B Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International %D 2000 %T Optimizing retrieval and processing of multi-dimensional scientific datasets %A Chang,Chialin %A Kurc, T. %A Sussman, Alan %A Saltz, J. %K active data repository %K Area measurement %K Computer science %K Data analysis %K distributed memory parallel machines %K Educational institutions %K Information retrieval %K Information Storage and Retrieval %K infrastructure %K Microscopy %K Microwave integrated circuits %K multi-dimensional scientific datasets retrieval %K PARALLEL PROCESSING %K Pathology %K range queries %K regular d-dimensional array %K Satellites %K Tomography %X We have developed the Active Data Repository (ADR), an infrastructure that integrates storage, retrieval, and processing of large multi-dimensional scientific datasets on distributed memory parallel machines with multiple disks attached to each node. In earlier work, we proposed three strategies for processing range queries within the ADR framework. Our experimental results show that the relative performance of the strategies changes under varying application characteristics and machine configurations. In this work we investigate approaches to guide and automate the selection of the best strategy for a given application and machine configuration. We describe analytical models to predict the relative performance of the strategies where input data elements are uniformly distributed in the attribute space of the output dataset, restricting the output dataset to be a regular d-dimensional array %B Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International %I IEEE %P 405 - 410 %8 2000/// %@ 0-7695-0574-0 %G eng %R 10.1109/IPDPS.2000.846013 %0 Conference Paper %B Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000 %D 2000 %T Supporting creativity with powerful composition tools for artifacts and performances %A Shneiderman, Ben %K artifacts %K Artificial intelligence %K composition tools %K Computer science %K Context modeling %K creativity %K creativity support %K Educational institutions %K Information retrieval %K Laboratories %K Manufacturing %K music composition %K performances %K Software design %K software libraries %K software tools %K US Department of Transportation %X Modern software such as word processors, slide preparation/presentation tools, or music composition packages are designed to produce artifacts or performances. Now, some designers are expanding their goals to include creativity support into their software. This essay builds on the genex framework for creativity, which has four phases and eight activities. It focuses on the composition activity by considering tools to support initiation, revision, and evaluation. Some existing tools provide partial support that suggests ways in which to develop more ambitious low, middle, and high level tools. The goal is to enable more people to be more creative more of the time. %B Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000 %I IEEE %8 2000/01/04/7 %@ 0-7695-0493-0 %G eng %R 10.1109/HICSS.2000.926896 %0 Conference Paper %B 2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000 %D 2000 %T Visualization methods for personal photo collections: browsing and searching in the PhotoFinder %A Kang,Hyunmo %A Shneiderman, Ben %K Browsing %K Computer science %K digital photo library %K Displays %K drag-and-drop interface %K dynamic query %K Educational institutions %K Filters %K Histograms %K Image retrieval %K personal computing %K personal photo collections %K photo collection management %K PhotoFinder %K Prototypes %K query preview %K scatter plot thumbnail display %K Scattering %K searching %K software libraries %K software tools %K User interfaces %K visual Boolean query interfaces %K visual databases %K Visualization %K visualization methods %X Software tools for personal photo collection management are proliferating, but they usually have limited searching and browsing functions. We implemented the PhotoFinder prototype to enable non-technical users of personal photo collections to search and browse easily. PhotoFinder provides a set of visual Boolean query interfaces, coupled with dynamic query and query preview features. It gives users powerful search capabilities. Using a scatter plot thumbnail display and drag-and-drop interface, PhotoFinder is designed to be easy to use for searching and browsing photos %B 2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000 %I IEEE %V 3 %P 1539-1542 vol.3 - 1539-1542 vol.3 %8 2000/// %@ 0-7803-6536-4 %G eng %R 10.1109/ICME.2000.871061 %0 Conference Paper %B IEEE International Conference on Multimedia Computing and Systems, 1999 %D 1999 %T Integrated admission control in hierarchical video-on-demand systems %A Mundur, Padma %A Simon,R. %A Sood,A. %K Admission control %K Bandwidth %K blocking %K Computer science %K Design methodology %K end-to-end system %K hierarchical video-on-demand systems %K integrated admission control %K Intelligent networks %K Load management %K Motion pictures %K Network servers %K network subsystem %K performance %K Performance analysis %K performance evaluation %K quality of service %K request handling %K resource allocation %K Resource management %K simulation %K storage subsystem %K video on demand %K video servers %X We develop a unified model of a hierarchical video-on-demand (VoD) system by integrating the storage and the network subsystems. Rather than restricting the analysis to an isolated subsystem the performance of the VoD system is analyzed as an end-to-end system. On a system-wide basis, request handling and admission control policies are designed to minimize global performance metrics. Through our simulation, we compare different request handling policies and show that a hierarchical VoD architecture with request handling that allows retrials at more than one resource will minimize overall blocking %B IEEE International Conference on Multimedia Computing and Systems, 1999 %I IEEE %V 1 %P 220-225 vol.1 - 220-225 vol.1 %8 1999/07// %@ 0-7695-0253-9 %G eng %R 10.1109/MMCS.1999.779196 %0 Conference Paper %B Third International Conference on Computational Intelligence and Multimedia Applications, 1999. ICCIMA '99. Proceedings %D 1999 %T Network service selection for distributed multimedia applications %A Simon,R. %A Sood,A. %A Mundur, Padma %K Admission control %K Application software %K application-adequate end-to-end service %K Bandwidth %K Communication system traffic control %K Computer science %K Delay %K distributed processing %K end-to-end delivery delay control %K flexibility %K high-bandwidth distributed multimedia applications %K interactive multimedia %K multimedia systems %K network service selection %K network throughput %K nonpreemptive earliest deadline first %K queueing theory %K Regulators %K system support %K telecommunication services %K Throughput %K Traffic control %K weighted fair queueing %X An important question in the development of system support for distributed multimedia is the type of network service offered to applications. This paper compares two network service disciplines: weighted fair queueing (WFQ) and non-preemptive earliest deadline first (NEDF). We show that, for a broad class of high-bandwidth distributed multimedia applications, WFQ outperforms NEDF in terms of network throughput while still providing an application-adequate end-to-end service. This result holds despite the fact that NEDF offers applications far greater flexibility in terms of control over end-to-end delivery delay %B Third International Conference on Computational Intelligence and Multimedia Applications, 1999. ICCIMA '99. Proceedings %I IEEE %P 388 - 392 %8 1999/// %@ 0-7695-0300-4 %G eng %R 10.1109/ICCIMA.1999.798561 %0 Conference Paper %B 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings %D 1998 %T Improved bounds and algorithms for hypergraph two-coloring %A Radhakrishnan,J. %A Srinivasan, Aravind %K algorithms %K Application software %K Approximation algorithms %K bounds %K computational geometry %K Computer science %K Contracts %K Erbium %K graph colouring %K History %K hypergraph two-coloring %K Lab-on-a-chip %K MATHEMATICS %K n-uniform hypergraph %K Parallel algorithms %K Polynomials %K probability %X We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn)×2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1)×2n due to Beck (1978). We further generalize this to a “local” version, improving on one of the first applications of the Lovasz Local Lemma %B 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings %I IEEE %P 684 - 693 %8 1998/11/08/11 %@ 0-8186-9172-7 %G eng %R 10.1109/SFCS.1998.743519 %0 Conference Paper %B 18th International Conference on Distributed Computing Systems, 1998. Proceedings %D 1998 %T LBF: a performance metric for program reorganization %A Eom, H. %A Hollingsworth, Jeffrey K %K case study %K Computational modeling %K computer network %K Computer science %K Debugging %K distributed processing %K distributed program %K Educational institutions %K Integrated circuit testing %K LBF metric %K load balancing factor %K Load management %K measurement %K NIST %K parallel program %K parallel programming %K performance metric %K program reorganization %K program tuning %K Programming profession %K resource allocation %K software metrics %K software performance evaluation %K US Department of Energy %X We introduce a new performance metric, called Load Balancing Factor (LBF), to assist programmers with evaluating different tuning alternatives. The LBF metric differs from traditional performance metrics since it is intended to measure the performance implications of a specific tuning alternative rather than quantifying where time is spent in the current version of the program. A second unique aspect of the metric is that it provides guidance about moving work within a distributed or parallel program rather than reducing it. A variation of the LBF metric can also be used to predict the performance impact of changing the underlying network. The LBF metric can be computed incrementally and online during the execution of the program to be tuned. We also present a case study that shows that our metric can predict the actual performance gains accurately for a test suite of six programs %B 18th International Conference on Distributed Computing Systems, 1998. Proceedings %I IEEE %P 222 - 229 %8 1998/05/26/29 %@ 0-8186-8292-2 %G eng %R 10.1109/ICDCS.1998.679505 %0 Conference Paper %B , Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998 %D 1998 %T Multicommodity flow and circuit switching %A Leighton,T. %A Rao,S. %A Srinivasan, Aravind %K Application software %K Bandwidth %K circuit switching %K Computer science %K constant-degree expanders %K graph theory %K High speed integrated circuits %K Integrated circuit technology %K Laboratories %K low congestion %K MATHEMATICS %K multicommodity flow %K National electric code %K network routing %K path selections %K Routing %K short flow paths %K Switching circuits %K switching theory %K undirected graphs %K virtual circuit routing %X Given a set of request pairs in a network, the problem of routing virtual circuits with low congestion is to connect each pair by a path so that few paths use the same link in the network. We build on an earlier multicommodity flow based approach of Leighton and Rao (1996) to show that short flow paths lead to path selections with low congestion. This shows that such good path selections exist for constant-degree expanders with strong expansion, generalizing a result of (Broder et al., 1994). We also show, for infinitely many n, n-vertex undirected graphs Gn along with a set T of connection requests, such that: T is fractionally realizable using flow-paths that impose a (fractional) congestion of at most 1; but any rounding of such a flow to the given set of flow-paths, leads to a congestion of Ω(log n/log log n). This is progress on a long-standing open problem %B , Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998 %I IEEE %V 7 %P 459-465 vol.7 - 459-465 vol.7 %8 1998/01/06/9 %@ 0-8186-8255-8 %G eng %R 10.1109/HICSS.1998.649241 %0 Conference Paper %B Fourteenth International Conference on Pattern Recognition, 1998. Proceedings %D 1998 %T Pictorial query trees for query specification in image databases %A Soffer,A. %A Samet, Hanan %A Zotkin,Dmitry N %K Automation %K complex queries %K Computer science %K content-based retrieval %K Database systems %K database-image objects %K Educational institutions %K Electrical capacitance tomography %K grammars %K Image databases %K Image matching %K parsing %K pictorial query trees %K Postal services %K query specification %K query-image objects %K spatial constraints %K syntax %K visual databases %X A technique that enables specifying complex queries in image databases using pictorial query trees is presented. The leaves of a pictorial query tree correspond to individual pictorial queries that specify which objects should appear in the target images as well as how many occurrences of each object are required. In addition, the minimum required certainty of matching between query-image objects and database-image objects, as well as spatial constraints that specify bounds on the distance between objects and the relative direction between them are also specified. Internal nodes in the query tree represent logical operations (AND, OR, XOR) and their negations on the set of pictorial queries (or subtrees) represented by its children. The syntax of query trees is described. Algorithms for processing individual pictorial queries and for parsing and computing the overall result of a pictorial query tree are outlined %B Fourteenth International Conference on Pattern Recognition, 1998. Proceedings %I IEEE %V 1 %P 919-921 vol.1 - 919-921 vol.1 %8 1998/08// %@ 0-8186-8512-3 %G eng %R 10.1109/ICPR.1998.711383 %0 Conference Paper %B IEEE Symposium on Information Visualization, 1997. Proceedings %D 1997 %T Design and evaluation of incremental data structures and algorithms for dynamic query interfaces %A Tanin,E. %A Beigel,R. %A Shneiderman, Ben %K Algorithm design and analysis %K Bars %K Computer science %K continuous real-time feedback %K Data structures %K data visualisation %K Data visualization %K database access mechanism %K Displays %K DQI algorithms %K dynamic query interfaces %K Feedback %K Graphical user interfaces %K Heuristic algorithms %K incremental data structures %K Information Visualization %K large databases %K Manipulator dynamics %K NASA %K query formulation %K query languages %K Query processing %K real-time systems %K small databases %K User interfaces %K very large databases %K visual databases %K visual languages %X A dynamic query interface (DQI) is a database access mechanism that provides continuous real-time feedback to the user during query formulation. Previous work shows that DQIs are elegant and powerful interfaces to small databases. Unfortunately, when applied to large databases, previous DQI algorithms slow to a crawl. We present a new incremental approach to DQI algorithms and display updates that work well with large databases, both in theory and in practice. %B IEEE Symposium on Information Visualization, 1997. Proceedings %I IEEE %P 81 - 86 %8 1997/10/21/21 %@ 0-8186-8189-6 %G eng %R 10.1109/INFVIS.1997.636790 %0 Conference Paper %B , 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings %D 1997 %T Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems %A Srinivasan, Aravind %K Approximation algorithms %K Bandwidth %K Channel allocation %K computational complexity %K Computer science %K edge-disjoint paths %K graph theory %K High speed integrated circuits %K IEL %K Image motion analysis %K Information systems %K multi-commodity flow relaxation %K Multiprocessor interconnection networks %K network routing %K Optical fiber networks %K Routing %K routing problems %K unsplittable flow %X We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation %B , 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings %I IEEE %P 416 - 425 %8 1997/10/20/22 %@ 0-8186-8197-7 %G eng %R 10.1109/SFCS.1997.646130 %0 Conference Paper %B , 1997 International Conference on Parallel Architectures and Compilation Techniques., 1997. Proceedings %D 1997 %T MDL: a language and compiler for dynamic program instrumentation %A Hollingsworth, Jeffrey K %A Niam, O. %A Miller, B. P %A Zhichen Xu %A Goncalves,M. J.R %A Ling Zheng %K Alpha architecture %K application program %K application program interfaces %K Application software %K compiler generators %K Computer science %K dynamic code generation %K Dynamic compiler %K dynamic program instrumentation %K Educational institutions %K files %K instrumentation code %K Instruments %K MDL %K measurement %K message channels %K Message passing %K Metric Description Language %K modules %K nodes %K Operating systems %K optimising compilers %K PA-RISC %K Paradyn Parallel Performance Tools %K Parallel architectures %K parallel programming %K performance data %K platform independent descriptions %K Power 2 architecture %K Power generation %K procedures %K program debugging %K Program processors %K running programs %K Runtime %K software metrics %K SPARC %K Specification languages %K x86 architecture %X We use a form of dynamic code generation, called dynamic instrumentation, to collect data about the execution of an application program. Dynamic instrumentation allows us to instrument running programs to collect performance and other types of information. The instrumentation code is generated incrementally and can be inserted and removed at any time. Our instrumentation currently runs on the SPARC, PA-RISC, Power 2, Alpha, and x86 architectures. Specification of what data to collect are written in a specialized language called the Metric Description Language, that is part of the Paradyn Parallel Performance Tools. This language allows platform independent descriptions of how to collect performance data. It also provides a concise way to specify, how to constrain performance data to particular resources such as modules, procedures, nodes, files, or message channels (or combinations of these resources). We also describe the details of how we weave instrumentation into a running program %B , 1997 International Conference on Parallel Architectures and Compilation Techniques., 1997. Proceedings %I IEEE %P 201 - 212 %8 1997/11/10/14 %@ 0-8186-8090-3 %G eng %R 10.1109/PACT.1997.644016 %0 Conference Paper %B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings %D 1996 %T An algebraic theory of process efficiency %A Natarajan,V. %A Cleaveland, Rance %K algebraic characterization %K algebraic specification %K algebraic theory %K bisimulation-based efficiency preorders %K Calculus %K calculus of communicating systems %K Carbon capture and storage %K Computer science %K concurrent systems %K formal logic %K formal specification %K full abstractness result %K internal activity %K optimality %K process efficiency %K reasoning %K semantic preorders %K System testing %K testing-based semantic theory %X This paper presents a testing-based semantic theory for reasoning about the efficiency of concurrent systems as measured in terms of the amount of their internal activity. The semantic preorders are given an algebraic characterization, and their optimality is established by means of a full abstractness result. They are also shown to subsume existing bisimulation-based efficiency preorders. An example is provided to illustrate the utility of this approach %B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings %I IEEE %P 63 - 72 %8 1996/07/27/30 %@ 0-8186-7463-6 %G eng %R 10.1109/LICS.1996.561304 %0 Conference Paper %B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings %D 1996 %T Efficient model checking via the equational μ-calculus %A Bhat,G. %A Cleaveland, Rance %K Automata %K BDD-based algorithms %K Boolean functions %K Calculus %K compositional model-checking approaches %K computational complexity %K Computer science %K CTL* %K Data structures %K Encoding %K equational variant %K equational μ-calculus %K Equations %K expressive temporal logic %K Logic %K Maintenance %K modal μ-calculus %K Model checking %K on-the-fly procedures %K Surges %K temporal logic %K temporal logic model checking %K unified framework %X This paper studies the use of an equational variant of the modal μ-calculus as a unified framework for efficient temporal logic model checking. In particular we show how an expressive temporal logic, CTL*, may be efficiently translated into the μ-calculus. Using this translation, one may then employ μ-calculus model-checking techniques, including on-the-fly procedures, BDD-based algorithms and compositional model-checking approaches, to determine if systems satisfy formulas in CTL* %B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings %I IEEE %P 304 - 312 %8 1996/07/27/30 %@ 0-8186-7463-6 %G eng %R 10.1109/LICS.1996.561358 %0 Book Section %B Dependable Computing — EDCC-2 %D 1996 %T On stratified sampling for high coverage estimations %A Powell,David %A Michel Cukier %A Arlat,Jean %E Hlawiczka,Andrzej %E Silva,João %E Simoncini,Luca %K Computer science %X This paper addresses the problem of estimating the coverage of a fault tolerance mechanism through statistical processing of observations collected in faultinjection experiments. In an earlier paper, several techniques for sampling the fault/activity input space of a fault tolerance mechanism were presented. Various estimators based on simple sampling in the whole space and stratified sampling in a partitioned space were studied; confidence limits were derived based on a normal approximation. In this paper, the validity of this approximation is analyzed, especially for high coverage systems. The theory of confidence regions is then introduced to estimate the coverage without approximation when, for practical reasons, stratification is used. Three statistics are considered for defining confidence regions. It is shown that one of these statistics — a vectorial statistic — is often more conservative than the other two. However, only the vectorial statistic is computationally tractable. The results obtained are compared with those based on approximation by means of three hypothetical example systems. %B Dependable Computing — EDCC-2 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 1150 %P 35 - 54 %8 1996/// %@ 978-3-540-61772-3 %G eng %U http://www.springerlink.com/content/7t2w2u472601h730/abstract/ %0 Conference Paper %B Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the %D 1995 %T Code generation for multiple mappings %A Kelly,W. %A Pugh, William %A Rosser,E. %K code generation %K Computer science %K Concurrent computing %K control overhead %K Educational institutions %K iteration reordering transformations %K Law %K Legal factors %K loop blocking %K multiple mappings %K optimisation %K optimising compilers %K Optimizing compilers %K PARALLEL PROCESSING %K Performance analysis %K program compilers %X There has been a great amount of recent work toward unifying iteration reordering transformations. Many of these approaches represent transformations as affine mappings from the original iteration space to a new iteration space. These approaches show a great deal of promise, but they all rely on the ability to generate code that iterates over the points in these new iteration spaces in the appropriate order. This problem has been fairly well-studied in the case where all statements use the same mapping. We have developed an algorithm for the less well-studied case where each statement uses a potentially different mapping. Unlike many other approaches, our algorithm can also generate code from mappings corresponding to loop blocking. We address the important trade-off between reducing control overhead and duplicating code %B Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the %I IEEE %P 332 - 341 %8 1995/02/06/9 %@ 0-8186-6965-9 %G eng %R 10.1109/FMPC.1995.380437 %0 Journal Article %J IEEE Transactions on Software Engineering %D 1995 %T Comparing detection methods for software requirements inspections: a replicated experiment %A Porter, Adam %A Votta,L. G. %A Basili, Victor R. %K Assembly %K Computer science %K Design for experiments %K detection methods %K Fault detection %K fault detection rate %K Fault diagnosis %K formal specification %K formal verification %K Gain measurement %K individual fault detection rate %K Inspection %K Loss measurement %K nonsystematic techniques %K performance evaluation %K Performance gain %K replicated experiment %K scenario-based method %K Software development management %K software requirements inspections %K software requirements specifications %K team fault detection rate %X Software requirements specifications (SRS) are often validated manually. One such process is inspection, in which several reviewers independently analyze all or part of the specification and search for faults. These faults are then collected at a meeting of the reviewers and author(s). Usually, reviewers use Ad Hoc or Checklist methods to uncover faults. These methods force all reviewers to rely on nonsystematic techniques to search for a wide variety of faults. We hypothesize that a Scenario-based method, in which each reviewer uses different, systematic techniques to search for different, specific classes of faults, will have a significantly higher success rate. We evaluated this hypothesis using a 3×24 partial factorial, randomized experimental design. Forty eight graduate students in computer science participated in the experiment. They were assembled into sixteen, three-person teams. Each team inspected two SRS using some combination of Ad Hoc, Checklist or Scenario methods. For each inspection we performed four measurements: (1) individual fault detection rate, (2) team fault detection rate, (3) percentage of faults first identified at the collection meeting (meeting gain rate), and (4) percentage of faults first identified by an individual, but never reported at the collection meeting (meeting loss rate). The experimental results are that (1) the Scenario method had a higher fault detection rate than either Ad Hoc or Checklist methods, (2) Scenario reviewers were more effective at detecting the faults their scenarios are designed to uncover, and were no less effective at detecting other faults than both Ad Hoc or Checklist reviewers, (3) Checklist reviewers were no more effective than Ad Hoc reviewers, and (4) Collection meetings produced no net improvement in the fault detection rate-meeting gains were offset by meeting losses %B IEEE Transactions on Software Engineering %V 21 %P 563 - 575 %8 1995/06// %@ 0098-5589 %G eng %N 6 %R 10.1109/32.391380 %0 Conference Paper %B , Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. LICS '95. Proceedings %D 1995 %T Efficient on-the-fly model checking for CTL %A Bhat,G. %A Cleaveland, Rance %A Grumberg,O. %K Algorithm design and analysis %K Automata %K computational complexity %K Computer science %K CTL %K Encoding %K finite automata %K finite-state system %K global algorithm %K Logic %K LTL %K on-the-fly model checking %K Performance analysis %K Safety %K State-space methods %K sublogic %K temporal logic %K time complexity %X This paper gives an on-the-fly algorithm for determining whether a finite-state system satisfies a formula in the temporal logic CTL. The time complexity of our algorithm matches that of the best existing “global algorithm” for model checking in this logic, and it performs as well as the best known global algorithms for the sublogics CTL and LTL. In contrast with these approaches, however, our routine constructs the state space of the system under consideration in a need-driven fashion and will therefore perform better in practice %B , Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. LICS '95. Proceedings %I IEEE %P 388 - 397 %8 1995/06/26/29 %@ 0-8186-7050-9 %G eng %R 10.1109/LICS.1995.523273 %0 Conference Paper %B , IEEE International Conference on Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century %D 1995 %T Experimental investigation of high performance cognitive and interactive text filtering %A Oard, Douglas %A DeClaris,N. %A Dorr, Bonnie J %A Faloutsos,C. %A Marchionini,G. %K Cause effect analysis %K Computer science %K Contracts %K Cornell SMART text retrieval system %K Educational institutions %K Gaussian User Model %K high performance cognitive interactive text filtering %K History %K Information filtering %K Information filters %K Information retrieval %K information retrieval system evaluation %K Libraries %K Matched filters %K online front-ends %K Query processing %K System testing %K text selection effectiveness %K user evaluations %K User interfaces %K user modelling %X Text filtering has become increasingly important as the volume of networked information has exploded in recent years. This paper reviews recent progress in that field and reports on the development of a testbed for experimental investigation of cognitive and interactive text selection based on a history of user evaluations. An interactive filtering system model is presented and a new cognitive filtering technique which the authors call the Gaussian User Model is described. Because development of analytic measures of text selection effectiveness has proven intractable, the authors have modified the Cornell SMART text retrieval system to create a flexible text filtering testbed for experimental determination of filtering effectiveness. The paper concludes with a description of the design of this testbed system %B , IEEE International Conference on Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century %I IEEE %V 5 %P 4398-4403 vol.5 - 4398-4403 vol.5 %8 1995/10/22/25 %@ 0-7803-2559-1 %G eng %R 10.1109/ICSMC.1995.538486 %0 Conference Paper %B , Fifth International Conference on Computer Vision, 1995. Proceedings %D 1995 %T Global rigidity constraints in image displacement fields %A Fermüller, Cornelia %A Aloimonos, J. %K 3D motion parameters %K algorithms %K Automation %K Computer science %K Computer vision %K conic sections %K curves %K equal vectors %K Fluid flow measurement %K global geometric structure %K global rigidity constraints %K image displacement fields %K Image motion analysis %K Image segmentation %K Image sequences %K imaging surface %K Laboratories %K Layout %K Motion estimation %K Motion measurement %K motion vectors %K multiple views %K normal flow fields %K optical flow fields %K regions %K rigid motion %K stereo disparity fields %K Stereo vision %K vectors %K visual information recovery %X Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views %B , Fifth International Conference on Computer Vision, 1995. Proceedings %I IEEE %P 245 - 250 %8 1995/06/20/23 %@ 0-8186-7042-8 %G eng %R 10.1109/ICCV.1995.466779 %0 Conference Paper %B Proceedings of Fifth International Conference on Computer Vision, 1995 %D 1995 %T Global rigidity constraints in image displacement fields %A Fermüller, Cornelia %A Aloimonos, J. %K 3D motion parameters %K algorithms %K Automation %K Computer science %K Computer vision %K conic sections %K curves %K equal vectors %K Fluid flow measurement %K global geometric structure %K global rigidity constraints %K image displacement fields %K Image motion analysis %K Image segmentation %K Image sequences %K imaging surface %K Laboratories %K Layout %K Motion estimation %K Motion measurement %K motion vectors %K multiple views %K normal flow fields %K optical flow fields %K regions %K rigid motion %K stereo disparity fields %K Stereo vision %K vectors %K visual information recovery %X Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views %B Proceedings of Fifth International Conference on Computer Vision, 1995 %I IEEE %P 245 - 250 %8 1995/06/20/23 %@ 0-8186-7042-8 %G eng %R 10.1109/ICCV.1995.466779 %0 Journal Article %J IEEE Transactions on Parallel and Distributed Systems %D 1995 %T Going beyond integer programming with the Omega test to eliminate false data dependences %A Pugh, William %A Wonnacott,D. %K Algorithm design and analysis %K Arithmetic %K Computer science %K Data analysis %K false data dependences %K integer programming %K Linear programming %K Omega test %K Privatization %K Production %K production compilers %K program compilers %K Program processors %K program testing %K program transformations %K Testing %X Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a subclass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers %B IEEE Transactions on Parallel and Distributed Systems %V 6 %P 204 - 211 %8 1995/02// %@ 1045-9219 %G eng %N 2 %R 10.1109/71.342135 %0 Book %D 1995 %T Image Analysis and Processing: 8th International Conference, Iciap '95, San Remo, Italy, September 13-15, 1995 : Proceedings %A Braccini,Carlo %A De Floriani, Leila %A Vernazza,Gianni %K Artificial intelligence %K COMPUTER AIDED DESIGN %K Computer Graphics %K Computer science %K Computer vision %K Computers / CAD-CAM %K Computers / Computer Graphics %K Computers / Computer Science %K Computers / Computer Vision & Pattern Recognition %K Computers / Image Processing %K Computers / Intelligence (AI) & Semantics %K Computers / Optical Data Processing %K Computers / Software Development & Engineering / General %K Electronic books %K IMAGE PROCESSING %K Image processing/ Congresses %K Imaging systems %K Optical data processing %K Optical pattern recognition %K software engineering %X This book presents the proceedings of the 8th International Conference on Image Analysis and Processing, ICIAP '95, held in Sanremo, Italy in September 1995 under the sponsorship of the International Association of Pattern Recognition IAPR.The volume presents 108 papers selected from more than 180 submissions together with six invited contributions. The papers are written by a total of 265 contributing authors and give a comprehensive state-of-the-art report on all current issues of image analysis and processing. Theoretical aspects are addressed as well as systems design and advanced applications, particularly in medical imaging. %I Springer %8 1995/09/28/ %@ 9783540602989 %G eng %0 Conference Paper %B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings %D 1995 %T Splitters and near-optimal derandomization %A Naor,M. %A Schulman,L. J %A Srinivasan, Aravind %K Boosting %K Circuit testing %K computational complexity %K computational linguistics %K Computer science %K Contracts %K derandomization %K deterministic constructions %K Educational institutions %K Engineering profession %K exhaustive testing %K fairly general method %K fixed-subgraph finding algorithms %K hardness of approximation %K Information systems %K k-restrictions %K learning %K local-coloring protocol %K MATHEMATICS %K near-optimal constructions %K near-optimal derandomization %K Parallel algorithms %K probabilistic bound %K probability %K Protocols %K randomised algorithms %K Set cover %K splitters %X We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits %B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings %I IEEE %P 182 - 191 %8 1995/10/23/25 %@ 0-8186-7183-1 %G eng %R 10.1109/SFCS.1995.492475 %0 Conference Paper %B , 1994 IEEE International Conference on Systems, Man, and Cybernetics, 1994. 'Humans, Information and Technology' %D 1994 %T On automatic filtering of multilingual texts %A Oard, Douglas %A DeClaris,N. %A Dorr, Bonnie J %A Faloutsos,C. %K automated performance evaluation %K Business communication %K Computer science %K Discussion forums %K Displays %K Educational institutions %K Floods %K Government %K Information filtering %K Information filters %K Information retrieval %K multilingual information retrieval %K multilingual text filtering %K natural languages %K performance evaluation %X An emerging requirement to sift through the increasing flood of text information has led to the rapid development of information filtering technology in the past five years. This study introduces novel approaches for filtering texts regardless of their source language. We begin with a brief description of related developments in text filtering and multilingual information retrieval. We then present three alternative approaches to selecting texts from a multilingual information stream which represent a logical evolution from existing techniques in related disciplines. Finally, a practical automated performance evaluation technique is proposed %B , 1994 IEEE International Conference on Systems, Man, and Cybernetics, 1994. 'Humans, Information and Technology' %I IEEE %V 2 %P 1645-1650 vol.2 - 1645-1650 vol.2 %8 1994/10/02/5 %@ 0-7803-2129-4 %G eng %R 10.1109/ICSMC.1994.400083 %0 Conference Paper %B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings %D 1994 %T Computing with very weak random sources %A Srinivasan, Aravind %A Zuckerman,D. %K Application software %K BPP simulations %K Chor-Goldreich sources %K computational complexity %K Computational modeling %K Computer science %K Computer simulation %K cryptography %K distributed algorithms %K expander constructions %K hardness %K MATHEMATICS %K min-entropy %K Physics computing %K Polynomials %K probability %K R-bit string %K randomness-efficient Leftover Hash Lemma %K RP algorithms simulation %K Testing %K time-space tradeoffs %K very weak random sources %X For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson %B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings %I IEEE %P 264 - 275 %8 1994/11/20/22 %@ 0-8186-6580-7 %G eng %R 10.1109/SFCS.1994.365688 %0 Conference Paper %B International Conference on Application Specific Array Processors, 1994. Proceedings %D 1994 %T A SIMD solution to the sequence comparison problem on the MGAP %A Borah,M. %A Bajwa,R. S %A Hannenhalli, Sridhar %A Irwin,M. J %K AT-optimal algorithm %K Biological information theory %K biology computing %K biosequence comparison problem %K computational complexity %K Computer science %K Costs %K database size %K Databases %K DNA computing %K dynamic programming %K dynamic programming algorithms %K fine-grained massively parallel processor array %K Genetics %K Heuristic algorithms %K maximally similar sequence %K MGAP parallel computer %K Micro-Grain Array Processor %K Military computing %K molecular biology %K molecular biophysics %K Nearest neighbor searches %K nearest-neighbor connections %K Parallel algorithms %K pipeline processing %K pipelined SIMD solution %K sequence alignment problem %K sequences %X Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128 %B International Conference on Application Specific Array Processors, 1994. Proceedings %I IEEE %P 336 - 345 %8 1994/08/22/24 %@ 0-8186-6517-3 %G eng %R 10.1109/ASAP.1994.331791 %0 Book Section %B Dependable Computing — EDCC-1 %D 1994 %T Software reliability analysis of three successive generations of a Switching System %A Kaâniche,M. %A Kanoun,K. %A Michel Cukier %A Martini,M. %E Echtle,Klaus %E Hammer,Dieter %E Powell,David %K Computer science %X Most current approaches to software reliability evaluation are based on data collected on a single generation of products. However, many applications are developed through improvements of the existing software: to the families of products are added various generations as the need for new functionalities arises. Experimental studies dealing with the analysis of data collected on families of products are seldom reported. In this paper, we analyze the data (failure and correction reports) collected on the software of three successive generations of the Brazilian Switching System — TROPICO-R, during validation and operation. A comparative analysis of the three products is done and the main results are outlined. Emphasis is placed on the evolution of the software and the corresponding failures and corrected faults. The analysis addresses: i) the modifications introduced on system components, ii) the distribution of failures and corrected faults in the components and the functions fulfilled by the system, and iii) the evolution of the failure intensity functions. %B Dependable Computing — EDCC-1 %S Lecture Notes in Computer Science %I Springer Berlin / Heidelberg %V 852 %P 471 - 490 %8 1994/// %@ 978-3-540-58426-1 %G eng %U http://www.springerlink.com/content/f71g30v177521471/abstract/ %0 Conference Paper %B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 %D 1993 %T A distributed algorithm for ear decomposition %A Hannenhalli, Sridhar %A Perumalla,K. %A Chandrasekharan,N. %A Sridhar,R. %K Asynchronous communication %K asynchronous communication network %K Automata %K Communication networks %K computational complexity %K Computer networks %K Computer science %K decomposition graph %K distributed algorithm %K distributed algorithms %K Distributed computing %K Ear %K ear decomposition %K graph theory %K message-optimal %K network decomposition %K sorting %K Testing %K time-optimal %X A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition %B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 %I IEEE %P 180 - 184 %8 1993/05/27/29 %@ 0-8186-4212-2 %G eng %R 10.1109/ICCI.1993.315382 %0 Conference Paper %B , Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92 %D 1992 %T Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs %A Chandrasekharan,N. %A Hannenhalli, Sridhar %K chromatic polynomials %K computational complexity %K Computer science %K graph colouring %K graph theory %K matching polynomial %K Polynomials %K series-parallel graphs %K Terminology %K Tree data structures %K Tree graphs %X The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time %B , Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92 %I IEEE %P 42 - 45 %8 1992/05/28/30 %@ 0-8186-2812-X %G eng %R 10.1109/ICCI.1992.227709 %0 Conference Paper %B Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992 %D 1992 %T Exploratory active vision: theory %A Herve,J. -Y %A Aloimonos, J. %K active observer %K Active shape model %K active vision %K Automation %K autonomous robot %K CAMERAS %K Computer science %K Computer vision %K depth information %K Laboratories %K Layout %K Mobile robots %K Motion analysis %K optical flow %K Robots %K shape from shading %K shape from texture %K shape from x modules %K trajectory module %K Visual system %X An active approach to the integration of shape from x modules-here shape from shading and shape from texture-is proposed. The question of what constitutes a good motion for the active observer is addressed. Generally, the role of the visual system is to provide depth information to an autonomous robot; a trajectory module will then interpret it to determine a motion for the robot, which in turn will affect the visual information received. It is suggested that the motion can also be chosen so as to improve the performance of the visual system %B Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992 %I IEEE %P 10 - 15 %8 1992/06/15/18 %@ 0-8186-2855-3 %G eng %R 10.1109/CVPR.1992.223234 %0 Conference Paper %B , First International Workshop on Interoperability in Multidatabase Systems, 1991. IMS '91. Proceedings %D 1991 %T An algebra and calculus for relational multidatabase systems %A Grant,J. %A Litwin,W. %A Roussopoulos, Nick %A Sellis,T. %K Algebra %K autonomous databases %K Calculus %K Computer networks %K Computer science %K Data models %K Data structures %K Database systems %K database theory %K distributed databases %K Military computing %K multidatabase manipulation language %K multidatabase system %K multirelational algebra %K query languages %K relational algebra %K Relational databases %K Spatial databases %K theoretical foundation %X With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language. The authors propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase %B , First International Workshop on Interoperability in Multidatabase Systems, 1991. IMS '91. Proceedings %I IEEE %P 118 - 124 %8 1991/04// %@ 0-8186-2205-9 %G eng %R 10.1109/IMS.1991.153694 %0 Journal Article %J IEEE Transactions on Knowledge and Data Engineering %D 1991 %T Incremental implementation model for relational databases with transaction time %A Jensen,C. S %A Mark,L. %A Roussopoulos, Nick %K Computational modeling %K Computer science %K Data models %K data retrieval %K Database languages %K Database systems %K database theory %K decremental computations %K deferred update %K Degradation %K differential computation %K historical data %K History %K incremental computations %K Information retrieval %K partitioned storage models %K queries %K relational data model %K Relational databases %K stored views %K Transaction databases %K transaction time %K view materialization %X An implementation model for the standard relational data model extended with transaction time is presented. The implementation model integrates techniques of view materialization, differential computation, and deferred update into a coherent whole. It is capable of storing any view (reflecting past or present states) and subsequently using stored views as outsets for incremental and decremental computations of requested views, making it more flexible than previously proposed partitioned storage models. The working and the expressiveness of the model are demonstrated by sample queries that show how historical data are retrieved %B IEEE Transactions on Knowledge and Data Engineering %V 3 %P 461 - 473 %8 1991/12// %@ 1041-4347 %G eng %N 4 %R 10.1109/69.109107 %0 Conference Paper %B , Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991 %D 1991 %T Parallel transitive closure computations using topological sort %A Hua,K. A %A Hannenhalli, Sridhar %K Computer science %K Concurrent computing %K data partitioning %K Database systems %K database theory %K deductive databases %K File systems %K horizontal partitioning %K joins %K local data fragments %K message passing multiprocessor system %K Multiprocessing systems %K Parallel algorithms %K PARALLEL PROCESSING %K parallel programming %K parallel transitive closure %K processing nodes %K relation tuples %K Relational databases %K sorting %K topological sort %X Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm %B , Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991 %I IEEE %P 122 - 129 %8 1991/12/04/6 %@ 0-8186-2295-4 %G eng %R 10.1109/PDIS.1991.183079 %0 Conference Paper %B , Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS '91 %D 1991 %T A theory of testing for real-time %A Cleaveland, Rance %A Zwarico,A. E %K Algebra %K Character generation %K Computer science %K Delay %K formal logic %K Licenses %K nondeterminism %K Process control %K Protocols %K Real time systems %K real-time %K System testing %K testing preorders %K testing theory %K timed testing %K Timing %K timing behavior %K transition systems %X A framework for generating testing preorders that relate processes on the basis of their timing behavior as well as their degree of relative nondeterminism is developed. The basic concepts of transition systems and testing are reviewed, and timed testing, which takes account of the delay exhibited by a process as it attempts to pass a test, is introduced. The framework is then applied to two different scenarios. In the first, relations are constructed that relate processes on the basis of all timing considerations. In the second, relations are constructed that relate processes on the basis of their relative speeds. In both cases, alternative denotational characterizations of the resulting preorders are presented, and examples are given to illustrate the utility of the approach %B , Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS '91 %I IEEE %P 110 - 119 %8 1991/07/15/18 %@ 0-8186-2230-X %G eng %R 10.1109/LICS.1991.151635 %0 Journal Article %J IEEE Software %D 1991 %T Touch screens now offer compelling uses %A Shneiderman, Ben %K Application software %K Computer aided instruction %K Computer displays %K Computer science %K Cultural differences %K Fingers %K future developments %K information resources %K Marketing and sales %K Mice %K Psychology %K touch screen applications %K touch sensitive screens %K User interfaces %X Research on improving the user interfaces of touch screen applications is described. The advantages of touch screens are discusses, their current capabilities are examined, and possible future developments are considered.<> %B IEEE Software %V 8 %P 93 - 94 %8 1991/03// %@ 0740-7459 %G eng %N 2 %R 10.1109/52.73754 %0 Conference Paper %B , IEEE Conference on Visualization, 1991. Visualization '91, Proceedings %D 1991 %T Tree-maps: a space-filling approach to the visualization of hierarchical information structures %A Johnson,B. %A Shneiderman, Ben %K Computer displays %K Computer Graphics %K Computer science %K Data analysis %K display space %K Educational institutions %K Feedback %K hierarchical information structures %K HUMANS %K Laboratories %K Libraries %K Marine vehicles %K rectangular region %K semantic information %K space-filling approach %K tree-map visualization technique %K trees (mathematics) %K Two dimensional displays %K Visualization %X A method for visualizing hierarchically structured information is described. The tree-map visualization technique makes 100% use of the available display space, mapping the full hierarchy onto a rectangular region in a space-filling manner. This efficient use of space allows very large hierarchies to be displayed in their entirety and facilitates the presentation of semantic information. Tree-maps can depict both the structure and content of the hierarchy. However, the approach is best suited to hierarchies in which the content of the leaf nodes and the structure of the hierarchy are of primary importance, and the content information associated with internal nodes is largely derived from their children %B , IEEE Conference on Visualization, 1991. Visualization '91, Proceedings %I IEEE %P 284 - 291 %8 1991/10/22/25 %@ 0-8186-2245-8 %G eng %R 10.1109/VISUAL.1991.175815 %0 Journal Article %J IEEE Transactions on Software Engineering %D 1991 %T Trie hashing with controlled load %A Litwin,W. A %A Roussopoulos, Nick %A Levy,G. %A Hong,W. %K B-tree file %K Computer science %K controlled load %K Databases %K disk access %K dynamic files %K file organisation %K high load factor %K information retrieval systems %K key search %K load factor %K Military computing %K ordered insertions %K Predictive models %K primary key access method %K Protocols %K random insertions %K TH file %K THCL %K Tree data structures %K trees (mathematics) %K trie hashing %X Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree %B IEEE Transactions on Software Engineering %V 17 %P 678 - 691 %8 1991/07// %@ 0098-5589 %G eng %N 7 %R 10.1109/32.83904 %0 Conference Paper %B Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e %D 1990 %T When is `partial' adequate? A logic-based proof technique using partial specifications %A Cleaveland, Rance %A Steffen,B. %K Calculus %K Carbon capture and storage %K compositional proof rules %K Computer science %K Concurrent computing %K Context %K correctness %K formal specification %K logic-based proof technique %K modal formula %K parallel processes %K partial process specification %K partial specifications %K specification adequacy %K State-space methods %K Technological innovation %X A technique is presented for ascertaining when a (finite-state) partial process specification is adequate, in the sense of being specified enough, for contexts in which it is to be used. The method relies on the automatic generation of a modal formula from the partial specification; if the remainder of the network satisfies this formula, then any process that meets the specification is guaranteed to ensure correct behavior of the overall system. Using the results, the authors develop compositional proof rules for establishing the correctness of networks of parallel processes and illustrate their use with several examples %B Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e %I IEEE %P 440 - 449 %8 1990/06/04/7 %@ 0-8186-2073-0 %G eng %R 10.1109/LICS.1990.113768 %0 Conference Paper %B IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1989. Proceedings CVPR '89 %D 1989 %T 3D object recognition via simulated particles diffusion %A Yacoob,Yaser %A Gold,Y. I %K 3D object recognition %K alignment strategy %K Computational modeling %K Computer science %K data mining %K Gold %K Layout %K Noise shaping %K Object detection %K Object recognition %K parallel projection %K pattern recognition %K point features %K radio access networks %K scene acquisition %K shape characterisation %K Shape measurement %K simulated particles diffusion %K transformation detection %X A novel approach for 3D object recognition is presented. This approach is model-based, and assumes either 3D or 21/2 D scene acquisition. Transformation detection is accomplished along with an object identification (six degrees of freedom, three rotational and three translational, are assumed). The diffusion-like simulation recently introduced as a means for characterization of shape is used in the extraction of point features. The point features represent regions on the object's surface that are extreme in curvature (i.e. concavities and convexities). Object matching is carried out by examining the correspondence between the object's set of point features and the model's set of point features, using an alignment strategy. Triangles are constructed between all possible triples of object's point features, and then are aligned to candidate corresponding triangles of the model's point features. 21/2 range images are transformed into a volumetric representation through a parallel projection onto the 3-D space. The resultant volume is suitable for processing by the diffusion-like simulation %B IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1989. Proceedings CVPR '89 %I IEEE %P 442 - 449 %8 1989/06// %@ 0-8186-1952-x %G eng %R 10.1109/CVPR.1989.37886 %0 Journal Article %J IEEE Transactions on Software Engineering %D 1988 %T An efficient pictorial database system for PSQL %A Roussopoulos, Nick %A Faloutsos,C. %A Sellis,T. %K alphanumeric encodings %K Computer science %K Data structures %K Database languages %K database management systems %K Database systems %K Encoding %K Image coding %K Image databases %K multidimensional B-trees %K Object oriented databases %K pictorial database system %K PSQL %K query language %K query languages %K R+-trees %K Relational databases %K Spatial databases %K spatial objects %K spatial search %K User interfaces %X Pictorial databases require efficient and direct spatial search based on the analog form of spatial objects and relationships instead of search based on some cumbersome alphanumeric encodings of the pictures. A description is given of PSQL, a query language that allows pictorial domains to be presented to the user in their analog form and allows him or her to do direct manipulation on the objects found on those domains. Direct spatial search and computation on the pictures is done using efficient data structures, R- and R+-trees (multidimensional B-trees), which are excellent devices for searching spatial objects and relationships found on pictures %B IEEE Transactions on Software Engineering %V 14 %P 639 - 650 %8 1988/05// %@ 0098-5589 %G eng %N 5 %R 10.1109/32.6141 %0 Journal Article %J IEEE Transactions on Software Engineering %D 1982 %T The Logical Access Path Schema of a Database %A Roussopoulos, Nick %K Aggregation hierarchy %K Calculus %K Computer science %K Data structures %K Databases %K Design optimization %K external logical subschema %K generalization hierarchy %K Information retrieval %K Joining processes %K logical access path %K propositional calculus %K views %X A new schema which models the usage of the logical access paths of the database is proposed. The schema models all database activities (i.e., retrievals and updates), and integrates their logical access paths by recognizing common subpaths and increasing the "weight" of the shared subpaths. The logical access path schema provides a comprehensive picture of the logical access paths, and the cumulative usage of the shared subpaths and/or intermediate results. The schema serves a dual purpose. Firstly, it is used as a model of the access requirements during the database design, and secondly, as the basis for optimization during the operation of the database. %B IEEE Transactions on Software Engineering %V SE-8 %P 563 - 573 %8 1982/11// %@ 0098-5589 %G eng %N 6 %R 10.1109/TSE.1982.235886