27932771
Novel algorithms for multicast communication in self-routing MIN-based ATM switches
We discuss the multicast communication in the self-routing multistage interconnection network (MIN) for constructing the internal architecture of asynchronous transfer mode (ATM) switches. Many applications of ATM switches require multicast communications in addition to conventional point-to-point communications. This paper presents a novel approach to supporting multicast communication, on the basis of the recursive scheme that recycles a multicast packet one or more times through the network to reach at desired destinations. We also propose cost-effective multicast algorithms providing deadlock-freedom in MIN-based ATM switches. The proposed algorithms require a small and fixed number of recycling passes and a reasonable number of links used. The proposed algorithms can be easily applicable to buffered MIN-based ATM switches.
3145493
KPSP: A Knowledge Programming System based on Prolog
1326236
History Sensitive String for Multiple Alphabets
In most cases, to represent characters in a computer, conventional code systems such as ASCII, EBCDIC, or BCD, whose code-length is uniform, have been used. In some countries, where the native language is not English, people can easily adapt their alphabet to these code systems by simply replacing the Enghsh alphabet with the alphabet of their native language. In other countries, especially in Korea and Japan, a straightforward application of the conventional code system is not possible. This is because, to compose a sentence, people customarily intermix words each of which may be constructed by different alphabets. For example, in Korea, they have an alphabet for their native language called Hangul. Hangul is a complete language by which Koreans can communicate with each other. However, Korean culture was influenced by China and more recently by the western countries. This results in widespread usage of four different types of documents in Korea. Documents may be written in Hangul only, Hangul with Chinese words, Hangul with English words, and Hangul with both Chinese and English words. Even in these cases, Hangul is the main alphabet. Another example of the applications of multiple alphabets in a single text are the high level language programs in Korean environment where the program language is a popular high level language such as PASCAL, C, or LISP, but variable names or data in the program may consist of Korean characters [7,9]. In this case, the main alphabet is English. Another example using heterogeneous characters is the use of attributes such as color, size, or font in high quality text editors. In such cases, characters from multiple alphabets should be used in a computer. Since each alphabet may have characteristics different from each other, some coding methods for multiple alphabets can be considered. When the sizes of the alphabets are significantly different from each other, employment of codes of a uniform length is prohibitively expensive. There are two different techniques to encode the multiple alphabets into a single code system. In the following sections, two coding methods of multiple alphabets are generalized, and their advantages and disadvantages are analyzed.
39501622
A logic programming approach to hybrid knowledge representation
A new hybrid system called Sphinx is presented which combines classification-based reasoning with logic programming technique. It consists of two major components: a terminological component and an assertional one. The former uses a frame-based knowledge representation scheme based on classification and the latter is a theorem prover based on Horn logic. The assertional component can also handle a first-order query language and wh-questions. A new knowledge base maintenance mechanism based on the negation as failure inference rule enables Sphinx to support incremental assertions and retractions. In addition, Sphinx provides explanation capability to help the user in developing and debugging knowledge bases.
29923826
A Relational Dataflow Database Machine Based on Hierarchical Ring Network
32944410
SPHINX - A Hybrid Knowledge Representation System
1176457
Effective Change Detection Using Sampling
For a large-scale data-intensive environment, such as the World-Wide Web or data warehousing, we often make local copies of remote data sources. Due to limited network and computational resources, however, it is often difficult to monitor the sources constantly to check for changes and to download changed data items to the copies. In this scenario, our goal is to detect as many changes as we can using the fixed download resources that we have. In this paper we propose three sampling-based download policies that can identify more changed data items effectively. In our sampling-based approach, we first sample a small number of data items from each data source and download more data items from the sources with more changed samples. We analyze the effectiveness of the sampling-based policies and compare our proposed policies to existing ones, including the state-of-the-art frequency-based policy in [8, 11]. Our experiments on synthetic and real-world data will show the relative merits of various policies and the great potential of our sampling-based policy. In certain cases, our sampling-based policy could download twice as many changed items as the best existing policy.
5763081
A probabilistic approach to metasearching with adaptive probing
An ever-increasing amount of valuable information is stored in Web databases, "hidden" behind search interfaces. To save the user's effort in manually exploring each database, metasearchers automatically select the most relevant databases to a user's query. In this paper, we focus on one of the technical challenges in metasearching, namely database selection. Past research uses a precollected summary of each database to estimate its "relevancy" to the query, and in many cases make incorrect database selection. In this paper, we propose two techniques: probabilistic relevancy modelling and adaptive probing. First, we model the relevancy of each database to a given query as a probabilistic distribution, derived by sampling that database. Using the probabilistic model, the user can explicitly specify a desired level of certainty for database selection. The adaptive probing technique decides which and how many databases to contact in order to satisfy the user's requirement. Our experiments on real hidden-Web databases indicate that our approach significantly improves the accuracy of database selection at the cost of a small number of database probing.
30800683
An optimal signal design for band-limited asynchronous DS-CDMA Communications
An optimal signal design for band-limited, asynchronous, direct-sequence code-division multiple-access (DS-CDMA) communications with aperiodic random spreading sequences and a conventional matched filter receiver is considered in an additive white Gaussian noise (AWGN) channel. With bandwidth defined in the strict sense, two optimization problems are solved under finite bandwidth and zero interchip interference constraints. First, a chip waveform optimization is performed given the system bandwidth, the data symbol transmission rate, and the processing gain. A technique to characterize a band-limited chip waveform with a finite number of parameters is developed, and it is used to derive optimum chip waveforms which minimize the effect of multiple-access interference (MAI) for any energy and delay profile of users. Next, a joint optimization of the processing gain and the chip waveform is performed, given the system bandwidth and the data symbol transmission rate. A sufficient condition for a system to have lower average probability of bit error for any energy profile is found, and it is used to derive some design strategies. It is shown that the flat spectrum pulse with the processing gain leading to zero excess bandwidth results in the minimum average probability of bit error. Design examples and numerical results are also provided.
9811102
Four-bend top-down global routing
We propose a new global net distribution approach for high-performance m/spl times/m two-dimensional arrays of very large scale integration and multichip-modules. The objective is to route n nets with minimum density of global cells, using a "small" number of bends. There are a number of applications where it is necessary to limit the number of bends on each wire. For example, it is desirable to limit the number of bends on each microstrip (transmission) line, for mismatches of line impedance can cause reflections from the junction points such as bends and vias. Furthermore, for high-performance routing, intersections of wires cause the use of more vias, which in turn require the use of more routing resources (because of the larger via pitch). This is the first paper that addresses a graph-theoretic framework to solve the bend-constrained global routing problem in two-dimensional arrays. In this paper, at each level of an underlying quad-tree, we present a novel four-bend routing algorithm by decomposing the original problem at level i into two subproblems that can be solved exactly based on a two-stage approach of smaller-sized linear program followed by min-cost flow networks. The overall (i.e., entire level of the four-way partition hierarchy) constraint and variable size for the first stage is O(md/sub o/), while the overall run time for the second stage is O(n/sup 3/ log n/sup 2/). The time complexity of such a hierarchical approach is one order of magnitude less than one of constructing a global routing using the min-cost-flow-based flat design approach. Last, we present an extension that permits a limited degree of control over the number of bends. The proposed algorithm can also be used for estimating the wireability in the early design planning stage for high-level synthesis. Experimental results showed the effectiveness of the proposed algorithm.
513620
Synchronizing a database to improve freshness
In this paper we study how to refresh a local copy of an autonomous data source to maintain the copy up-to-date. As the size of the data grows, it becomes more difficult to maintain the copy \ fresh, “making it crucial to synchronize the copy effectively. We define two freshness metrics, change models of the underlying data, and synchronization policies. We analytically study how effective the various policies are. We also experimentally verify our analysis, based on data collected from 270 web sites for more than 4 months, and we show that our new policy improves the \ freshness” very significantly compared to current policies in use.