the proceedings contain 44 papers. the special focus in this conference is on algorithms and datastructures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction fr...
ISBN:
(纸本)3540405453
the proceedings contain 44 papers. the special focus in this conference is on algorithms and datastructures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction from gene-rearrangement data with unequal gene content;common-deadline lazy bureaucrat scheduling problems;bandwidth-constrained allocation in grid computing;algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection;fast algorithms for a class of temporal range queries;optimal worst-case operations for implicit cache-oblivious search trees;extremal configurations and levels in pseudoline arrangements;fast relative approximation of potential fields;integrated prefetching and caching with read and write requests;online seat reservations via offline seating arrangements;routing and call control algorithms for ring networks;algorithms and models for railway optimization;approximation of rectilinear Steiner trees with length restrictions on obstacles;cropping-resilient segmented multiple watermarking;on simultaneous planar graph embeddings;approximation algorithm for hotlink assignments in web directories;drawing graphs with large vertices and thick edges;semi-matchings for bipartite graphs and load balancing;sorting circular permutations by reversal;an improved bound on Boolean matrix multiplication for highly clustered data;real two dimensional scaled matching;the zigzag path of a pseudo-triangulation;improved approximation algorithms for the quality of service Steiner tree problem;a model for analyzing black-box optimization;on the hausdorff voronoi diagram of point clusters in the plane;significant-presence range queries in categorical data and parameterized complexity of directed feedback set problems in tournaments.
Multimedia information is ubiquitous and essential in many applications from homeland security to medicine and bioinformatics. As evidenced by the success of the previous editions of MDM/KDD, there is an increasing ne...
ISBN:
(纸本)9781595938374
Multimedia information is ubiquitous and essential in many applications from homeland security to medicine and bioinformatics. As evidenced by the success of the previous editions of MDM/KDD, there is an increasing need in new techniques and tools that can detect and discover patterns, in multimedia data, that can lead to new knowledge. For example, tools are needed for discovering relationships between objects or segments within images, classifying images based on their content, extracting patterns in sound, categorizing speech and music, and recognizing and tracking objects in video streams. there is also an increasing interest in the real-time analysis of multimedia data generated by distributed sensory applications and ambient intelligence *** is a leading venue where researchers, both from the academia and industry, can exchange and compare both relatively mature and green house theories, methodologies, algorithms and frameworks for multimedia data mining. To address this aim, the workshop brings together experts in the analysis of digital media content, multimedia databases, multimedia information retrieval, and domain experts from different applied disciplines with potential in multimedia data mining and knowledge discovery. the previous seven workshops have been held in conjunction with KDD 2000 (Boston, MA), KDD2001 (San Francisco, CA), KDD 2002 (Edmonton, Canada), KDD 2003 (Washington, DC), KDD 2004 (Seattle, WA), KDD 2005 (Chicago, IL), and KDD 2006 (Philadelphia, PA) respectively. Like the previous editions, MDM 2007 aimed at facilitating cross-disciplinary exchange of *** 2007 contains six regular papers focusing on various aspects of multimedia data mining, including content-supported learning of user preferences, integration of multiple visual learners for media mining, salient-point based image object detection, the use of relevance feedback for video event mining, association rule mining for infrequent database items, and a novel
We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes 0(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting k...
详细信息
ISBN:
(纸本)3540405453
We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes 0(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting keys take O(log n) time. We show that these bounds can be simultaneously achieved in the worst case for searching and updating by suitably maintaining a permutation of the n keys in the array. the resulting data structure is called implicit as it uses just 0(l) extra memory cells beside the n cells for the array. the data structure is also cacheoblivious, attaining O(log(B) n) block transfers in the worst case for any (unknown) value of the block size B, without wasting any single cell of memory at any level of the memory hierarchy.
Given a set of P. objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing efficient indexing structures such that the following type of queries ca...
详细信息
ISBN:
(纸本)3540405453
Given a set of P. objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing efficient indexing structures such that the following type of queries can be handled efficiently: given d value ranges and a time interval, report or count all the objects whose attributes fall within the corresponding d value ranges at each time instance lying in the specified time interval. We establish efficient datastructures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of O(log n log m + f) for one-sided queries when d = 1, where f is the output size. We also show that the most general problem can be solved with polylogarithmic query time using nonlinear space datastructures.
the restricted rotation distance d(R)(S, T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of t...
详细信息
the restricted rotation distance d(R)(S, T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of the root. A sharp upper bound d(R) (S, T) <= 4n - 8 is known, based on group theory [S. Cleary, J. Taback., Bounding restricted rotation distance, Information Processing Letters 88 (5) (2003) 251-256]. We refine this bound to a sharp d(R) (S, T) <= 4n - 8 - rho(S) - rho(T), where rho(S) and rho(T) are the numbers of vertices in the rightmost vertex chains of the two trees, using an elementary transformation algorithm. We then generalize the concept to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree, and study the new distance for k = 2. the case k >= 3 is essentially open. (c) 2006 Elsevier B.V. All rights reserved.
作者：
Arge, LBRICS
Department of Computer Science University of Aarhus Denmark
In this paper we develop a technique for transforming an internal memory tree data structure into an external storage structure. We show how the technique can be used to develop a search-tree-like structure, a priorit...
详细信息
ISBN:
(纸本)3540602208
In this paper we develop a technique for transforming an internal memory tree data structure into an external storage structure. We show how the technique can be used to develop a search-tree-like structure, a priority-queue, a (one-dimensional) range-tree and a segment-tree, and give examples of how these structures can be used to develop efficient I/O-algorithms. All our algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms given the developed external datastructures.
At present, GPR profiling is widely used in engineering surveys and geotechnical investigations to handle various tasks. High efficiency and resolution of GPR technique help to obtain huge volumes of data, which need ...
详细信息
ISBN:
(纸本)9781479964956
At present, GPR profiling is widely used in engineering surveys and geotechnical investigations to handle various tasks. High efficiency and resolution of GPR technique help to obtain huge volumes of data, which need quicklook (real-time) data processing. In particular, this usually occurs while GPR surveys in highway and railway engineering, in water areas (rivers and lakes), line structures, etc. Here, the basic data-processing problem is of GPR records matching stretched interfaces of the beds with varying electrical and physical characteristics. Several algorithms were tested to pick wave patterns;STA\LTA tracing algorithms based on Radon or Hough transforms seemed to be the best to solve the problem.
In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of that color intersect...
详细信息
暂无评论