In recent years, several information retrieval methods using information about Web-links have been developed, such as HITS and trawling. In order to analyze Web-links dividing into links inside each Web site (local-links) and links between Web sites (global-links)for information retrieval, a proper model of the Web site is required. In existing research, a Web server is used as a model of the Web site. This idea works relatively well when a Web site corresponds to a server, as is the case for public Web sites, but works poorly when multiple Web sites correspond to a server, as is the case for private Web sites on rental Web servers. We propose a new model of the Web site, "directory-based site", to handle typical private sites, and a method to identify them using information about the URL and Web-links. We verify the method can approximately identify, at a rate of 66% of over 110,000 servers, whether each server has multiple directory-based sites or not, and extract over 500,000 directory-based sites and 4 million global-links by computational experiments using jp-domain URLs and Web-link data contains over 23 million URLs and 100 million Web-links, collected from July to August 2000, by Toyoda and Kitsuregawa. We also propose a new framework of Web-link based information retrieval that uses directory-based sites and global-links instead of Web pages and whole Web-links respectively, and examine the effectiveness of our framework by comparing a result of trawling on our framework to one on the existing framework.

The context tree weighting method is a universal compression algorithm for FSMX sources. Though we expect that it will have a good compression ratio in practice, it is difficult to implement it and in many cases the implementation is only for estimating compression ratio. Though Willems and Tjalkens (1997) showed a practical implementation using not block probabilities but conditional probabilities, it is used for only binary alphabet sequences. We extend the method for multi-alphabet sequences and show a simple implementation using PPM techniques. We also propose a method to optimize a parameter of the context tree weighting for binary alphabet case. Experimental results on texts and DNA sequences show that the performance of PPM can be improved by combining the context tree weighting and that DNA sequences can be compressed in less than 2.0 bpc.

No abstract available.

No abstract available.

Article Voronoi diagram in statistical parametric space by Kullback-Leibler divergence Share on Authors: Kensuke Onishi Graduate School of Science and Technology, Kobe University, Kobe, Japan Graduate School of Science and Technology, Kobe University, Kobe, JapanView Profile , Hiroshi Imai Department of Information Science, University of Tokyo, Japan Department of Information Science, University of Tokyo, JapanView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 463–465https://doi.org/10.1145/262839.263084Online:01 August 1997Publication History 12citation530DownloadsMetricsTotal Citations12Total Downloads530Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The multiple sequence alignment problem is very applicable and important in various fields in molecular biology.But the optimal alignment, based on the scoring criterion is not always the biologically most significant alignment.We here demonstrate two flexible and efficient approaches to solve this problem, together with computational results for largescale problems.One approach is to provide many suboptimal

No abstract available.

Regular triangulationsform a meaningful wide subclass of triangulations of points in general dimensions.They can be defined as a natural extension of the Delaunay triangulation and also of lexicographic triangulations, a subclass of triangulations well-known in the theory

No abstract available.

No abstract available.

In this paper we consider thek-clustering problem for a set S of n points i=(xi) in thed-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum on intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster Sj,

We consider a minimax facility location problem for n points such that the facility is a line segment of a given length. The general problem can be solved by case analysis in O(n4 log n) time. When the orientation of the segment is fixed, the problem is shown to be linear-time solvable by using the prune-and-search technique. Other variations of this problem are also discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in Ο(m4n λ16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in Ο(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of κ rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for κn points is shown to be Ο(n2) and Ο(n3κ4 log* κ) for κ = 2, 3 and κ ≥ 4, respectively. Several related problems are also treated in a unified way.

Article Free Access Share on Fining k points with minimum spanning trees and related problems Authors: A. Aggarwal IBM T. J. Watson Research Center IBM T. J. Watson Research CenterView Profile , H. Imai Kyushu University, Japan Kyushu University, JapanView Profile , N. Katoh Kobe University of Commerce, Japan Kobe University of Commerce, JapanView Profile , S. Suri Bell Communications Research Bell Communications ResearchView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 283–291https://doi.org/10.1145/73833.73865Published:05 June 1989Publication History 7citation660DownloadsMetricsTotal Citations7Total Downloads660Last 12 Months14Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

No abstract available.

This paper presents algorithms for approximating a set of n points by a linear function, or a line, that minimizes the L1 norm of vertical and orthogonal distances. The algorithms find exact solutions based upon geometric properties of the problems as opposed to approximate solutions based upon existing numerical techniques. The algorithmic complexity of these problems appears not to have been investigated before our work in [9], although Ο(n3) naive algorithms can be easily obtained based on some simple characteristics of optimal L1 solutions. In this paper, an Ο(n) optimal time algorithm for the weighted vertical L1 problem is presented. The algorithm is based upon a modified multi-dimensional search technique which extends the applicability of the basic technique to a wider class of problems. An Ο(n1.5 log2 n) algorithm is presented for the unweighted orthogonal problem, and an Ο(n2) algorithm is presented for the weighted problem. An Ω(n log n) lower bound for the orthogonal L1 problem is shown under a certain model of computation. Also, the complexity of solving the orthogonal L1 problem is related to the construction of the k-belt of an arrangement of lines.

Given a set of non-intersecting line segments in the plane, we are required to connect the line segments such that they form a simple circuit (a simple polygon).However, not every set of segments can be so connected.Figure 1 shows a set of segments that does not admit a simple circuit.This leads to the challenging problem of determining when a set of segments admits a simple circuit, and if it does, then find such a circuit.It has been shown [Rappaport] that in general, to determine whether a set of segments admits a simple circuit is NP-complete.In this paper an optimal algorithm is presented to determine whether a simple circuit exists, and deliver a simple circuit, on a set of line segments, where each segment has at least one endpoint on the convex hull of the segments (a CHconnected set of segments).Furthermore this technique can be used to determine a simple circuit of minimum length, or a simple circuit that bounds the minimum area, with no increase in computational complexity.The rest of the paper is summarized.In section 2 cf this paper, the preliminary definitions and notation are introduced.In section 3, the geometric properties of the set, of segments are used to transform the segments into an associated graph.

The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number M * of the trapezoids in the minimum partition of a polygonal region P is shown to be M * = n + w - h - d - 1, where n , w , and h are the number of vertices, windows (holes), and horizontal edges of P , respectively, and d is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with P . Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an O ( n 2 )-time algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an O ( n log n )-time approximation algorithm with the performance bound 3 is presented.

In this paper, we show that many graph search problems can be solved quite efficiently for a geometric intersection graph of horizontal and vertical line segments. We first extract several basic operations for depth first search and breadth first search on a graph. Then we present data structures for the intersection graph in terms of which those operations can be implemented in an efficient manner. The data structures enable us to solve various graph search problems besides depth first search and breadth first search. Specifying the results obtained in this paper for an intersection graph of n horizontal and vertical segments with m pairs of intersecting segments, we obtain algorithms with the following complexity, where $N = \min \{ m,n\log n\} $. (i) Depth first search and breadth first search can be executed in $O(n\log n)$ time and $O(N)$ space. (ii) The biconnected components can be found in $O(n\log n)$ time and $O(N)$ space. (iii) A maximum matching and a maximum independent set can be found in $O(\sqrt n N)$ time and $O(N)$ space when no two horizontal (vertical) segments intersect. (iv) The connectivity $k_G $ can be found in $O(k_G n^{{3 / 2}} N)$ time and $O(N)$ space. Our algorithms can be applied to various practical problems such as the problem of finding a minimum dissection of a rectilinear region, which arises in the manipulation of VLSI artwork data, and the problem of determining whether there is a Manhattan wiring on a single layer, which arises in the design automation of digital systems.

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n2) time, improving earlier O(n2 log n) results.

We extend the concept of Voronoi diagram in the ordinary Euclidean geometry for n points to the one in the Laguerre geometry for n circles in the plane, where the distance between a circle and a point is defined by the length of the tangent line, and show that there is an $O(n\log n)$ algorithm for this extended case. The Voronoi diagram in the Laguerre geometry may be applied to solving effectively a number of geometrical problems such as those of determining whether or not a point belongs to the union of n circles, of finding the connected components of n circles, and of finding the contour of the union of n circles. As in the case with ordinary Voronoi diagrams, the algorithms proposed here for those problems are optimal to within a constant factor. Some extensions of the problem and the algorithm from different viewpoints are also suggested.

In this paper, we consider two restricted types of dynamic orthogonal segment intersection search problems. One is the problem in which the underlying set is updated only by insertions. In the other, the set is updated only by deletions. We show that an intermixed sequence of O(n) queries and updates in both problems can be executed on-line in O(n log n+K) time and O(n log n) space, where K is the total number of reported intersections. Our algorithms utilize set-union and set-splitting algorithms. Especially, we present a linear-time algorithm for the incremental set-splitting problem, and use it for the problem in which only insertions are allowed. The data structures developed here give new better solutions for various geometric problems on orthogonal segments. We give a paradigm of solving those geometric problems by combining graph algorithms with these data structures, and describe a variety of applications.