Search

A key research interest in the area of Constraint Satisfaction Problems (CSP) is to identify tractable classes of constraints and develop efficient algorithms for solving them. In this paper, we propose an optimal algorithm for solving r-ary min-closed and max-closed constraints. Assuming r = O(1), our algorithm has an optimal running time of O(ct) where c and t are the number of constraints and the maximum size of any constraint, respectively. This significantly improves the existing pairwise consistency based algorithm that takes O(c2t2) time. Moreover, for (binary) connected row convex (CRC) constraints, we design an optimal algorithm for arc consistency that runs in O(cd) time where d is the largest size of any domain. This again improves upon the existing O(cd2) algorithms. This, in turn, leads to a faster algorithm for solving CRC constraints. We also show how our solutions can be applied to determine problems in large distributed IT systems. The experimental evaluation shows that the proposed algorithms are several orders of magnitudes faster than the state-of-the-art algorithms.

Facility location problems aim to identify the best locations to set up new services. The majority of the existing works typically assume that the users are static . However, there exists a wide array of services such as fuel stations, ATMs, food joints, etc., that are widely accessed by mobile users besides the static ones. Such trajectory-aware services should, therefore, factor in the trajectories of its users rather than simply their static locations. In this work, we introduce the problem of optimal placement of facility locations for such trajectory-aware services that minimize the user inconvenience . The inconvenience of a user is the extra distance traveled by her from her regular path to avail a service. We call this the TIPS problem (Trajectory-aware Inconvenience-minimizing Placement of Services) and consider two variants of it. The goal of the first variant, MAX-TIPS, is to minimize the maximum inconvenience faced by any user, while that of the second, AVG-TIPS, is to minimize the average inconvenience over all the users. We show that both these problems are NP-hard, and propose multiple efficient heuristics to solve them. Empirical evaluation on real urban-scale road networks validate the efficiency and effectiveness of the proposed heuristics.

Facility location queries identify the best locations to set up new facilities for providing service to its users. Majority of the existing works in this space assume that the user locations are static. Such limitations are too restrictive for planning many modern real-life services such as fuel stations, ATMs, convenience stores, cellphone base-stations, etc. that are widely accessed by mobile users. The placement of such services should, therefore, factor in the mobility patterns or trajectories of the users rather than simply their static locations. In this work, we introduce the TOPS (Trajectory-Aware Optimal Placement of Services) query that locates the best k sites on a road network. The aim is to optimize a wide class of objective functions defined over the user trajectories. We show that the problem is NP-hard and even the greedy heuristic with an approximation bound of (1-1/e) fails to scale on urban-scale datasets. To overcome this challenge, we develop a multi-resolution clustering based indexing framework called NetClus. Empirical studies on real road network trajectory datasets show that NetClus offers solutions that are comparable in terms of quality with those of the greedy heuristic, while having practical response times and low memory footprints. Additionally, the NetClus framework can absorb dynamic updates in mobility patterns, handle constraints such as site-costs and capacity, and existing services, thereby providing an effective solution for modern urban-scale scenarios., Comment: ICDE 2017 poster

We design and evaluate algorithms for efficient user-mobility driven macro-cell planning in cellular networks. As cellular networks embrace heterogeneous technologies (including long range 3G/4G and short range WiFi, Femto-cells, etc.), most traffic generated by static users gets absorbed by the short-range technologies, thereby increasingly leaving mobile user traffic to macro-cells. To this end, we consider a novel approach that factors in the trajectories of mobile users as well as the impact of city geographies and their associated road networks for macro-cell planning. Given a budget k of base-stations that can be upgraded, our approach selects a deployment that impacts the most number of user trajectories. The generic formulation incorporates the notion of quality of service of a user trajectory as a parameter to allow different application-specific requirements, and operator choices.We show that the proposed trajectory utility maximization problem is NP-hard, and design multiple heuristics. We evaluate our algorithms with real and synthetic data sets emulating different city geographies to demonstrate their efficacy. For instance, with an upgrade budget k of 20%, our algorithms perform 3-8 times better in improving the user quality of service on trajectories in different city geographies when compared to greedy location-based base-station upgrades., Comment: Published in INFOCOM 2015

In this paper, we study the problem of effective route search in road networks. Given a pair of source and destination locations, the aim is to find a path from the source to the destination that visits k different types of sites in a particular order as prescribed by the user. The route planning problem has two objectives to optimize: minimize the total path length and maximize the probability of getting served from the k sites. Since the problem has a multi-objective nature, we utilize the skyline setting and retrieve all skyline paths according to the two aggregated attributes. The naive way of determining the path lengths can involve a large number of shortest path computations. Although the shortest paths between the sites can be pre-computed, the shortest paths from the source to the first type of site and those from the last type of site to the destination cannot be computed in an offline manner as the source and destination are arbitrary points that are available only at runtime. Similarly, the choice and order of the k different types of sites are also specified at runtime only. Since in a large road network, it is prohibitory to compute many shortest paths, we employ a heuristic to approximately solve the problem. The shortest path computation from the source to a site (and similarly, from a site to the destination) is approximated by introducing reference points. The reference points are chosen by employing a grid-based partitioning method on the space underlying the road network. We show that the above heuristic introduces only an additive error to the distance but not to the probability of service while reducing the running times by up to orders of magnitude.

We consider lifetime quality-of-experience (QoE) management for video-on-demand (VoD) users in WiMAX networks. For efficient resource utilization while enhancing user experience, we propose run-time load balancing through joint scheduling among multiple base stations (BSs), referred to as macro scheduling. Macro scheduling employs a utility-maximization approach. To achieve long-term proportional fairness (PF) and manage lifetime QoE, user and flow utilities are modeled as functions of their past service rates, in addition to current channel conditions and bandwidth needs. We show that scheduling flows across multiple BSs jointly to achieve PF is NP-hard in the strong sense. Since approximation algorithms proposed in prior work are computationally expensive for online use, we design efficient heuristics that perform as well as the approximation algorithms. A simulation-based evaluation shows that our overall macro scheduling scheme can improve the number of satisfied users by up to 35% in comparison to other approaches, while only minimally sacrificing on throughput.

Problem determination in a large and dynamic IT service is a challenging task. In this paper we propose a framework for problem determination based on monitoring the event streams generated by the different components of an IT service. We give a generic representation of a problem through spatial-temporal patterns, which is a graph where the vertices capture the location and the time of the matching events, and the edges represent the spatio-temporal conditions between two matching events. The spatial conditions are based on the underlying system topology graph, and the temporal conditions are based on event timestamps.A practical implementation of the above framework will require fast algorithms for detecting patterns. We present efficient algorithms when the pattern graph is a range and a tree, which are then used as building blocks for a hierarchical heuristic for detecting general patterns. Finally, we show that our algorithms perform well in practice through extensive numerical simulations.