Abstract In this paper we study regular expression matching in cases in which the identity of the symbols received is subject to uncertainty. We develop a model of symbol emission and uses a modification of the shortest path algorithm to find optimal matches on the Cartesian Graph of an expression provided that the input is a finite list. In the case of infinite streams, we show that the problem is in general undecidable but, if each symbols is received with probability 0 infinitely often, then with probability 1 the problem is decidable.

Abstract In this paper we present an indexing method for probably approximately correct nearest neighbor queries in high dimensional spaces capable of improving the performance of any index whose performance degrades with the increased dimensionality of the query space. The basic idea of the method is quite simple: we use SVD to concentrate the variance of the inter-element distance in a lower dimensional space, Ξ. We do a nearest neighbor query in this space and then we “peek” forward from the nearest neighbor by gathering all the elements whose distance from the query is less than $d_{\Xi }(1+\zeta \sigma _{\Xi }^{2})$ d Ξ ( 1 + ζ σ Ξ 2 ) , where dΞ is the distance from the nearest neighbor in Ξ, $\sigma _{\Xi }^{2}$ σ Ξ 2 is the variance of the data in Ξ, and ζ a parameter. All the data thus collected form a tentative set T, in which we do a scan using the complete feature space to find the point closest to the query. The advantages of the method are that (1) it can be built on top of virtually any indexing method and (2) we can build a model of the distribution of the error precise enough to allow designing a compromise between error and speed. We show the improvement that we can obtain using data from the SUN data base.

We develop a model of infection spread that takes into account the existence of a vulnerable group as well as the variability of the social relations of individuals. We develop a compartmentalized power-law model, with power-law connections between the vulnerable and the general population, considering these connections as well as the connections among the vulnerable as parameters that we vary in our tests. We use the model to study a number of vaccination strategies under two hypotheses: first, we assume a limited availability of vaccine but an infinite vaccination capacity, so all the available doses can be administered in a short time (negligible with respect to the evolution of the epidemic). Then, we assume a limited vaccination capacity, so the doses are administered in a time non-negligible with respect to the evolution of the epidemic. We develop optimal strategies for the various social parameters, where a strategy consists of (1) the fraction of vaccine that is administered to the vulnerable population and (2) the criterion that is used to administer it to the general population. In the case of a limited vaccination capacity, the fraction (1) is a function of time, and we study how to optimize it to obtain a maximal reduction in the number of fatalities.

Abstract We present a collection of algorithms to filter a stream of documents in such a way that the filtered documents will cover as well as possible the interest of a person, keeping in mind that, at any given time, the offered documents should not only be relevant, but should also be diversified, in the sense of covering all the interests of the person. We use a modification of the WEBSOM algorithm to create a user model based on a self‐organizing network trained using a collection of documents representative of the person's interests. We introduce the concepts of freshness and coverage. A document is fresh if it belongs to a semantic area of interest to a person for which no documents were seen in the recent past; a group of documents has coverage to the extent to which it is a good representation of all the interests of a person. Our tests show that these algorithms can effectively increase the coverage of the documents that are shown to the user without overly affecting precision.

One of the most common ways in which results are displayed by an information retrieval system is in the form of a list, in which the most relevant results appear in the first positions. Today's large screens, however, allow one to create more complex displays of results, especially in cases such as image retrieval, in which each unit returned is fairly compact. For these layouts the simple list model is no longer valid, since the relations between the slots in which the results are placed do not form a sequence, that is, the relation among them is no longer that of a total order. In this paper we model these layouts as partial orders and show that a "stalwart display" property (a layout in which items' relevance is unambiguously conveyed by their display position) can be obtained only in the case of lists. For the other layouts, we define two classes of representation functions: "safe" functions (which display results without adding spurious structure) and "rich" functions (which do not drop any structure from the result set), as well as an algorithm to optimally display fully ordered result sets in arbitrary display layouts.

In many taditional retrieval systems, the results are scored using a single real value (representing relevance) and displayed using a list-like interface, which presents a natural correspondence with the ordering induced by the scores. In many moderns systems, however, the layout of the result is considerably more complex than a simple list of result.

This short overview describes the contents of the tutorial Semantic computing in multimedia, which was offered to the participants of ACM Multimedia 2011.

This article introduces the notion of virtual feature stream , a feature stream defined from a primary data stream, in which at any time only the features that are needed to compute the queries that are currently running in the system are computed. Virtual feature streams are, in general, impossible to determine a priori, but the paper introduces an algorithm that stops the computation of features as soon as it can be proved that they are no longer needed thus generating, albeit in a roundabout and more expensive than the ideal way, a feature stream that is less expensive than the complete one to compute and safe: the queries that accept the virtual feature stream are those (and only those) that would accept the original feature stream.

panel "Disputatio" on the Use of Ontologies in Multimedia Share on Authors: Simone Santini Universidad Autónoma de Madrid, Madrid, Spain Universidad Autónoma de Madrid, Madrid, SpainView Profile , Amarnath Gupta University of California San Diego, La Jolla, CA, USA University of California San Diego, La Jolla, CA, USAView Profile Authors Info & Claims MM '10: Proceedings of the 18th ACM international conference on MultimediaOctober 2010 Pages 1723–1728https://doi.org/10.1145/1873951.1874340Online:25 October 2010Publication History 2citation133DownloadsMetricsTotal Citations2Total Downloads133Last 12 Months1Last 6 weeks1 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

This paper presents an overview of the data integration mediation system developed as part of the Biomedical Informatics Research Network (BIRN; http://www.nbirn.net) project. BIRN is sponsored by the National Center for Research Resources (NCRR), a component of the National Institutes of Health (NIH). A core BIRN goal is the development of a multi-institution information management system to support biomedical research. Each participating institution maintains a database of their experimental or computationally derived data, and the data integration system performs semantic integration over the databases to enable researchers to perform analyses based on larger and broader datasets than would be available from any single institution's data. This demonstration paper describes architecture, implementation, and capabilities of the semantically based data integration system for BIRN

This paper presents the rudiments of a theory of schema design for databases containing high dimensional features of the type used for describing multimedia data. We introduce a model of multimedia database based on tables containing feature types, and the concept of schema design which is based on splitting tables depending on the functional relations between different parts of the features. We show that certain relations between substructures of a same feature structure can lead to schemas for which efficient algorithms for k-nearest neighbor and range searches can be defined.

This paper defines wavelet transforms as a datatype suitable for inclusion in databases and an algebra for the manipulation of this data type.

In this paper, we briefly discuss some aspects of image semantics and the role that it plays for the design of image databases. We argue that images don't have an intrinsic meaning, but that they are endowed with a meaning by placing them in the context of other images and by the user interaction. From this observation, we conclude that, in an image, database users should be allowed to manipulate not only the individual images, but also the relation between them. We present an interface model based on the manipulation of configurations of images.

A prototype semiorder database used for activity recognition in multi-sensory monitoring environments is described. Activities are spatio-temporal compositions of events, which are a type of atomic semantic units for such compositions. The focus is on the temporal composition of activities from events in the presence of bounded duration of temporal uncertainty in an event occurrence. Such temporal uncertainty forces the concurrency between event occurrences to be intransitive. Under certain assumptions, a subclass of partial orders, known as semiorders, models such intransitive concurrency appropriately. The semiorder database stores events and their semiorder temporal order of occurrences. A semiorder data model and the corresponding query language that embeds a semiorder pattern language are the main constituents of the semiorder database. We demonstrate this database and queries for activity recognition in a real time environment. The demonstration also includes a transducer subsystem for detection of events.

With the development of the Internet and the omnipresence of video cameras, the amount of visual information available to individuals with access to the world wide web has increased by orders of magnitude in the last few years. Due to cost and communication constraints, this information is usually of rather low quality. The cooccurrence of a large number of sensors and the low quality of every single sensor has the potential to create a new episteme in computer vision. This paper presents an example of how certain limitations of a single sensor can be overcome by using the sensor multiplicity. Using a number of web cameras available in the Seattle area, the paper performs first a simple qualitative traffic analysis from each single camera. Since the cameras provide images at a very low rate (1 image every 2 minutes), standard techniques based on motion detection are unusable, and the paper proposes a simple approach based on image variance. Then, the data are integrated using the structure of the Seattle highway system and network tomography to determine the major flows of traffic at different times of the day.

Presents a review of 200 references in content-based image retrieval. The paper starts with discussing the working conditions of content-based retrieval: patterns of use, types of pictures, the role of semantics, and the sensory gap. Subsequent sections discuss computational steps for image retrieval systems. Step one of the review is image processing for retrieval sorted by color, texture, and local geometry. Features for retrieval are discussed next, sorted by: accumulative and global features, salient points, object and shape features, signs, and structural combinations thereof. Similarity of pictures and objects in pictures is reviewed for each of the feature types, in close connection to the types and means of feedback the user of the systems is capable of giving by interaction. We briefly discuss aspects of system engineering: databases, system architecture, and evaluation. In the concluding section, we present our view on: the driving force of the field, the heritage from computer vision, the influence on computer vision, the role of similarity and of interaction, the need for databases, the problem of evaluation, and the role of the semantic gap.

With complex multimedia data, we see the emergence of database systems in which the fundamental operation is similarity assessment. Before database issues can be addressed, it is necessary to give a definition of similarity as an operation. We develop a similarity measure, based on fuzzy logic, that exhibits several features that match experimental findings in humans. The model is dubbed fuzzy feature contrast (FFC) and is an extension to a more general domain of the feature contrast model due to Tversky (1977). We show how the FFC model can be used to model similarity assessment from fuzzy judgment of properties, and we address the use of fuzzy measures to deal with dependencies among the properties.

This paper considers some of the problems we found trying to atract mtig from image in database applications, and propos= some wa~s to solve th-~k argue that the m-g of an image xs an N-d@ed enti@, and it is not in general possible to derive from m image the mwning that the user of the database ~ts.&tier, we shodd be contrmt tith a wrreKation between the intended meaning ad simple perceptual du~that databases -~.&ther than ~orking on the impossible task of ~g unaxnblguous meaning from ixnag~, we shoxdd provide the user with the took he needs to tire the database in the arm of the f=ture space where %ter~~dges are -.-.. .-=.

This paper considers some of the problems we found trying to extract meaning from images in database applications, and proposes some ways to solve them. We argue that the meaning of an image is an ill-defined entity, and it is not in general possible to derive from an image the meaning that the user of the database wants. Rather, we should be content with a correlation between the intended meaning and simple perceptual clues that databases can extract. Rather than working on the impossible task of extracting unambiguous meaning from images, we should provide the user with the tools he needs to drive the database in the areas of the feature space where "interesting" images are.

We describe our "virtual museum" project: an union of image and text retrieval technologies that allows users to visit art collections on the Web. The virtual museum is composed of a series of rooms that the user can visit. The connections between the rooms are variable: passing from a room to another yields a result which is the outcome of a query, and depends on the query criterion that the user has selected. This "variable topology" adds interest to the museum visit since it allows the visitor, within certain limits, to customize his/her museum experience and to make it different every time.

We analyze the operations that form the conceptual foundation of a traditional database: the determination and matching of the meaning of a record of data. With a careful definition of the "meaning" of a piece of data, we show that matching can be naturally defined. We then analyze whether a similar concept can be applied to image databases. We argue that several concepts, that led to image database models based on matching, cannot be reasonably extended to the visual world of a perceptual search engine.

Query-by-content image database will be based on similarity, rather than on matching, where similarity is a measure that is defined and meaningful for every pair of images in the image space. Since it is the human user that, in the end, has to be satisfied with the results of the query, it is natural to base the similarity measure that we will use on the characteristics of human similarity assessment. In the first part of this paper, we review some of these characteristics and define a similarity measure based on them. Another problem that similarity-based databases will have to face is how to combine different queries into a single complex query. We present a solution based on three operators that are the analogous of the and, or, and not operators one uses in traditional databases. These operators are powerful enough to express queries of unlimited complexity, yet have a very intuitive behavior, making easy for the user to specify a query tailored to a particular need.

We show that a certain class of similarity measures, which is based on set-theoretic concepts, and explains many of the characteristics of human similarity assessment, can be interpreted as a distance in a suitable psychological space. This view unifies a number of different measures of similarity that psychological experiments have determined to be active in humans for different classes of stimuli. The study arises out of a consideration of similarity in retrieval from a multimedia database.

Many of the properties of the well-known Kohonen map algorithm are not easily derivable from its discrete formulation. For instance, the "projection" implemented by the map from a high dimensional input space to a lower dimensional map space must be properly regarded as a projection from a smooth manifold to a lattice and, in this framework, some of its properties are not easily identified. This paper describes the self-organizing field: a continuous embedding of a smooth manifold (the map) into another (the input manifold) that implements a topological map by self-organization. The adaptation of the self-organizing field is governed by a set of differential equations analogous to the difference equations that determine weights updates in the Kohonen map. This paper derives several properties of the self-organizing field, and shows that the emergence of certain structures on the brain-like the columnar organization in the primary visual cortex-arise naturally in the new model.

We present a method for elastic pattern matching that we apply to segmentation-free OCR. We use a number of digit models (templates) that are allowed to undergo elastic deformation while trying to adapt to the digit image they are exposed to. Each template must satisfy two competing requirements: (1) it must match the image as much as possible and (2) it must keep its elastic deformation energy as little as possible. These two requirements can be expressed in the form of a variational problem, whose solution gives the optimal deformation for a template.

Fiber Distributed Data Interface (FDDI) local area networks (LAN's) are used either as high-speed links between computers and peripherals, or as backbones for lower-speed LAN's, such as Ethernet and Token Ring. The availability of such a high-speed channel will lead to the implementation of high-performance distributed environments spread over a wider area than that allowed by commonly used LAN's. The performance of such distributed environments will strongly depend on that of the interconnecting devices. In this paper, two different algorithms for packet filtering are discussed, referring to bridges interconnecting Ethernet LAN's to FDDI backbones. Algorithm performance is compared with respect to 1) the traffic increase produced on a local Ethernet, and 2) the maximum allowed traffic on remote Ethernets.>

Mobile robots and vehicles may be driven by dynamical neural networks which utilize image data of real-world scenes collected through a TV camera for learning and performance. An innovative system for road direction detection is proposed which is comprised of three specialized blocks performing edge extraction, image-segments detection, and road direction estimation. The road direction estimation block is implemented as a feedback neural network.>

A two-layers architecture for optical flow computation is presented, which uses neural nets in the lower layer and a special relaxation system in the upper layer. The high degree of parallelism of the architecture makes it particularly suitable for real-time applications.>