Journal papers

2021

• [QUESTA21] Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf, Adam Wierman, "Correction to: Multi-Server Queueing Systems with Multiple Priority Classes," Queueing Systems: Theory and Applications, 99(3): 397-398, 2021.  PDF

2017

• • [IBM17] Takayuki Osogami and Sakyasingha Dasgupta, Learning the values of the hyperparameters of a dynamic Boltzmann machine. IBM Journal of Research and Development, 61(4/5), 2017. PDF

    • Abstract The dynamic Boltzmann machine (DyBM) has recently been proposed as a model of an artificial recurrent neural network that can be trained via spike-timing-dependent plasticity, a learning rule that has been postulated and experimentally confirmed for biological neural networks. More specifically, the parameters such as weights and biases of a DyBM can be optimized via this learning “rule” in a way that the likelihood of given time-series data is maximized (i.e., the time-series data are most likely to be generated according to the probability distributions defined by the DyBM with the optimized parameters). However, a DyBM has hyperparameters that need to be tuned by other means. These hyperparameters include the decay rates of eligibility traces and the lengths of first-in-first-out queues. Here, we propose ways to learn the values of the hyperparameters of a DyBM. In particular, we tune the value of the decay rate via a stochastic gradient method with an approximation, to keep the learning time in each step independent of the length of the time-series used for learning. We empirically demonstrate the effectiveness of the proposed approaches in the settings of predicting sequential patterns, including music.

2015

• • [SREP15] Takayuki Osogami and Makoto Otsuka, Seven neurons memorizing sequences of alphabetical images via spike-timing dependent plasticity. Sci. Rep. 5, 14149; doi: 10.1038/srep14149 (2015).  http://www.nature.com/articles/srep14149

    • Abstract An artificial neural network, such as a Boltzmann machine, can be trained with the Hebb rule so that it stores static patterns and retrieves a particular pattern when an associated cue is presented to it. Such a network, however, cannot effectively deal with dynamic patterns in the manner of living creatures. Here, we design a dynamic Boltzmann machine (DyBM) and a learning rule that has some of the properties of spike-timing dependent plasticity (STDP), which has been postulated for biological neural networks. We train a DyBM consisting of only seven neurons in a way that it memorizes the sequence of the bitmap patterns in an alphabetical image “SCIENCE” and its reverse sequence and retrieves either sequence when a partial sequence is presented as a cue. The DyBM is to STDP as the Boltzmann machine is to the Hebb rule.

  • [QUESTA15] Takayuki Osogami and Rudy Raymond, "Erratum to: Analysis of transient queues with semidefinite optimization," Queueing Systems, 80(4): 387-388, 2015. PDF

2013

• • [IRDJ13] Takayuki Osogami, Takashi Imamichi, Hideyuki Mizuta, Toyotaro Suzumura, and Tsuyoshi Ide, "Toward simulating entire cities with behavioral models of traffic," IBM Journal of Research and Development, 57(5): Paper 6, 2013. PDF

    • Abstract Resilient transportation systems enable quick evacuation, rescue, distribution of relief supplies, and other activities for reducing the impact of natural disasters and for accelerating the recovery from them. The resilience of a transportation system largely relies on the decisions that we make when we face a natural disaster. We develop an agent-based traffic simulator for predicting the results of potential actions taken with respect to the transportation system to quickly make appropriate decisions. For realistic simulation, we govern the behavior of individual drivers of vehicles with the foundational principles that we learn from probe-car data. For example, we use the probe-car data to estimate the personality of individual drivers of vehicles in selecting their routes, taking into account various metrics of routes such as travel time, travel distance, and the number of turns. This behavioral model constructed from real data constitutes a unique feature of our simulator. We built this simulator using the X10 language, which enables massively parallel execution, for simulating traffic in a large metropolitan area. We report the use cases of the simulator in three major cities in the context of disaster recovery and resilient transportation.

  • [JMI13] Takayuki Osogami, Tomoyuki Shirai, and Hayato Waki, "Remarks on positivity of alpha-determinants via SDP relaxation," Journal of Math-for-Industry, 5:1-10, 2013. PDF

    • Abstract After we survey our positivity problem for alpha-determinants of matrices, we reformulate it as polynomial optimization problems. By using SDP relaxation, we perform numerical computation for these optimization problems. We also give SOS representations for the alpha-determinants to obtain the optimal value when the matrix size n = 3, and give conjectures for n = 4, 5.

  • [QUESTA13] Takayuki Osogami and Rudy Raymond, "Analysis of transient queues with semidefinite optimization", Queueing Systems: Theory and Applications, 73(2):195-234, 2013.  PDF

    • Abstract We derive upper bounds on the tail distribution of the transient waiting time in the GI/GI/1 queue, given a truncated sequence of the moments of the service time and that of the interarrival time. Our upper bound is given as the objective value of the optimal solution to a semidefinite program (SDP) and can be calculated numerically by solving the SDP. We also derive the upper bounds in closed form for the case when only the first two moments of the service time and those of the interarrival time are given. The upper bounds in closed form are constructed by formulating the dual problem associated with the SDP. Specifically, we obtain the objective value of a feasible solution of the dual problem in closed from, which turns out to be the upper bound that we derive. In addition, we study bounds on the maximum waiting time in the first busy period.

2011

• • [QUEATA11] Varun Gupta and Takayuki Osogami, "On Markov-Krein Characterization of the Mean Waiting Time in M/G/K and Other Queueing Systems", Queueing Systems: Theory and Applications (special issue on open problems), 68(3): 339-352, 2011. An extended version available as a technical report: PDF

    • Abstract We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems—via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov–Krein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.

2010

• • [PE10] Takayuki Osogami, "Differentiating the performance of systems more reliably," Performance Evaluation, 67(10): 929-945, 2010. Three invited talks are given on this topic.  Original version available as technical report: PDF

    • Abstract The system of measuring the performance of a Web system using a workload generator can be modeled as a closed interactive system. In such a system, the throughput and the mean response time are related by the response time law. However, we find that a measured throughput and a corresponding measured mean response time can have significantly different accuracy. As a result, one metric may be more reliable than the other to identify the better of two given configurations of a Web system, which is an important problem that appears frequently in practice. Using simulation, we derive rules of thumb that characterize when throughput is more reliable than mean response time. Also, we explain these rules of thumb analytically. Specifically, we refine the response time law using the central limit theorem and formally define the asymptotic reliability of an estimator of a metric. Using these analytical frameworks, we provide insights into when and why one metric is more reliable than the other.

  • [AAP10] Takayuki Osogami, "A fluid limit for a cache algorithm with general request processes," Advances in Applied Probability, 42(3):1-18, 2010. Original version available as technical report: PDF

    • Abstract We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the Least-Recently-Used algorithm when requests are issued according to general stochastic point processes.  We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes when the number of replications approaches infinity.  We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit.  We show that, when requests follow inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system.  Also, we compare the asymptotic characteristics, as the cache size approaches infinity, of the average miss probability in the fluid limit to those in the original system.

  • [OR10] Ryo Hirade and Takayuki Osogami, "Analysis of page replacement policies in the fluid limit," Operations Research, 58(4):971-984, 2010. Original version available as technical report: PDF

    • Abstract The performance of storage systems and database systems depends significantly on the page replacement policies. Although many page replacement policies have been discussed in the literature, their performances are not fully understood. We introduce analytical techniques for evaluating the performances of page replacement policies including two queue (2Q), which manages two buffers to capture both the recency and frequency of requests. We derive an exact expression for the probability that a requested item is found (the hit probability) in a buffer managed by 2Q in the fluid limit, where the number of items is scaled by n, the size of items is scaled by 1/n, and n approaches infinity. The hit probability in the fluid limit approximates the hit probability in the original system, and we find that the relative error in the approximation is typically within 1%. Our analysis also illuminates several fundamental properties of 2Q useful for system designers.

2009

• • [TOMACS09] Takayuki Osogami, "Finding probably best systems quickly via simulations," ACM Transactions on Modeling and Computer Simulation, 19(3):Article No. 12, 2009.  PDF  Awarded Bunken-sho Shorei-sho (an award for an outstanding paper written by a young reseacher) from Operations Research Society of Japan, Mar. 2010.

    • Abstract We propose an indifference-zone approach for a ranking and selection problem with the goal of reducing both the number of simulated samples of the performance and the frequency of configuration changes. We prove that with a prespecified high probability, our algorithm finds the best system configuration. Our proof hinges on several ideas, including the use of Anderson's probability bound, that have not been fully investigated for the ranking and selection problem. Numerical experiments show that our algorithm can select the best system configuration using up to 50% fewer simulated samples than existing algorithms without increasing the frequency of configuration changes.

2006

• • [PE06b] Adam Wierman, Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "How many servers are best in a dual-priority M/PH/k system?," Performance Evaluation, 63(12):1253-1272, 2006.  Preprint: PDF

    • Abstract We ask the question, "for minimizing mean response time (sojourn time), which is preferable: one fast server of speed 1, or k slow servers each of speed 1/k?" Our setting is the View the MathML source system with two priority classes of customers, high priority and low priority, where PH is a phase-type distribution. We find that multiple slow servers are often preferable, and we demonstrate exactly how many servers are preferable as a function of the load and service time distribution. In addition, we find that the optimal number of servers with respect to the high priority jobs may be very different from that preferred by low priority jobs, and we characterize these preferences. We also study the optimal number of servers with respect to overall mean response time, averaged over high and low priority jobs. Lastly, we ascertain the effect of the service demand variability of high priority jobs on low priority jobs. 

  • [PE06a] Takayuki Osogami and Mor Harchol-Balter, "Closed form solutions for mapping general distributions to quasi-minimal PH distributions," Performance Evaluation, 63(6):524-552, 2006.  Special issue for the selected best papers of TOOLS 2003.  Preprint: PDF

    • Abstract Approximating general distributions by phase-type (PH) distributions is a popular technique in stochastic analysis, since the Markovian property of PH distributions often allows analytical tractability. This paper proposes an algorithm for mapping a general distribution, G, to a PH distribution, which matches the first three moments of G. Efficiency of our algorithm hinges on narrowing the search space to a particular subset of the PH distributions, which we refer to as Erlang–Coxian (EC) distributions. The class of EC distributions has a small number of parameters, and we provide closed form solutions for these. Our solution applies to any distribution whose first three moments can be matched by a PH distribution. Also, our resulting EC distribution requires a nearly minimal number of phases, within one of the minimal number of phases required by any acyclic PH distribution.

2005

• • [QUESTA05] Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf, and Adam Wierman, "Multi-server queueing systems with multiple priority classes," Queueing Systems: Theory and Applications, 51(3-4):331-360, 2005.  Preprint: PDF

    • Abstract We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution.

Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes--"smart" prioritization (giving priority to the smaller jobs) versus "stupid" prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes.

• • • ERRATA

      • Section 2.2 (page 340), matrix B^{(\ell)}: the diagonal elements should be corrected from (min{2,\ell}, 1, 0, ...) to (min{2,\ell}, 1, 1, 0,...).

      • Section 2.2 (page 341), matrix L^{(\ell)}: \lambda_M and \lambda_H should be switched with each other in the (1, 4) block and (1, 5) block.

  • [PE05] Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "Analysis of cycle stealing with switching costs and thresholds," Performance Evaluation, 61(4): 347-369, 2005.  Preprint: PDF

    • Abstract We consider two processors, each serving its own M/GI/1 queue, where one of the processors (the “donor”) can help the other processor (the “beneficiary”) with its jobs, during times when the donor processor is idle. That is the beneficiary processor “steals idle cycles” from the donor processor. There is a switching time required for the donor processor to start working on the beneficiary jobs, as well as a switching back time. We also allow for threshold constraints on both the beneficiary and donor sides, whereby the decision to help is based not only on idleness but also on satisfying threshold criteria in the number of jobs.

    • We analyze the mean response time for the donor and beneficiary processors. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate principles on the general benefits of cycle stealing and the design of cycle stealing policies.

2003

• • [HEUR03] Takayuki Osogami and Hiroyuki Okano, "Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics," Journal of Heuristics, 9: 29-49, 2003.  Preprint: PDF

    • Abstract The tradeoff between the speed and quality of the solutions obtained by various construction and local search algorithms for the elementary bin packing problem (BPP) are analyzed to obtain useful information for designing algorithms for real-world problems that can be modeled as BPPs. On the basis of intensive computational experiments, we observe that the framework of a solution (i.e., a part of a solution consisting of large items or items with tight constraints) should be constructed in the early stages of a local search. New local search algorithms are proposed as empirical support for the observation.