HKUST Institutional Repository
(5.016 recursos)
Repository of Hong Kong University of Science and Technology. Managed by the HKUST Library.
Mostrando recursos 1 - 15 de 15
1.
The Number of spanning trees in circulant graphs - Zhang, Yuanping; Yong, Xuerong; Golin, Mordecai J.
In this paper we develop a method for determining the exact number of spanning trees in (directed or undirected) circulant graphs. Using this method we can, for any class of circulant graph, exhibit a recurrence relation for the number of its spanning trees. We describe the method and give examples of its use.
2.
An Algorithm for finding a k-median in a directed tree - Vigneron, Antoine; Gao, Lixin; Golin, Mordecai J.; Italiano, Giuseppe F.; Li, Bo
We consider the problem of ?nding a k-median in a directed tree. We present an algorithm that computes a k-median in O(Pk2) time where k is the number of resources to be placed and P is the path length of the tree. In the case of a balanced tree, this implies O(k2n log n) time, in a random tree O(k2n3/2), while in the worst case O(k2n2). Our method employs dynamic programming and uses O(nk) space, while the best known algorithms for undirected trees require O(n2k) space.
3.
On the expected depth of random circuits - Arya, Sunil; Golin, Mordecai J.; Mehlhorn, Kurt
In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the previously added gates. The depth of the new gate is defined to be one more than the maximal depth of its input gates. We show that the expected depth of a random circuit with n gates is bounded from above by eflnn and from below by 2.04...flnn.
4.
Mellin transforms and asymptotics : the mergesort recurrence - Flajolet, Philippe; Golin, Mordecai J.
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise analysis of the standard top-down recursive mergesort algorithm, in the average case, as well as in the worst and best cases. It also derives the variance and shows that the cost of mergesort has a Gaussian limiting distribution. The approach is applicable to a number of divide-and-conquer recurrences.
5.
On caching effectiveness of web clusters under persistent connections - Tang, Xueyan; Chanson, Samuel T.
Due to the emergence of the HTTP/1.1 standards, persistent connections are increasingly being used in web retrieval. This paper studies the caching performance of web clusters under persistent connections, focusing on the difference between session-grained and request-grained allocation strategies adopted by the web switch. It is shown that the content-based algorithm considerably improves caching performance over the content-blind algorithm at the request-grained level. However, most of the performance gain is offset by the allocation dependency that arises when the content-based algorithm is used at the session-grained level. The performance loss increases with cluster size and connection holding time. An optimization...
6.
Competitive facility location : the Voronoi game - Ahn, Hee-Kap; Cheng, Siu-Wing; Cheong, Otfried; Golin, Mordecai J.; Van Oostrum, Rene
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We also consider a variation where players can play more than one point at a time for the circle arena.
7.
On ?-skeleton as a subgraph of the minimum weight triangulation - Cheng, Siu-Wing; Xu, Yin-Feng
Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S. The weight of the triangulation is the sum of the lengths of the edges. In this paper, we show that for ? > 1/sin k, the ?-skeleton of S is a subgraph of a minimum weight triangulation of S, where k=tan-1(3/?2?3)?? /3.1. There exists a four point example such that the ?-skeleton for ? < 1/sin(? /3) is not a subgraph of the minimun weight triangulation.
8.
Irrelevance and parameter learning in Bayesian networks - Zhang, Nevin Lianwen
It is possible to learn the parameters of a given Bayesian network structure from data because those parameters influence the probability of observing the data. However, some of the parameters are irrelevant to the probability of observing a particular data case. This paper shows how such irrelevancies can be exploited to speedup various algorithms for parameter learning in Bayesian networks.
9.
Latent variable discovery in classification models - Zhang, Nevin Lianwen; Nielsen, Thomas D.; Jensen, Finn V.
The naive Bayes model makes the often unrealistic assumption that the feature variables are mutually independent given the class variable. We interpret a violation of this assumption as an indication of the presence of latent variables, and we show how latent variables can be detected. Latent variable discovery is interesting, especially for medical applications, because it can lead to a better understanding of application domains. It can also improve classification accuracy and boost user confidence in classification models.
10.
Scheduling multimedia documents in a distributed system - Ahmad, Ishfaq; Lai, William Yat Ming; Li, Bo; Deng, Xin
In a client-server based distributed multimedia system, requests for multimedia documents arrive sporadically. These requests must be served by delivering the requested multimedia documents with a fast response time and ensure a certain quality of service. This requires the server to determine the transmission schedule of each multimedia stream while ensuring necessary inter - and intra-stream synchronizations. The multimedia server has to generate schedules in real-time for multiple requests. Therefore, the scheduling algorithm must incur small execution cost. In this paper, we propose a number of dynamic heuristic algorithms. The main feature of our algorithms is that they include an...
11.
Providing information retrieval mechanisms inside a web database server for structured document management - Andres, Frederic; Boulos, Jihad; Lee, Dik Lun; Ono, Kinji
With the growing popularity of the internet and the World Wide Web (web), there is a fast growing demand for access to documents from the Web according to their structure and contents. This paper presents how and why to combine text retrieval mechanisms and Web database server. A realization of a Web database server using text retrieval plug-ins and signature files, based on Phasme is presented and discussed. Phasme is an application-oriented DBMS whose goals are to meet information systems' requirements such as better and faster data access, durability against standards and hardware trends. Phasme as a satellite DBMS, helps...
12.
TUGEN : a tool for automatic test suite generation - Hao, Ruibin; Wu, Jianping; Chanson, Samuel T.
This paper presents a tool called TUGEN which is used for automatic test suite derivation from formal protocol specification. TUGEN is based on a formal model called EBE (External Behaviour Expression) which can be obtained from formal protocol specification in either Estelle or LOTOS . This model specifies only the external behaviour of a protocol in terms of the input/output sequences and their logical (function and predicate) relations. Based on the EBE specification of a protocol, a test sequence derivation method is used to identify associations between inputs and outputs through the interaction paths and their I/O subpaths, then generic...
13.
Multi-dimensional reverse kNN search - Papadias, Dimitris; Tao, Yufei; Lian, Xiang; Xiao, Xiaokui
Given a multi-dimensional point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: they (i) do not support arbitrary values of k, (ii) cannot deal efficiently with database updates, (iii) are applicable only to 2D data but not to higher dimensionality, and (iv) retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact RkNN processing with arbitrary values of k on dynamic, multi-dimensional datasets. Our methods utilize a conventional...
14.
Algorithms for hierarchical spatial reasoning - Papadias, Dimitris; Egenhofer, Max J.
In several applications, there is the need to reason about spatial relations using multiple local frames of reference that are organized hierarchically. This paper focuses on hierarchical reasoning about direction relations, a special class of spatial relations that describe order in space (e.g., north or northeast). We assume a spatial database of points and regions. Points belong to regions, which may recursively be parts of larger regions. The direction relations between points in the same region are explicitly represented (and not calculated from coordinates). Inference mechanisms are applied to extract direction relations between points located in different regions and to...
15.
Valuation of employee reload options in utility maximization framework - Kwok, Yue Kuen; Lau, Ka Wo
The reload provision in an employee stock option is an option enhancement that allows the employee to pay the strike upon exercising the stock option using his owned stocks and to receive new 'reload' stock options. The usual Black-Scholes risk neutral valuation approach cannot be adopted as the pricing vehicle for employee stock options, due to the non-transferability of the ownership of the options and the restriction on short selling of the firm's stocks as hedging strategy. In this paper, we present a general utility maximization frmework to price non-tradeable employee stock options with reload provision. The risk aversion of...
1.
