Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

PDF

Selected Works

2010

Discipline
Institution
Keyword
Publication

Articles 31 - 60 of 771

Full-Text Articles in Physical Sciences and Mathematics

Constrained Shortest Path Computation, Manolis Terrovitis, Spiridon Bakiras, Dimitris Papadias, Kyriakos Mouratidis Dec 2010

Constrained Shortest Path Computation, Manolis Terrovitis, Spiridon Bakiras, Dimitris Papadias, Kyriakos Mouratidis

Kyriakos MOURATIDIS

This paper proposes and solves a-autonomy and k-stops shortest path problems in large spatial databases. Given a source s and a destination d, an aautonomy query retrieves a sequence of data points connecting s and d, such that the distance between any two consecutive points in the path is not greater than a. A k-stops query retrieves a sequence that contains exactly k intermediate data points. In both cases our aim is to compute the shortest path subject to these constraints. Assuming that the dataset is indexed by a data-partitioning method, the proposed techniques initially compute a sub-optimal path by …

Go to article

Optimal Matching Between Spatial Datasets Under Capacity Constraints, Hou U Leong, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis Dec 2010

Optimal Matching Between Spatial Datasets Under Capacity Constraints, Hou U Leong, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis

Kyriakos MOURATIDIS

Consider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The capacity constrained assignment (CCA) is a matching between the two sets such that (i) each customer is assigned to at most one provider, (ii) every provider serves no more customers than its capacity, (iii) the maximum possible number of customers are served, and (iv) the sum of Euclidean distances within the assigned provider-customer pairs is minimized. Although max-flow algorithms are applicable …

Go to article

Capacity Constrained Assignment In Spatial Databases, Hou U Leong, Man Lung Yiu, Kyriakos Mouratidis, Nikos Mamoulis Dec 2010

Capacity Constrained Assignment In Spatial Databases, Hou U Leong, Man Lung Yiu, Kyriakos Mouratidis, Nikos Mamoulis

Kyriakos MOURATIDIS

Given a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q 2 Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M Q × P such that (i) each point q 2 Q (p 2 P) appears at most k times (at most nce) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|,P q2Q q.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs) is minimized. Thus, the CCA problem is …

Go to article

Continuous Nearest Neighbor Monitoring In Road Networks, Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis Dec 2010

Continuous Nearest Neighbor Monitoring In Road Networks, Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis

Kyriakos MOURATIDIS

Recent research has focused on continuous monitoring of nearest neighbors (NN) in highly dynamic scenarios, where the queries and the data objects move frequently and arbitrarily. All existing methods, however, assume the Euclidean distance metric. In this paper we study k-NN monitoring in road networks, where the distance between a query and a data object is determined by the length of the shortest path connecting them. We propose two methods that can handle arbitrary object and query moving patterns, as well as °uctuations of edge weights. The ¯rst one maintains the query results by processing only updates that may invalidate …

Go to article

Continuous Spatial Assignment Of Moving Users, Leong Hou U, Kyriakos Mouratidis, Nikos Mamoulis Dec 2010

Continuous Spatial Assignment Of Moving Users, Leong Hou U, Kyriakos Mouratidis, Nikos Mamoulis

Kyriakos MOURATIDIS

Consider a set of servers and a set of users, where each server has a coverage region (i.e., an area of service) and a capacity (i.e., a maximum number of users it can serve). Our task is to assign every user to one server subject to the coverage and capacity constraints. To offer the highest quality of service, we wish to minimize the average distance between users and their assigned server. This is an instance of a well-studied problem in operations research, termed optimal assignment. Even though there exist several solutions for the static case (where user locations are fixed), …

Go to article

Continuous Monitoring Of Spatial Queries, Kyriakos Mouratidis Dec 2010

Continuous Monitoring Of Spatial Queries, Kyriakos Mouratidis

Kyriakos MOURATIDIS

No abstract provided.

Go to article

Continuous Monitoring Of Top-K Queries Over Sliding Windows, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias Dec 2010

Continuous Monitoring Of Top-K Queries Over Sliding Windows, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias

Kyriakos MOURATIDIS

Given a dataset P and a preference function f, a top-k query retrieves the k tuples in P with the highest scores according to f. Even though the problem is well-studied in conventional databases, the existing methods are inapplicable to highly dynamic environments involving numerous long-running queries. This paper studies continuous monitoring of top-k queries over a fixed-size window W of the most recent data. The window size can be expressed either in terms of the number of active tuples or time units. We propose a general methodology for top-k monitoring that restricts processing to the sub-domains of the workspace …

Go to article

Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis Dec 2010

Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis

Kyriakos MOURATIDIS

Shortest path computation is one of the most common queries in location-based services that involve transportation net- works. Motivated by scalability challenges faced in the mo- bile network industry, we propose adopting the wireless broad- cast model for such location-dependent applications. In this model the data are continuously transmitted on the air, while clients listen to the broadcast and process their queries locally. Although spatial problems have been considered in this environment, there exists no study on shortest path queries in road networks. We develop the rst framework to compute shortest paths on the air, and demonstrate the practicality and …

Go to article

A Threshold-Based Algorithm For Continuous Monitoring Of K Nearest Neighbors, Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, Yufei Tao Dec 2010

A Threshold-Based Algorithm For Continuous Monitoring Of K Nearest Neighbors, Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, Yufei Tao

Kyriakos MOURATIDIS

Assume a set of moving objects and a central server that monitors their positions over time, while processing continuous nearest neighbor queries from geographically distributed clients. In order to always report up-to-date results, the server could constantly obtain the most recent position of all objects. However, this naïve solution requires the transmission of a large number of rapid data streams corresponding to location updates. Intuitively, current information is necessary only for objects that may influence some query result (i.e., they may be included in the nearest neighbor set of some client). Motivated by this observation, we present a threshold-based algorithm …

Go to article

Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu Dec 2010

Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu

Kyriakos MOURATIDIS

Research on spatial network databases has so far considered that there is a single cost value associated with each road segment of the network. In most real-world situations, however, there may exist multiple cost types involved in transportation decision making. For example, the different costs of a road segment could be its Euclidean length, the driving time, the walking time, possible toll fee, etc. The relative significance of these cost types may vary from user to user. In this paper we consider such multi-cost transportation networks (MCN), where each edge (road segment) is associated with multiple cost values. We formulate …

Go to article

Is Solution For The Global Environmental Challenge: An Australian Initiative, Trevor A. Spedding, Aditya K. Ghose, Helen M. Hasan Dec 2010

Is Solution For The Global Environmental Challenge: An Australian Initiative, Trevor A. Spedding, Aditya K. Ghose, Helen M. Hasan

Trevor Spedding

There is a complex range of interrelated environmental issues that currently challenge decision-makers across the world. To date the reputation of the information and communication technology (ICT) industry in Australia, and elsewhere, has been quite negative with respect to its effect on the environment. The recent "Green IT" initiatives of the Australian Computer Society to reduce carbon emission are manifestations of this. While not denying the worth of this agenda, the authors of this paper suggest that it is timely to promote a more positive position for ICT as a source of solutions to environmental problems. In this paper, we …

Go to article

Carbon-Centric Computing: It Solutions For Climate Change, Aditya K. Ghose, Helen M. Hasan, T. Spedding Dec 2010

Carbon-Centric Computing: It Solutions For Climate Change, Aditya K. Ghose, Helen M. Hasan, T. Spedding

Trevor Spedding

IT has a role to play in the current debate on climate change. The current discourse on IT and climate change views IT in a negative light, as a polluter. What remains unrecognized is the critical role of IT as a source of solutions to the climate change problem. We live in a massive, inter-connected Planet Earth Supply Chain. IT provides a range of tools to model, manage and optimize this supply chain. The University of Wollongong Carbon-Centric Computing Initiative (CCCI) seeks to seed a program of research that addresses the climate change problem with a range of computing technologies …

Go to article

Retinylidene Iminium Salts And Related Systems, Gary Stephen Shaw Dec 2010

Retinylidene Iminium Salts And Related Systems, Gary Stephen Shaw

Gary M. Shaw

This thesis encompasses some investigations into the structure and chemistry of iminium salts. The interest in this work stems from previous investigations of the visual pigment rhodopsin and a related protein, bacteriorhodopsin. Both of these proteins have been shown to consist of an iminium salt linkage between the chromophore and the protein. Also, these compounds are able to absorb light in the visible region of the spectrum and undergo efficient isomerization processes. A series of iminium salts related to these natural chromophores were prepared and characterized by a variety of spectroscopic methods in both solution and the solid states. In …

Go to article

Evaluation Of A Novel Two-Step Server Selection Metric, Katrina M. Hanna, Nandini Natarajan, Brian Neil Levine Dec 2010

Evaluation Of A Novel Two-Step Server Selection Metric, Katrina M. Hanna, Nandini Natarajan, Brian Neil Levine

Brian Levine

Choosing the best-performing server for a particular client from a group of replicated proxies is a difficult task. We offer a novel, two-step technique for server selection that chooses a small subset of five servers, and isolates testing to that subset for ten days. We present an empirical evaluation of both our method and previously proposed metrics based on traces to 193 commercial proxies. We show that our technique performs better than any of the other metrics we studied — often one to two seconds better for a one-megabyte file — while requiring considerably less work over time. Metrics such …

Go to article

Dtn Routing As A Resource Allocation Problem, Aruna Balasubramanian, Brian Neil Levine, Arun Venkataramani Dec 2010

Dtn Routing As A Resource Allocation Problem, Aruna Balasubramanian, Brian Neil Levine, Arun Venkataramani

Brian Levine

Routing protocols for disruption-tolerant networks (DTNs) use a variety of mechanisms, including discovering the meeting probabilities among nodes, packet replication, and network coding. The primary focus of these mechanisms is to increase the likelihood of finding a path with limited information, and so these approaches have only an incidental effect on routing such metrics as maximum or average delivery delay. In this paper, we present rapid, an intentional DTN routing protocol that can optimize a specific routing metric such as the worst-case delivery delay or the fraction of packets that are delivered within a deadline. The key insight is to …

Go to article

Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine Dec 2010

Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine

Brian Levine

Disruption Tolerant Networks (DTNs) require routing algorithms that are different from those designed for ad hoc networks. In DTNs, transport of data through the network is achieved through the physical movement of the participants in the network. We address two fundamental problems of routing in DTNs: routing algorithms with robust delivery rates, and management of networks where demand for routes does not match with the movement of peers. For the first problem, we propose the MV algorithm, which is based on observed meetings between peers and visits of peers to geographic locations. We show that our approach can achieve robust …

Go to article

Interactive Wifi Connectivity For Moving Vehicles, Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, John Zahorjan Dec 2010

Interactive Wifi Connectivity For Moving Vehicles, Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, John Zahorjan

Brian Levine

We ask if the ubiquity of WiFi can be leveraged to provide cheap connectivity from moving vehicles for common applications such as Web browsing and VoIP. Driven by this question, we conduct a study of connection quality available to vehicular WiFi clients based on measurements from testbeds in two different cities. We find that current WiFi handoff methods, in which clients communicate with one basestation at a time, lead to frequent disruptions in connectivity. We also find that clients can overcome many disruptions by communicating with multiple basestations simultaneously. These findings lead us to develop ViFi, a protocol that opportunistically …

Go to article

Mobile Distributed Information Retrieval For Highly-Partitioned Networks, Katrina M. Hanna, Brian Neil Levine, R. Manmatha Dec 2010

Mobile Distributed Information Retrieval For Highly-Partitioned Networks, Katrina M. Hanna, Brian Neil Levine, R. Manmatha

Brian Levine

We propose and evaluate a mobile, peer-to-peer Information Retrieval system. Such a system can, for example, support medical care in a disaster by allowing access to a large collections of medical literature. In our system, documents in a collection are replicated in an overlapping manner at mobile peers. This provides resilience in the face of node failures, malicious attacks, and network partitions. We show that our design manages the randomness of node mobility. Although nodes contact only direct neighbors (who change frequently) and do not use any ad hoc routing, the system maintains good IR performance. This makes our design …

Go to article

Proto-Transfer Learning In Markov Decision Processes Using Spectral Methods, Kimberly Ferguson, Sridhar Mahadevan Dec 2010

Proto-Transfer Learning In Markov Decision Processes Using Spectral Methods, Kimberly Ferguson, Sridhar Mahadevan

Sridhar Mahadevan

In this paper we introduce proto-transfer leaning, a new framework for transfer learning. We explore solutions to transfer learning within reinforcement learning through the use of spectral methods. Proto-value functions (PVFs) are basis functions computed from a spectral analysis of random walks on the state space graph. They naturally lead to the ability to transfer knowledge and representation between related tasks or domains. We investigate task transfer by using the same PVFs in Markov decision processes (MDPs) with different rewards functions. Additionally, our experiments in domain transfer explore applying the Nyström method for interpolation of PVFs between MDPs of different …

Go to article

Learning To Communicate And Act Using Hierarchical Reinforcement Learning, Mohammad Ghavamzadeh, Sridhar Mahadevan Dec 2010

Learning To Communicate And Act Using Hierarchical Reinforcement Learning, Mohammad Ghavamzadeh, Sridhar Mahadevan

Sridhar Mahadevan

In this paper, we address the issue of rational communication behavior among autonomous agents. The goal is for agents to learn a policy to optimize the communication needed for proper coordination, given the communication cost. We extend our previously reported cooperative hierarchical reinforcement learning (HRL) algorithm to include communication decisions and propose a new multiagent HRL algorithm, called COM-Cooperative HRL. In this algorithm, we define cooperative subtasks to be those subtasks in which coordination among agents significantly improves the performance of the overall task. Those levels of the hierarchy which include cooperative subtasks are called cooperation levels. Coordination skills among …

Go to article

Hierarchical Policy Gradient Algorithms, Mohammad Ghavamzadeh, Sridhar Mahadevan Dec 2010

Hierarchical Policy Gradient Algorithms, Mohammad Ghavamzadeh, Sridhar Mahadevan

Sridhar Mahadevan

Hierarchical reinforcement learning is a general framework which attempts to accelerate policy learning in large domains. On the other hand, policy gradient reinforcement learning (PGRL) methods have received recent attention as a means to solve problems with continuous state spaces. However, they su#11;er from slow convergence. In this paper, we combine these two approaches and propose a family of hierarchical policy gradi- ent algorithms for problems with continuous state and/or action spaces. We also introduce a class of hierarchical hybrid algorithms, in which a group of subtasks, usually at the higher-levels of the hierarchy, are formulated as value function-based RL …

Go to article

Manifold Alignment Using Procrustes Analysis, Chang Wang, Sridhar Mahadevan Dec 2010

Manifold Alignment Using Procrustes Analysis, Chang Wang, Sridhar Mahadevan

Sridhar Mahadevan

In this paper we introduce a novel approach to manifold alignment, based on Procrustes analysis. Our approach di®ers from \semi- supervised alignment" in that it results in a mapping that is de¯ned everywhere { when used with a suitable dimensionality reduction method { rather than just on the training data points. We describe and evaluate our approach both theoretically and experimen- tally, providing results showing useful knowl- edge transfer from one domain to another. Novel applications of our method including cross-lingual information retrieval and trans- fer learning in Markov decision processes are presented.

Go to article

Framework For Analyzing Garbage Collection, Matthew Hertz, Neil Immerman, J. Eliot B. Moss Dec 2010

Framework For Analyzing Garbage Collection, Matthew Hertz, Neil Immerman, J. Eliot B. Moss

Neil Immerman

While the design of garbage collection algorithms has come of age, the analysis of these algorithms is still in its infancy. Current analyses are limited to merely documenting costs of individual collector executions; conclusive results, measuring across entire programs, require a theoretical foundation from which proofs can be offered. A theoretical foundation also allows abstract examination of garbage collection, enabling new designs without worrying about implementation details. We propose a theoretical framework for analyzing garbage collection algorithms and show how our framework could compute the ef#2;ciency (time cost) of garbage collectors. The central novelty of our proposed framework is its …

Go to article

A Control Architecture Formulti-Modal Sensory Integration, Luiz M. G. Gonçalves, Roderic A. Grupen, Antonio A. F. Oliveira Dec 2010

A Control Architecture Formulti-Modal Sensory Integration, Luiz M. G. Gonçalves, Roderic A. Grupen, Antonio A. F. Oliveira

Roderic Grupen

This work describes the architecture of an integrated multi-modal sensory (vision and touch) computational system. We propose to use an approach based on robotics control theory that is motivated by biology and developmental psychology, in order to integrate the haptic and visual information processing. We show some results carried out in simulation and discuss the implementation of this system using a platform consisting on an articulated stereo-head and an arm, which is currently under development.

Go to article

Capturing Data Uncertainty In Highvolume Stream Processing, Yanlei Diao, Boduo Li, Anna Liu, Liping Peng, Charles Sutton, Thanh Tran, Michael Zink Dec 2010

Capturing Data Uncertainty In Highvolume Stream Processing, Yanlei Diao, Boduo Li, Anna Liu, Liping Peng, Charles Sutton, Thanh Tran, Michael Zink

Yanlei Diao

We present the design and development of a data stream system that captures data uncertainty from data collection to query processing to final result generation. Our system focuses on data that is naturally modeled as continuous random variables such as many types of sensor data. To provide an end-to-end solution, our system employs probabilistic modeling and inference to generate uncertainty description for raw data, and then a suite of statistical techniques to capture changes of uncertainty as data propagates through query operators. To cope with high-volume streams, we explore advanced approximation techniques for both space and time efficiency. We are …

Go to article

Flux: A Language For Programming High-Performance Servers, Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D. Berger, Mark D. Corner Dec 2010

Flux: A Language For Programming High-Performance Servers, Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D. Berger, Mark D. Corner

Mark Corner

Programming high-performance server applications is challenging: it is both complicated and error-prone to write the concurrent code required to deliver high performance and scalability. Server performance bottlenecks are difficult to identify and correct. Finally, it is difficult to predict server performance prior to deployment. This paper presents Flux, a language that dramatically simplifies the construction of scalable high-performance server applications. Flux lets programmers compose offthe- shelf, sequential C or C++ functions into concurrent servers. Flux programs are type-checked and guaranteed to be deadlock-free. We have built a number of servers in Flux, including a web server with PHP support, an …

Go to article

Improving The Accuracy Of Petri Net-Based Analysis Of Concurrent Programs, A. T. Chamillard, Lori A. Clarke Dec 2010

Improving The Accuracy Of Petri Net-Based Analysis Of Concurrent Programs, A. T. Chamillard, Lori A. Clarke

Lori Clarke

Spurious results are an inherent problem of most static analysis methods. These methods, in an effort to produce conservative results, overestimate the executable behavior of a program. Infeasible paths and imprecise alias resolution are the two causes of such inaccuracies. In this paper we present an approach for improving the accuracy of Petri net-based analysis of concurrent programs by including additional program state information in the Petri net. We present empirical results that demonstrate the improvements in accuracy and, in some cases, the reduction in the search space that result from applying this approach to concurrent Ada programs.

Go to article

Model-Based Motion Planning, Brendan Burns, Oliver Brock Dec 2010

Model-Based Motion Planning, Brendan Burns, Oliver Brock

Oliver Brock

Robotic motion planning requires configuration space exploration. In high-dimensional configuration spaces, a complete exploration is computationally intractable. To devise practical motion planning algorithms in such high-dimensional spaces, computational resources have to be expended in proportion to the local complexity of a configuration space region. We propose a novel motion planning approach that addresses this problem by building an incremental, approximate model of configuration space. The information contained in this model is used to direct computational resources to difficult regions. This effectively addresses the narrow passage problem by adapting the sampling density to the complexity of that region. Each sample of …

Go to article

Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine Dec 2010

Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine

Oliver Brock

Disruption Tolerant Networks (DTNs) require routing algorithms that are different from those designed for ad hoc networks. In DTNs, transport of data through the network is achieved through the physical movement of the participants in the network. We address two fundamental problems of routing in DTNs: routing algorithms with robust delivery rates, and management of networks where demand for routes does not match with the movement of peers. For the first problem, we propose the MV algorithm, which is based on observed meetings between peers and visits of peers to geographic locations. We show that our approach can achieve robust …

Go to article

Sampling-Based Motion Planning Using Predictive Models, Brendan Burns, Oliver Brock Dec 2010

Sampling-Based Motion Planning Using Predictive Models, Brendan Burns, Oliver Brock

Oliver Brock

Robotic motion planning requires configuration space exploration. In high-dimensional configuration spaces, a complete exploration is computationally intractable. Practical motion planning algorithms for such high-dimensional spaces must expend computational resources in proportion to the local complexity of configuration space regions. We propose a novel motion planning approach that addresses this problem by building an incremental, approximate model of configuration space. The information contained in this model is used to direct computational resources to difficult regions, effectively addressing the narrow passage problem by adapting the sampling density to the complexity of that region. In addition, the expressiveness of the model permits predictive …

Go to article

First Prev Next Last